pythoncomputer-visiongeometry

Using Python to get unblocked area


I have a rather complicated problem. Suppose I have the shape below. You can think of the red dot as a person and the pointy shape inside the big polygon as an obstacle. My goal is to compute the total unblocked vision of the person inside the big polygon, which is the area of the polygon minus the red shaded area.

I want to write a function that takes in the coordinates of the person, the coordinates of the ordered vertices of the obstacle(s) and those of the ordered vertices of the big polygon, and returns the area of the unblocked vision.

I have tried multiple things, and I'm aware of the shoelace algorithm, but the only way that I can come up with is through monte carlo. Can I get a hint on a more intelligent and efficient way to compute the area in a closed-form way?

enter image description here


Solution

  • I think your problem is solved by finding the "Visibility polygon". https://en.wikipedia.org/wiki/Visibility_polygon

    You can use https://karlobermeyer.github.io/VisiLibity1/ library to compute the visibility area.