# 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
`sites`

List of points

Type
`vertices`

List of vertices

Type
`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.

1. 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.

2. while event_queue is not empty.

3. do Remove the event with largest y-coordinate from event_queue.

4.   if the event is a site event, occurring at site point

5. 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.

6. If remove_zero_length_edges is true.

7.  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.

1. 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`.)

2. 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.

3. 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.

1. 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.

2. 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`.

3. 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.

4. 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.

5. 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