CODEWITHSUNDEEP
algorithmmathgeometry
user2818113
user2818113

Reputation: 53

How to find visibility of a polygon from a vertex v in a concave polygon

I'm working on an assignment 2d art gallery problem to find a minimum number of vertex guards. As part of solving the problem using genetic algorithms, I would need to find out the area of the polygon that is visible for a guard placed on a vertex.

The input is a polygon with known 2d (x,y) coordinates. Could you please help me know how to calculate the visibility of the guard(i.e what part of the polygon he could possibly see) placed on a vertex of the polygon?

Upvotes: 1

Views: 1029

Answers (1)

saastn
saastn

Reputation: 6015

This is a solution for finding visible area from an arbitrary point inside the polygon. You can change it to restrict point to polygon vertices: enter image description here

Step 1: Draw rays from guard toward each vertex and find intersection points with all edges of polygon.

Step 2: Check if ray crosses polygon (yellow) or just touches it (purple).

Step 3: Sort intersections on a ray by their distances from the guard and find closet cross point. Call all further points invisible (red) and closer ones visible (green).

Step 4: Now each edge of polygon is equivalent to one or multiple segments, each segment that its both end points are labeled as visible will be visible. Sum length of such segments.

Here is a more complicated sample:

enter image description here

And keep in mind that it is just a start and you can optimize it. Think about Niko's comment for first improvement.

Upvotes: 1

Related Questions