CODEWITHSUNDEEP
c#algorithmgeometry
Aaginor
Aaginor

Reputation: 4782

Modifying a convex hull to exclude unwanted points

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

Upvotes: 0

Views: 1400

Answers (1)

Luka Rahne
Luka Rahne

Reputation: 10447

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.

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

Complexity is now N*log(N)

Upvotes: 0

Related Questions