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.