Fortune's algorithm
Páginas: 2 (439 palabras)
Publicado: 25 de enero de 2012
Fortune’s algorithm
This algorithm is based on “sweeping” the plane. There is a line L moving from bottom to the top, which proceeds each point, which it passes. Let’s think, which points under Lalready belong to Voronoi diagram.
If the point x has the same distance to a and b (all 3 lies under a sweep line), this point x doesn’t have to be in diagram, because there can be next site rightabove the sweep line, which is closer. We can decide a Voronoi diagram only for points, which are closer to any site under the line than to the very line L. These points lie under a parabola, site a isits focus point and the sweep line is its directrix, due the definition of a parabola.
The border, which says, for which points we can draw a diagram, is made of an arcs of parabolas. We call it abeachline. Intersections of these parabola’s arcs have the same distance to some 2 sites (2 foci of parabolas) and to the sweep line. Thus, when moving a sweepline upwards, these intersections draw thediagram. The beachline is a sequence of arcs p and intersections x, which we can call “edges”, because they draw the edge of the Voronoi graph.
Beachline p0,x0,p1,x1,…,xn−1,pn .
The beachlinechanges while the sweepline moves upwards. It can be changed only at 2 occasions:
• Site event – the sweepline passes a new site, which adds a new parabola into the beachline. The beachline is dividedinto 2 arcs and 2 edges (2 parts of final edge) start to come in the opposite directions under this new site. Thus, the parabola pi is replaced by a sequence pi,xi,pi+1,xi+1,pi+2, where pi a pi+2 havea focus of a previous parabola and pi+1 has it’s focus in a newly added site.
• Circle event – an arc disappears, two neighbor arcs “squeeze” it. A new edge between neighbors is started. Thus, asequence xi−1,pi,xi is replaced by a new edge xi. A place, at which arc disappears and new edge begins, is in the same distance to all 3 focii (it’s focus and neighbors’ focii). Thus, it is the...
This algorithm is based on “sweeping” the plane. There is a line L moving from bottom to the top, which proceeds each point, which it passes. Let’s think, which points under Lalready belong to Voronoi diagram.
If the point x has the same distance to a and b (all 3 lies under a sweep line), this point x doesn’t have to be in diagram, because there can be next site rightabove the sweep line, which is closer. We can decide a Voronoi diagram only for points, which are closer to any site under the line than to the very line L. These points lie under a parabola, site a isits focus point and the sweep line is its directrix, due the definition of a parabola.
The border, which says, for which points we can draw a diagram, is made of an arcs of parabolas. We call it abeachline. Intersections of these parabola’s arcs have the same distance to some 2 sites (2 foci of parabolas) and to the sweep line. Thus, when moving a sweepline upwards, these intersections draw thediagram. The beachline is a sequence of arcs p and intersections x, which we can call “edges”, because they draw the edge of the Voronoi graph.
Beachline p0,x0,p1,x1,…,xn−1,pn .
The beachlinechanges while the sweepline moves upwards. It can be changed only at 2 occasions:
• Site event – the sweepline passes a new site, which adds a new parabola into the beachline. The beachline is dividedinto 2 arcs and 2 edges (2 parts of final edge) start to come in the opposite directions under this new site. Thus, the parabola pi is replaced by a sequence pi,xi,pi+1,xi+1,pi+2, where pi a pi+2 havea focus of a previous parabola and pi+1 has it’s focus in a newly added site.
• Circle event – an arc disappears, two neighbor arcs “squeeze” it. A new edge between neighbors is started. Thus, asequence xi−1,pi,xi is replaced by a new edge xi. A place, at which arc disappears and new edge begins, is in the same distance to all 3 focii (it’s focus and neighbors’ focii). Thus, it is the...
Leer documento completo
Regístrate para leer el documento completo.