

Hello all,
My name is Natanael Ramos. 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 send in the attachment both the polygon P (poly.pdf) and the resulting visibility polygon (vis.pdf). 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 "745") 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_{n1}, 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 xaxis"
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?
Best Regards,
Natanael Ramos


Hi Natanel,
It does look like a bug. Please attach a simple program that reproduces this issue. To do that, you first need to (have an account and) sign in to GitHub
Regards, Efi
____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/('_(/ _/
Hello all,
My name is Natanael Ramos. 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 send in the attachment both the polygon P (poly.pdf) and the resulting visibility polygon (vis.pdf). 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 "745") 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_{n1}, 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 xaxis"
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?
Best Regards,
Natanael Ramos


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 halfedge containing the query point is the parameter. In this case, it works as expected.
Thanks for the response. Hi Natanel,
It does look like a bug. Please attach a simple program that reproduces this issue. To do that, you first need to (have an account and) sign in to GitHub
Regards, Efi
____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/('_(/ _/
Hello all,
My name is Natanael Ramos. 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 send in the attachment both the polygon P (poly.pdf) and the resulting visibility polygon (vis.pdf). 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 "745") 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_{n1}, 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 xaxis"
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?
Best Regards,
Natanael Ramos

