How find all inner diagonals of the non-convex and simple polygon in O(N*N) and better. My solution consisting of two steps
A] throw all intersecting diagonals: test if diagonal intersects any edge of the polygon
b] test, if diagonal is inner/or outer
was slow... Is there any faster solution? Thanks fof your help...
See Finding the visibility graph of a simple polygon in time proportional to its size for an output-sensitive algorithm. However, the author says that the algorithm may be difficult to implement and suggests a simpler algorithm that runs in time $O(m+\log n)$, where $m$ is the number of diagonals and $n$ is the number of vertices.