I am currently in the process of writing software and have encountered a mathematical problem. Perhaps there are some experts here who are familiar with this. It involves the classification of polygons with n points in 2D space, generalizing the classic convex and concave cases.
Each polygon is assigned a number of so-called "waterholes" and "airpockets." I imagine the polygon as a container that is filled with water from the deepest point (the first waterhole). During the filling process, the water may spill into lower areas, which would result in additional waterholes. The number of different points where the water touches the ceiling at possibly different locations, I call airpockets.
It's easy to see that a rectangle, regardless of its orientation, can always be assigned the tuple (1,1). It has exactly one waterhole and exactly one airpocket.
Another example for illustration is the following zigzag shape: In two figures, I have drawn it once as type (2,2) and once as type (1,1).
My current pseudocode looks like this:
if polygon isConvex {
return (1,1)
} else {
...
}
To check if a polygon is convex, I use the following algorithm: Form the cross product of two consecutive pairs of vectors that outline the polygon. If the x₃-component of the cross product is of the same sign for all these pairs, the polygon is convex.
Currently, my idea is to refine this algorithm further and create regions where the x₃ components are either positive, negative, or zero. Within these regions, I search for the point of the polygon with the highest or lowest y-component to conclude the existence of a waterhole or an airpocket.
This seems complicated and fishy. Are there better ideas? Removing points of the polygon step by step and then checking each time for convexity/concavity?
tl;dr: I am looking for a mapping from $\mathbb{R}^{2n} \to \mathbb{R}^2$, which assigns to each polygon the number of its waterholes and airpockets. Bonus points if the index of the special points can also be extracted.
