Modifying a convex hull to exclude unwanted points

Question

In my C#-Silverlight 3 program, I have a set of points. Those points can be of a different color, green, red or blue. Then I create a convex hull for the different points: A hull for green, a hull for red and a hull for blue. Now it can happen, that within the hull of each color are points from another color, like red points within the green hull.

Are there any algorithms to modify the hull, so that those other-colored points would be excluded from the hull (which wouldn't be convex anymore at this point)?

Thanks in advance, Frank

What do you mean by excluding? You mean removing these points? But when removing some points, you might "break" an existing convex hull. And what would happen when all points of the green convex hull are inside the red convex hull? More details are needed to answer this question. A concrete expample would also help. — Bart Kiers
By "breaking" a convex hull, I meant removing say 3 of the 5 points of the convex hull because these 3 points were inside another hull. Then you end up with 2 remaining points which cannot be a convex hull. — Bart Kiers

Luka Rahne Luka Rahne · Accepted Answer · 2009-10-20T13:42:36

Translate to classic travelling salesman problem.

Use points that generates this hull and add the other points that you want them to exclude. Now find shotrest path over this points and you have this new hull

EDIT

We need to find one noncrossing path over points.

Find one point in middle (artithmetic center for instance)
Calculate angle to each point (use function atan2)
Sort this points by angle.

Complexity is now N*log(N)

Modifying a convex hull to exclude unwanted points

1 Answers