search

trylock / visibility

Simple sweep line visibility polygon algorithm implementation
MIT License
95 stars 15 forks source link

References for the algorithm #1

Open davidglavas opened 6 years ago

davidglavas commented 6 years ago

Do you have any source(s) which contains a detailed description and analysis of the algorithm?

trylock commented 6 years ago

I couldn't find any good description and analysis and my assignment was not written in English.

Fortunately, it is an angular sweep algorithm. Better yet, all events are known at the beginning which makes the analysis even simpler. I think, if you are familiar with sweep line algorithms, the main idea should be sufficient (at least it was for me and I'm not exactly the brightest). The main idea is that we start with a ray having observer's position as its origin. The ray rotates around this point and as it hits the first obstacle, it traces the visibility polygon.

Hopefully this helps somehow. If not, I might be able to write a more detailed description in future but I'm pretty busy at the moment.