enter image description here

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:

  1. Use the natural order of cutting-points and remove items with a smaller t to their previous ones (works on I, III and IV).
  2. 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:

  1. When should I use the first and when the second approach (I can't see it)?
  2. Is there an easier way?

1 Answer 1


I solved it myself. Here is a result:

enter image description here

The example is out of this post: here

  • 1
    $\begingroup$ It would be great to have a summary of what made the difference and how it helped. $\endgroup$ Commented Mar 19, 2017 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.