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.
I will have to compute all of the parabolas of the beachline as seen here to try and find the biggest value, witch should be the one with witch the new site event intersects. I must now find a way to do so efficiently as I still do not understand how to implement that binary tree