zigui-ps / voronoidiagram Goto Github PK
View Code? Open in Web Editor NEWFortune's Algorithm O(N log N) for ICPC
License: MIT License
Fortune's Algorithm O(N log N) for ICPC
License: MIT License
Hello, zigui !
I am a new learner to computational geometry from China and I am trying to realize of VoronoiDiagram in C++.
I was quite interested at the first time when I found your code because you just coded with 150 lines and used splay tree instead of AVL. But I had a bit confused about some details of your code. Here are my question:
(1) the underlying principle of function line_intersection(a, b, u, v) in VoronoiDiagram.cpp : Is this function used to calculate the intersection point of two line (one is defined by point a and point b while the other is defined by point u and point v) ? I tested line_intersection({1,0}, {0,1}, {0,0}, {1,1}) and got a result point{1,1}. It obvious that the intersection should be {0.5,0.5}. Could you please explain the meaning of each argument and the principle of this function ?
(2) the principle of dealing with the false alarm in Fortune 's algorithm : As mentioned in the original Fortune 's algorithm, it exists 2 situation of false alarm. But I couldn't find the obvious dealing process of these false alarms in your code. I guessed you dealt with them in function get_event() with two if-return lines, but I couldn't understand these two lines well. By the way, I am not sure whether my supposal is correct . Could you please tell me how and where you deal with these false alarms ?
(3) the meaning of "end" field of node structure : I couldn't understand the end field here and why it is set as "size of edge * 2". Could you please explain it specifically ?
Thank you!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.