Finding the polygon that encompasses some points, but others must be outside 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! :)
 A: 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:

*

*Create several PointGroups, each containing a different only one mandatory point. So far the perimeter is 0, and it's not a polygon.

*Pick the PointGroup with smallest perimeter.

*Check if:

*

*It contains at least 3 points (is it a polygon?).

*All mandatory points are in the group.

*A point that needs to be outside is inside. (https://en.wikipedia.org/wiki/Point_in_polygon)



*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.



*If the condition succeeds, this PointGroup is the answer to the problem.

Not sure if this is optimal, but it works.
