Algorithm¶

class foronoi.algorithm.Algorithm(bounding_poly: Optional[foronoi.graph.polygon.Polygon] = None, remove_zero_length_edges=True)¶

A Python implementation of Fortune’s algorithm based on the description of “Computational Geometry: Algorithms and Applications” by de Berg et al.

Parameters

bounding_poly (Polygon) – The bounding box or bounding polygon around the voronoi diagram
remove_zero_length_edges (bool) – Removes zero length edges and combines vertices with the same location into one

bounding_poly¶

The bounding box (or polygon) around the edge

Type: Polygon

event_queue¶

Event queue for upcoming site and circle events

Type: PriorityQueue

status_tree¶

The status structure is a data structure that stores the relevant situation at the current position of the sweep line. This attribute points to the root of the balanced binary search tree that functions as a status structure which represents the beach line as a balanced binary search tree.

Type: Node

sweep_line¶

The y-coordinate

Type: Decimal

arcs¶

List of arcs

Type: list(foronoi.nodes.Arc)

sites¶

List of points

Type: list(foronoi.graph.Point)

vertices¶

List of vertices

Type: list(foronoi.graph.Vertex)

clean_up_zero_length_edges()¶: Removes zero length edges and vertices with the same coordinate that are produced when two site-events happen at the same time.

create_diagram(points: list)¶

Create the Voronoi diagram.

The overall structure of the algorithm is as follows.

Initialize the event queue event_queue with all site events, initialize an empty status structure status_tree and an empty doubly-connected edge list D.
while event_queue is not empty.
do Remove the event with largest y-coordinate from event_queue.
if the event is a site event, occurring at site point
then handle_site_event()
else handle_circle_event()
The internal nodes still present in status_tree correspond to the half-infinite edges of the Voronoi diagram. Compute a bounding box (or polygon) that contains all vertices of bounding box by updating the doubly-connected edge list appropriately.
If remove_zero_length_edges is true.
Call clean_up_zero_length_edges() which removes zero length edges and combines vertices with the same location into one.

Parameters: points (list(Point)) – A set of point sites in the plane.
Returns
Return type: Output. The Voronoi diagram Vor(P) given inside a bounding box in a doublyconnected edge list D.

handle_circle_event(event: foronoi.events.circle_event.CircleEvent)¶

Handle a circle event.

Delete the leaf γ that represents the disappearing arc α from status_tree. Update the tuples representing the breakpoints at the internal nodes. Perform rebalancing operations on status_tree if necessary. Delete all circle events involving α from event_queue; these can be found using the pointers from the predecessor and the successor of γ in status_tree. (The circle event where α is the middle arc is currently being handled, and has already been deleted from event_queue.)
Add the center of the circle causing the event as a vertex record to the doubly-connected edge list D storing the Voronoi diagram under construction. Create two half-edge records corresponding to the new breakpoint of the beach line. Set the pointers between them appropriately. Attach the three new records to the half-edge records that end at the vertex.
Check the new triple of consecutive arcs that has the former left neighbor of α as its middle arc to see if the two breakpoints of the triple converge. If so, insert the corresponding circle event into event_queue. and set pointers between the new circle event in event_queue and the corresponding leaf of status_tree. Do the same for the triple where the former right neighbor is the middle arc.

Parameters: event –

handle_site_event(event: foronoi.events.site_event.SiteEvent)¶

Handle a site event.

Let point_i = event.point. If status_tree is empty, insert point_i into it (so that status_tree consists of a single leaf storing point_i) and return. Otherwise, continue with steps 2– 5.
Search in status_tree for the arc α vertically above point_i. If the leaf representing α has a pointer to a circle event in event_queue, then this circle event is a false alarm and it must be deleted from status_tree.
Replace the leaf of status_tree that represents α with a subtree having three leaves. The middle leaf stores the new site point_i and the other two leaves store the site point_j that was originally stored with α. Store the breakpoints (point_j, point_i) and (point_i, point_j) representing the new breakpoints at the two new internal nodes. Perform rebalancing operations on status_tree if necessary.
Create new half-edge records in the Voronoi diagram structure for the edge separating the faces for point_i and point_j, which will be traced out by the two new breakpoints.
Check the triple of consecutive arcs where the new arc for pi is the left arc to see if the breakpoints converge. If so, insert the circle event into status_tree and add pointers between the node in status_tree and the node in event_queue. Do the same for the triple where the new arc is the right arc.

Parameters: event (SiteEvent) – The site event to handle.

initialize(points)¶

Initialize the event queue event_queue with all site events.

Parameters: points (list(Point)) – The list of cell points to initialize
Returns: event_queue – Event queue for upcoming site and circle events
Return type: PriorityQueue