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)
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:
The algorithm:
Not sure if this is optimal, but it works.