VoronoiDiagram_Lectures

Lecture Link

https://www.youtube.com/watch?v=Pn19deUBsM8&t=13s

The Post-Office Problem

https://link.springer.com/chapter/10.1007%2F3-540-10291-4_1

http://blog.ivank.net/voronoi-diagram-in-javascript.html

http://paperjs.org/examples/voronoi/

https://shaneosullivan.wordpress.com/2011/03/22/sweep-line-voronoi-algorithm-in-javascript/

https://jacquesheunis.com/post/fortunes-algorithm/

http://blog.ivank.net/fortunes-algorithm-and-implementation.html

https://github.com/pvigier/FortuneAlgorithm

http://www.cs.uu.nl/geobook/

https://pvigier.github.io/2018/11/18/fortune-algorithm-details.html

TakeAwayFromPvigier’s blog

https://pvigier.github.io/2018/11/18/fortune-algorithm-details.html

pseudo-code from Pvigier’s Blog

add a site event in the event queue for each site
while the event queue is not empty
    pop the top event
    if the event is a site event
        insert a new arc in the beachline
        check for new circle events
    else
        create a vertex in the diagram
        remove the shrunk arc from the beachline
        delete invalidated events
        check for new circle events

• site event
• circle event

Diagram’s Data Structure

Double connected edge list(DCEL).

class VoronoiDiagram{
    public:
        //...
    private:
        std::vector<Site> mSite;
        std::vector<Face> mFace;
        std::list<Vertex> mVertices;
        std::list<HalfEdge> mHalfEdges;
}

The Site class represents an input point. Each site has an index, which is useful to query them, coordinates and a pointer to their cell(face):

struct Site{
    std::size_t index;
    Vector2 point;
    Face* face;
};

The vertices of the cells are represented by the Vertex class, they just have a cooridinates field:

struct Vertex{
    Vector2 point;
};

Here is the implementation of half-edges:

struct HalfEdge{
    Vertex* origin;
    Vertex* destination;
    HalfEdge* twin;
    Face* incidentFace;
    HalfEdge* prev;
    HalfEdge* next;
};

An edge in a Voronoi diagram is shared by two adjacent cells. In the DCEL data structure, we splite these edfes in two half-edges, one for each cell, and they are linked by the twin pointer.

Moreover, a hald-edge has an origin vertex and a desrination vertex.
The incidenetFace field points to the face to which the half-edge belongs to.

Finally, in DCEL, cells are implemented as a circular doubly linked list of half-edges where adjacent half-edges are linked together. Thus the prev and next fields points to the previous and next half-edges in the cell.

Finally, the Face class represents a cell and it just contains a pointer to its site and another to one of its half-edges. It does not matter which half-edge it is because a cell is a closed polygon. Thus we can access to all of its hald-edges by traversing the circular linked list.

struct Face{
    Site* site;
    HalfEdge* outerComponent;
};

Event Queue

The standard way to implement the event queue is to use a priority queue.

During the processing of site and circle events we may need to remove circle events from the queue because they are not valid anymore.

But most of the standard implementations of priority queues do not allow to remove an element which is not the top one. In particular that is the case for std::priority_queue.

There are two ways to tackle this problem.

1. The first and simplest one is to add a valid flag to true initially. Then instead of removing the circle event from the queue, we just set its flag to false. Finially, when we process the events in the main loop, if the valid flag of an event equals to false, we simply discard it and process the next one.
2. The second method which I adopted is not to use std::priority_queue. Instead, I implemented my own priority queue which supports removal of any element it contains. The implementation of such a queue is pretty straightforward. I choose this method because I find it makes the code for the algorithm clearer.

Beachline

If not implemented correctly there is no guarantee that the algorithm will run in O(log(n)). The key to reach this time complecity is to use a self-balancing tree.

In my implementation the beachline is still a tree, but all nodes represent an arc.

struct Arc{
    enum class Color{RED, BLACK};

    // Hierarchy
    Arc* parent;
    Arc* left;
    Arc* right;

    // Diagram
    VoronoiDiagram::Site* site;
    VoronoiDiagram::HalfEdge* leftHalfEdge;
    VoronoiDiagram::HalfEdge* rightHalfEdge;
    Event* event;
    // Optimizations
    Arc* prev;
    Arc* next;
    // Only for balancing
    Color color;
};

In Fortune’s algorithm we have no key, we only know that we want to insert an arc before or after another in the beachline. To do that, I create methods insertBefore and insertAfter:

void Beachline::insertBefore(Arc* x, Arc* y){
    // Find the right place
    if(isNil(x->left)){
        x->left = y;
        y->parent = x;
    }
    else{
        x->prev->right = y;
        y->parent = x->prev;
    }
    // Set the pointers
    y->prev = x->prev;
    if(!isNil(y->prev))
        y->prev->next = y;
    
    y->next = x;
    x->prev = y;

    // Balance the tree
    insertFixup(y);
}

Priority Queues

https://www.youtube.com/watch?v=wptevk0bshY

What is a Priority Queue

A priority queue is an Abstract Data Type(ADT) that operates similar to a normal queue excpet that each element has a certain priority. The priority of the elements in priority queue determin the order in which elements are removed from the PQ.

NOTE: Priority queues only supports comparable data.

What is a Heap?

A heap is a tree based DS that satifies the heap invariant(also called heap property):
If A is a parent node of B then A is ordered with repect to B for all nodes A, B in the heap.

• Max Heap
• Min Heap

Heaps must be trees.

When and where is a PQ used?

• Used in certain implementaitons of Dijkstra’s shortest Path algorithm.
• Anytime you need the dynamically fetch the next best or next worst element
• Used in Huffman coding (which is often used for lossless data compression).
• Best First Search(BFS) algorithms such as A* use PQs to continuously grab the next most promising node
• Used by minimum Spanning Tree(MST) algorithms

Complexity PQ with binary heap

• Binary Heap construction: O(n)
• Polling: O(log(n))
• Peeking: O(1)
• Adding: O(log(n))

Self balance Tree (AVL Tree)

https://www.youtube.com/watch?v=vRwi_UcZGjU

• Balance
• Rotation
• Implementation

Rebalancing threshold

pseudo-code from Jacquesheunis’ blog

https://jacquesheunis.com/post/fortunes-algorithm/

Fill the event queue with site events for each input site.
While the event queue still has items in it:
    If the next event on the queue is a site event:
        Add the new site to the beachline
    Otherwise it must be an edge-intersection event:
        Remove the squeezed cell from the beachline
Cleanup any remaining intermediate state

Voronoi Diagram - Computataional Geometry

Fortune’s Sweep

VoronoiDiagram(P are in R2)
Q : new PriorityQueue(P) // site events sortes by y-coord.
T : new BalancedBinarySearchTree() // sweep status(B)
D : new DCEL() // to-be Vor(P)

while not Q.empty() do
    p <- Q.ExtractMax()
    if p site event then
        HandleSiteEvent(p)
    else
        a <- arc on B that will disappear
        HandleCircleEvent(a)

treat remaining int. nodes of T(unbnd. edges of Vor(P))
return D

Handling Events

• HandleSiteEvent(point p)
  • Search in T for the arc a vertically above p. If a has pointer to circle event in Q, delete this event.
  • Split a into a0 and a2. Let a1 be the new arc of p
  • Add Vor-edges <q, p> and <p, q> to DECL
  • Check <., a0, a1> and <a1, a2, .> for circle events.
• HandleCircleEvent(arc a)
  • T.delete(a); update breakpts
  • Delete all circle events involving a from Q
  • Add Vor-vtx a_left and a_right