I Choosing points from a set that produce the largest polygon

[Jeff.Nevington]

I am trying to find the most efficient way to select points on a 2d plane from a set that maximizes the area of the of the shape they define when joined together.

The points are all paired (sharing the same A->B vector), with these pairs also appearing mirrored about the origin. Here is an example:

https://i.imgur.com/MNARxPI.png

Sometimes a single point is used from the pair, and sometimes both.

For any given problem I can easily draw the solution by hand, but I am struggling to clearly define a sensible solution. I can loop through and for each point, check adjacent points, using the solution for which no other point in the subset is further from the origin than the joining line, but it seems messy. I feel like there should be a more elegant solution.

Does anyone have any ideas?

 

[.Scott]

It's not so much finding a way to do it - but finding a relatively efficient way.
I would start by computing the average X,Y of all points, and then identifying the ones that are furthest from that center in each of 8 directions. I pick 8 directions because it is easy to sort them that way based on X>0, Y>0, and |X|>|Y|.
Then I would form large triangles with that initial group of points and eliminate any other point that fell within the triangle. Determining whether a point is inside a triangle (or any polygon) can be done by determining which side of each line of the triangle the point is on, if it is on the inside side of each line, it is inside the triangle and can be eliminated.

Ultimately, this test can be applied to all triangles and all points - all groups of 4 of the remaining points.

From there, it is just a matter of finding optimizations.

 

[.Scott]

Actually, any point that is furthest in any direction must be part of the border.
So start by finding the points with max and min X, max and min Y, max and min (X+Y)/2, and max and min (X-Y)/2.
Then eliminate all point that are within the resulting polygon.
Finally, do the "ultimate test" that I described above - except you do not have to test those original point, since they are definitely to be included.

 

[.Scott]

It's unclear whether there are additional constraints to your data.
Specifically:
When you draw a vector from one point in a pair to the other, is that vector of the same size and direction as all other vectors in the set?
If you take the midpoint of each pair, are they always the vertices of a convex polygon? With the points following clockwise or counter clockwise along that polygon?

If the answer to all three is yes, then rotate your figure so that the pair direction is along the X direction. Then, as you follow the pairs clockwise:
* for each segment that is decending (-Y direction), use the high X member of the pair;
* for each segment that is ascending (+Y direction), use the low X member of the pair.
Two pairs will have end up using both points. Those will be the ones where the trailing segment heads in a different Y direction than the leading segment.

 

[Jeff.Nevington]

Hi Scott! Thanks for these ideas. I really like the last one, though unfortunately the centers do not necessarily form a convex polygon. However, on reconsidering the problem I am dealing with, I would not be interested in points that contributed to a non-convex shape, so I think all I might need is to choose an existing convex hull algorithm.

 

[.Scott]

Hi Scott! Thanks for these ideas. I really like the last one, though unfortunately the centers do not necessarily form a convex polygon. However, on reconsidering the problem I am dealing with, I would not be interested in points that contributed to a non-convex shape, so I think all I might need is to choose an existing convex hull algorithm.

If you have a concave polygon, or one that may be concave, just follow it around taking the cross product of each adjacent pair of sides. Depending on the direction of travel (clockwise or CCW), you will be looking for only positive or negative cross products. If you find one that doesn't belong, the point between them should be dropped.