I am trying to implement my own voronoï in Unity3d ( in C# ) as I am not satisfied with the existing libs that I found ( they always tend to miss a piece of information on the output and / or tend to be very difficult to understand ).
I did a working implementation with a Delaunay triangulation but, as you might expect, it's no well suited for big diagramms.
I worked out most of the algorithm but I do not understand how I can efficiently know what is the parabola that the new site is going to intersect with.
The best method I found is intersecting all of the parabolas of the beach line and getting the intersection that has the highest Y coordinates ( in the case of the sweep line going from bottom to top ) but it's not very efficient as you end up with a small brute force in a loop.
I found 2 articles indicating that a binary tree is the best way to do so ( here and here ) but they don't not explain anything be it reason or implementation.
Do you know of a way that does not require a brute force ? Should I find no better solutions I will use it but it's clearly not the best way to use this algorithm.
