0
$\begingroup$

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...

  • 0
    I really don't understand this question. It looks like lhf does, and if you are happy with his/her/their answer, great. But if not, then please try to explain what exactly it is that you want.2011-04-26

1 Answers 1

3

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.