Determine if polygon has a hole?

Question

After experimenting with some triangulation work I ran across the question on how to determine if a polygon has a hole?

I know how to handle a known hole but am unsure of how to determine if one exists.

Example:

Given the following vertices:

0 ( 0, 0)
1 ( 0,20)
2 (20,20)
3 ( 0,20)
4 ( 2, 2)
5 ( 6, 2)
6 ( 6, 6)
7 ( 2, 6)

How do I know if it is a simple polygon such as:

or a non-simple/complex polygon like:

I ask because the data that I will have to work with has the potential of being a polygon with a hole, but I will have no knowledge beforehand of it being so.

note: the polygon will never be complex. I just need to know when the vertices of the outside of the polygon ends and the vertices comprising the hole begin.

Answer 1

From the vertices alone you cannot infer the layout of the polygon's edges. You will need to keep the edges as well (for example as pairs of vertices).

In your example, another graph layout would be, for instance, 0-1-5-6-2-3-7-4-0 where the resulting polygon contains no hole at all.

If you have the edges, you can align them so that they form circles, i.e. group those with common second/first element together: (0, 1), (1, 2), (2, 3), (3, 0) and (4, 5), (5, 6), (6, 7), (7, 4). If there is a hole, there will be two or more such groups which cannot be grouped together any further. You can then find out whose points are within the area surrounded by the other points to know where the hole is.

Answer 2

Figure out if two non-adjacent line segments intersect, and you will find the split between the hole and the polygon. Yes, this algorithm is O(n²), but a bit of foreknowledge can help cut down the number of tests.

Answer 3

I have yet too low reputation to comment on an answer, but I want to say that I strongly recommend to follow mathematical convention regarding holes. The outer polygon should go anti clockwise and the hole should always go clockwise. MATLAB does this in reverse order, but that goes then for both polygon (clockwise) and holes (anti-clockwise)

Answer 4

you can select a point from one circle "B" and judge whether the selected point is inside or outside another circle "A". If is, then you get the hole. If not, then you select a point from the circle A and judge whether the point is inside the circle B, if is, you get the holes.