:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » »
 




  2.1 Point event



The point event is handled when a new parabolic arc appears on parabolic front. This event happens exactly when a new arc appears on the parabolic front, or more precise, when the scanning line encounteres a point pi from set P. Then, the scanning plane hits the coin defined above point pi for the first time. Because the coin and the scanning plane are slanted for the same angle, the intersection between them appears as a line on the coin surface. This line is actually a half-edge, but if it is projected onto xy-plane we can consider it a degenerated parabola with zero width. This degenerated parabola starts to open as the scanning plane slides over the space. When a new arc comes across, it splits the existed arc into two parts and becomes a new member of the parabolic front (Figure 4).

Figure 4: When point event is encountered a new arc appears on the parabolic front

What happens with Voronoi diagram when a point event is encountered? Lets remember, that a joint point of two arcs on parabolic front describes the Voronoi edge.