Delete holes in a Polygon

Question

I have a polygon determined by an Array of Points.

This polygon is crossing itself making some holes in the polygon itself.

My questions is: How can I omit this holes and just get the exterior points of the polygon?

Or what will be the same and probably easier: Which Algorithm for checking if a point is inside a Polygon should I use to detect the points in the holes of the polygon as inside points?

Thanks in advance,

/roger

Answer 1

First, find all intersections of edges, add these intersections to the vertices list, and split the edges at these intersections. Then, start with one vertex that is obviously an external one (e.g. the "rightmost") and trace the outline, adding edges and vertices to the result sets. Tracing the outline is simply going along the edge with minimum angle to the last edge.

Answer 2

You might want to find the convex hull of all the points in your polygon.

One algorithm for doing this is Graham-Scan with complexity O(nlgn). From Cormen:

Let Q be the set of all points in your polygon
Graham-Scan(Q)

1  let p0 be the point in q with the minimum y-coordinate or the leftmost in case of tie
2  let (p1, p2,...,pm) be the remaining points in Q, sorted by polar angle around p0
       if more than one point shares the same polar angle, keep the farthest point

3  let S be an empty stack
4  PUSH(p0, S)
5  PUSH(p1, S)
6  PUSH(p2, S)
7  for i = 3 to m
8    while the angle formed by points NEXT_TO_TOP(S), TOP(S), and pi makes a non-left turn
9        POP(S)
10   PUSH(pi, S)
11 return S

S now contains all of the outer points of your polygon. You'll have to do some polar math, but that's pretty simple. To sort by polar order sort all points on their cotangent with your bottom most point. I forget the code for checking a right turn, but it's on the internet if you just search fro Graham-Scan. Hope this helps!