I'm researching this paper and attempting to implement some of the algorithms presented. I'm currently at the first algorithm, which presents a way to triangulate a set of points in a plane in quadratic time without using any work-space memory.

To save you from having to read everything about the algorithm, here's the main idea:

We traverse the points in a non-decreasing order of the x-coordinate. In each step we consider the current point q_i, and the point before u. We do a gift wrapping march from the point u and consider the edges we find along the way. For each edge we check whether it's visible from the point q_i and if it is we add a triangle made from q_i and that edge, we repeat that process until encountering the first non-visible edge. You can see the pseudocode for it on page 5.

The step that I'm not getting here is the one I've bolded, that is checking whether an edge is visible from the point q_i. How would you perform this check in linear time? Would you somehow have to iterate through all the triangles previously added and check whether any of their edges lies in between? How would this be done while maintaining the no extra memory restriction?

Thanks in advance.

CodePudding user response：

Working counterclockwise from q_i−1 (which is always visible from q_i), the next hull edge a→b is visible if and only if the triangle q_iab is clockwise, which you can check with a cross product. Working clockwise, counterclockwise.