CODEWITHSUNDEEP
computational-geometrycgal
Natanael Ramos
Natanael Ramos

Reputation: 450

Computing visibility polygon from a point in the boundary

I'm using the CGAL library to compute Visibility Polygons from a point p within a simple polygon P, where p is in the boundary of P. I'm using the class "Simple_polygon_visibility_2" and when the visibility polygon is computed, the results seem to be wrong. I'm sending in the attachment both the polygon P and the resulting visibility polygon. In this example, I'm interested in finding the visibility polygon from the vertex labeled "7". As you can see, the resulting visibility polygon has the edge from "4" to "5" (and consequently, the triangle "7-4-5") which is not valid, since this triangle is not part of P.

I've read the paper from Joe and Simpson, and they mention:

"For a boundary viewpoint z, we orient the vertices of P in counterclockwise order and label them z, v_0, v_1, ..., v_{n-1}, v_n and z, where v_0 is the successor vertex of z and v_n is the predecessor vertex of z. We also assume that the coordinate system is translated and rotated so that z is at the origin and v_0 is on the positive x-axis"

I think that maybe this is the issue, because I'm not sure if CGAL's implementation tests whether the query point is on the boundary or not and if so, treats it as an especial case. If so, do I have to do this translation/rotation a priori?

polygon visibility

Upvotes: 2

Views: 303

Answers (1)

Natanael Ramos
Natanael Ramos

Reputation: 450

Actually, its was my mistake. Since the point is in the boundary, it does not belong to either the interior or exterior face (when the arrangement is a simple polygon). So instead of using this version of the "compute_visibility" method, I should use the one in which the half-edge containing the query point is the parameter. In this case, it works as expected.

Upvotes: 2

Related Questions