<p>Is there any open-source implementation of n*log(n) visibility graph construction algorithm?</p>

<p>I'm trying to understand <a href="http://www-lb.cs.umd.edu/~mount/Papers/sicomp91-visib.pdf" rel="noreferrer">S. K. GHOSH and D. M. MOUNT</a> sweep line algorithm, but it's known for having very hard implementation. It would be great if I saw at least some implementation, in any programming language. Or in pseudo-code.</p>

CC BY-SA 4.0
2018-06-03T09:44:38.217Z
I looking for this type of algorithm. Have you found any implementation or replacent??
user43968
CC BY-SA 4.0
2018-06-04T11:49:37.733Z
@user43968, well, unfortunately none of them are simple. Currently I'm trying to implement this one with continious dijkstra approach. It's not nlog(n), but it's subquadratic, which is not bad too https://dl.acm.org/citation.cfm?id=161156.
Ibraim Ganiev
<algorithm><computational-geometry><2d><scene-graph>
Is there any open-source implementation of n*log(n) visibility graph construction algorithm?
Ibraim Ganiev
# Is there any open-source implementation of n*log(n) visibility graph construction algorithm?

(Asked by: username_0 on 2017-05-11)

Is there any open-source implementation of n\*log(n) visibility graph construction algorithm?

I'm trying to understand [S. K. GHOSH and D. M. MOUNT](http://www-lb.cs.umd.edu/~mount/Papers/sicomp91-visib.pdf) sweep line algorithm, but it's known for having very hard implementation. It would be great if I saw at least some implementation, in any programming language. Or in pseudo-code.

**Tags:** algorithm, computational-geometry, 2d, scene-graph

> **Comments:**
> **username_1**: I looking for this type of algorithm. Have you found any implementation or replacent??  
> **username_0**: @username_1, well, unfortunately none of them are simple. Currently I'm trying to implement this one with continious dijkstra approach. It's not nlog(n), but it's subquadratic, which is not bad too https://dl.acm.org/citation.cfm?id=161156.  

---

## 0 answers

