check whether a point is visible from a face of a 2d convex hull

1
votes

I am trying to implement the Bowyer-Watson algorithm for generating a Delaunay Triangulation of a set of points in a plane. The algorithm assumes a presence of a bounding super-triangle, but some alternatives like maintaining the convex hull of the set of points have also been mentioned.

Thus, when we decide to produce a delaunay triangulation of points by assuming a convex hull in an incremental algorithm, if a point lies outside the convex hull, we should draw vertices from the point to all the vertices on the convex hull which comprise the faces of the hull from which the point is visible.

I was wondering how could I approach this problem? Should I initially generate a convex hull of all the points or like in the incremental approach where points are added one at a time, should i maintain a convex hull in the form of a DCEL?

EDIT: In the image above, if I have the point P which is outside the convex hull of a set of points in a plane, I need to calculate the edges of the hull from which the point is visible. [The green edge of the hull] image above

I hope the image helps in clarifying the question.

Thanks in advance

1
computational-geometrydelaunayconvex-hull
Are you doing this as an exercise or do you plan to really use it? I ask the question because there already exists Delaunay Triangulation implementations. – sloriot
I am doing this as an exercise since I need to compare my implementation of the Delaunay Triangulation against the existing ones – chaitanya
I started to compose an answer, but then I realized I don't know what you are asking. What is "this problem" that you are wondering how to approach? – Joseph O'Rourke
The problem is suppose I have a convex hull of pts P in a plane CH(p) and I have maintained it as a doubly-connected edge list, thus I know all the vertices,edges and faces of the convex hull. Now, say a point q lies outside the convex hull, I want to obtain all the edges of the convex hull from which the point is visible – chaitanya

1 Answers

1
votes

The edges that see P are those that form a clockwise triangle with P when the hull is traversed counterclockwise (compute the signed area).