How to find the smallest bounding box in a spread of 2D Vectors

[david]

Hey all.
Moving this topic from rio to the forum.

I am wrapping my head around a problem which might be easy to solve but my brain is not working anymore… :-) I am looking for the smallest bounding box around a given center position from a given spread of 2d vectors.

see patch:
SmallestBoundsQuestion.v4p (10.9 KB)

–
In Riot Tebjan came up with a VL based approach.

Approach.zip (6.5 KB)

Anyhow, it is not solving the boundings properly yet. The bounding box should always contain the center point.
Anybody can help?

thanks

[readme]

I guess all there’s left to do for tebjan’s solution to work is to also do a max/min check with the resulting two points PLUS the input coordinate itself

[antokhio]

Yea, you got yourself a headache

[Hadasi]

Maybe find the smallest box containing three points in an OcTree and test there distances from each other? Use FromPointCloud to make a bounding box (in 3D) or use Rectangle (JoinPoints) (in 2D)?

[gregsn]

Sounds like:
You need 4 boolean flags that tell you if you have already found a

• x that is smaller than CenterPoint.X. Let’s call this flag FoundMinX
• so you need FoundMaxX, FoundMinY, FoundMaxY as well

Algorithm:

• Start with CenterPoint, all flags are false
• For each point in spread
  • If (PointX < CenterPoint.X)
    • If (not FoundMinX) => MinX = PointX; FoundMinX = true
    • else If (PointX > MinX) => MinX = PointX;

And now do this for the other flags as well…
This is a rather complicated solution, but should work, no?

[readme]

After having a chat with David it turned out the actual problem is a bit more complex and also needs to hold a state and cover some more cases … the solution is not unique to a random pointcloud and depends on the interaction with the system and how those coordinates move. We were kind of close to a solution though last night

[gregsn]

My “solution” above is probably wrong.

I think you need to precisely define what you need:

• (1) May the CenterPoint be on the border or not?
• (2) Define smallest. Is it about the area or the distance?

Let’s assume that the Centerpoint shall not be on the border. Then there are two possibilities to surround the Centerpoint

• (A) a point on left-top quadrant and a point on right-bottom quadrant OR
• (B) a point on left-bottom quadrant and a point on right-top quadrant.

Those quadrants are surrounding the Centerpoint.

You maybe could create 4 spreads (1 for each quadrant).
(A) If there is at least one point in left-top and at least one in right-bottom then this is an option. You start with those first points of those two quadrants. Let’s say it is not about the area, because you want to avoid very thin and wide rectangles. So let’s stick with the distance. For each quadrant you compute the one point with the smallest distance to the center independently. Now do the same for (B).
You now often have two solutions (A) and (B) that you need to compare and pick from.

Sorting into different quadrants very much goes into the answer Hayden provided.