Finding the polygon that encompasses some points, but others must be outside

euclidean-geometrygeometry

I have a convex/concave hull problem that must include some vertices, but not all of them. Some points must be outside of the polygon and some are optional.

I took a look at Graham's scan algorithm, but it's not exactly what I'm looking for. Since I have these optional vertices and these points that must be outside the resulting polygon.

For example:

  • Points that must be included: (0,0),(10,4),(0,5),(2,4).
  • Points that are optional: (2,3),(4,3).
  • Points that must be outside: (3,2).

The resulting polygon would be with the points: (0,0),(2,3),(10,4),(0,5).

  • If I were to just use the first 3 points, (3,2) would be inside. So we use the optional (2,3), but we don't need (4,3).

So this would be the result: (Red line marks an invalid path taken)

enter image description here

Is there an algorithm that can solve this problem already? I can only find algorithms that would include everything.

Thank you! 🙂

Best Answer

Just an update. I haven't found anything that helped me, but this is how I solved the problem:

  • I have organization groups that dictates the order of points I'm traveling. Let's call it PointGroup.
  • The polygon in the original example would be a group with this points in this order: (0,0),(2,3),(10,4),(0,5). The last points connects with the first point as well.

The algorithm:

  1. Create several PointGroups, each containing a different only one mandatory point. So far the perimeter is 0, and it's not a polygon.
  2. Pick the PointGroup with smallest perimeter.
  3. Check if:
  4. If the condition fails:
    • Create several child PointGroups, each by adding a single point. I try every possibility using mandatory and possible points.
    • Return to 2.
  5. If the condition succeeds, this PointGroup is the answer to the problem.

Not sure if this is optimal, but it works.

Related Question