Computing visibility polygon from a point in the boundary

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Computing visibility polygon from a point in the boundary

Natanael Ramos
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 "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?

Best Regards,

Natanael Ramos

polygon.pdf (22K) Download Attachment
vis.pdf (22K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Computing visibility polygon from a point in the boundary

Efi Fogel
Hi Natanel,

It does look like a bug.
Please attach a simple program that reproduces this issue.
Alternatively, you can go ahead an create an issue at https://github.com/CGAL/cgal/issues
To do that, you first need to (have an account and) sign in to GitHub

Regards,
Efi
   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/




On Mon, 16 Sep 2019 at 22:17, Natanael Ramos <[hidden email]> wrote:
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 "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?

Best Regards,

Natanael Ramos
Reply | Threaded
Open this post in threaded view
|

Re: Computing visibility polygon from a point in the boundary

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 half-edge containing the query point is the parameter. In this case, it works as expected.

Thanks for the response.

On Tue, Sep 17, 2019 at 1:08 PM Efi Fogel <[hidden email]> wrote:
Hi Natanel,

It does look like a bug.
Please attach a simple program that reproduces this issue.
Alternatively, you can go ahead an create an issue at https://github.com/CGAL/cgal/issues
To do that, you first need to (have an account and) sign in to GitHub

Regards,
Efi
   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/




On Mon, 16 Sep 2019 at 22:17, Natanael Ramos <[hidden email]> wrote:
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 "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?

Best Regards,

Natanael Ramos