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.