For a visibility algorithm I want to remove verts of polygon that are guaranteed not visible from a vert S. The idea is to remove pockets that points are on the backside of a plane formed by the vector n, the perpendicular vector between S and 0, and a point S.
The prerequisites are:
- the points of a polygon are in ccw order
- the labeled points are the cutting-points between g(t) and the edges of the polygon
- sorted by occurrence with respect to S
- only the points with a positive t are retained
- the points are part of a new created polygon, we are working with
The difficult task is to identify a pocket respectively the pair of indices a pocket starts and ends.
Here are my approaches:
- Use the natural order of cutting-points and remove items with a smaller t to their previous ones (works on I, III and IV).
- Sort the cutting-points by t. If the second point has the highest index in the original order, then all other cutting-points are part of the pocket and can be ignored (works on II).
Now the questions are:
- When should I use the first and when the second approach (I can't see it)?
- Is there an easier way?