leosix
commented
10 months ago 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!
I seem to know the answer : the argument b ( or d ) refer to the direction vector of each line passes through a ( or b ) .
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!