Naive pseudocode to create Voronoi cells (short version).

voronoi-short.md

Voronoi diagram in the Cartesian plane

INPUT:

S := {(x₀, y₀), (x₁, y₁), ..., (x_n-1, y_n-1)}

pad := padding (some number)

---

ALGORITHM:

x_l := minimum x-coordinate in S (left)
x_r := maximum x-coordinate in S (right)
y_t := maximum y-coordinate in S (top)
y_b := minimum y-coordinate in S (bottom)

Box := {(x_l-pad,y_t+pad), (x_r+pad,y_t+pad), (x_r+pad,y_b-pad), (x_l-pad,y_b-pad)}

cells := {}

for each point p in S, do:
    cell := Box

    for each point q in S, except p, do:
        B = bisector(p, q)   *perpendicular bisector of p and q*

        if B intersects cell twice, then:
            Let t1 be the first intersection
            Let t2 be the second intersection
            Let xi be the vertex of cell after the first intersection
            Let xj be the vertex of cell after the second intersection

            new_cell := {}      *empty set*
            new_cell ∪ {t1}     *add first intersection*
            new_cell ∪ {xi}     *add vertex xi*
            new_cell ∪ {xi+1}   *add vertex xi+1*
            ⋮
            new_cell ∪ {t2}     *add second intersection*

            if p is not in new_cell, then:
                new_cell := {}
                new_cell ∪ {t2}     *add second intersection*
                new_cell ∪ {xj}     *add vertex xj*
                new_cell ∪ {xj+1}   *add vertex xj+1*
                ⋮
                new_cell ∪ {t1}     *add first intersection*

            cell := new_cell

    cells ∪ {cell}   *add cell to cells*

---

OUTPUT:

cells