CODEWITHSUNDEEP
algorithmjuliacomputational-geometryvoronoi
Luis.Alberto
Luis.Alberto

Reputation: 107

How do you find circle points in Fortune's algorithm?

I know that when your sweepline encounters three centers of your array, you have to check if there is something called "circle points". I understand that circle points are the poles of the circle that goes through the other 3 points, but my questions is, which is the efficient way to do this, because what you really want is the center of the circle which is the vertex of three Voronoi poligons, so what came to my head is to find the three mediatrices and the intersection of the three will be the center, but it seems to me that if I do that the algorithm will be mor closely to a brute force algorithm, I hope you could help me with this, thanks in advance EDIT: I think it's worth saying that I'm working on Julia, and that I've already done two brute force algorithms, one aproximate and one exact

Upvotes: 0

Views: 108

Answers (1)

Håkan
Håkan

Reputation: 154

There is a rather good and detailed description of this algorithm in this course book:

https://www.springer.com/gp/book/9783540779735

They explain how efficiency is obtained by adding pointers between the status tree and the parts of the diagram being constructed.

Maybe it can help. I have not implemented the algorithm myself.

Upvotes: 1

Related Questions