1

I'm working on a small application with the P5 library that allow a user to click on a canvas to create points and build a polygon and I want to compute the visibility graph of that polygon. How can I implement an algorithm that can tell me if 2 vertices are visible in this polygon ? I don't know how to check if a line between these 2 vertices is inside the polygon. thank you.

user1241025
  • 49
  • 4

1 Answers1

0

Let a and b be two vertices. First check that the segment ab is locally inside at a, and at b. I.e., it falls within the cone determined by the vertices before and after a, and b. If so, then you need to intersect the segment ab with each edge of the polygon (except those incident to a and to b, because you just checked those).

For this you need segment-segment intersection code. You can find this all over the web, including in Chapter 7 of Computational Geometry in C, and this description by Martin Thoma.

Joseph O'Rourke
  • 4,346
  • 16
  • 25
  • Thank you for your response. Do you have a link that could help me to implement the part where I need to determine if the segment is locally inside at a and b. I have a problem in the case where the angle formed by the incident vertices is obtuse. – user1241025 Aug 15 '17 at 08:02
  • You want one vertex to the left of *ab* and one vertex to the right. So it can be checked with two calls to a LeftOf( ) function that takes three points as input and returns true iff the 1st pt is left of the line determined by the 2nd & 3rd. This is essentially the [signed area of a triangle](http://mathworld.wolfram.com/TriangleArea.html). – Joseph O'Rourke Aug 15 '17 at 10:43
  • Thank you for your help. – user1241025 Aug 15 '17 at 11:21