Voronoi diagram in the Cartesian plane

INPUT:

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

pad := padding (some number)

---

ALGORITHM:

n := number of sites

x_l := minimum x-coordinate in sites (left)
x_r := maximum x-coordinate in sites (right)
y_t := maximum y-coordinate in sites (top)
y_b := minimum y-coordinate in sites (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 i in {0, 1, ..., n-1} do:
    cell := Box

    site := sites[i]

    for each j in {0, 1, ..., n-1} do:
        if i = j, continue with next iteration

        m := length(cell)  *number of vertices in cell*

        new_cell := {}

        next := sites[j]

        bisector := two_points_bisector(site, next)   *perpendicular bisector of site and next*

        for each k in {0, 1, ..., m-1} do:
            A := cell[k]
            B := cell[(k+1) mod m]

            egde := segment(A, B)

            if bisector intersects edge, then:
                t := intersection(edge, bisector)

                if t = B, then:
                    new_cell := {B, cell[(k+2) mod m]}

                    first_intersection_index := (k+2) mod m

                otherwise:
                    new_cell := {t, B}

                    first_intersection_index := (k+1) mod m

                finish loop


        if new_cell = {}, then:
            new_cell := cell

        otherwise:
            for each k in {first_intersection_index, first_intersection_index+1, ..., m-1} do:
                A := cell[k]
                B := cell[(k+1) mod m]

                egde := segment(A, B)

                if bisector intersects edge, then:
                    u := intersection(edge, bisector)

                    new_cell ∪ {u}  *add u to new_cell*

                    second_intersection_index := k+1;

                    finish loop

                otherwise:
                    new_cell ∪ {B}  *add B to new_cell*


            if site is not in new_cell, then:
                new_cell := {u}

                while second_intersection_index mod m ≠ first_intersection_index do:
                    v := cell[second_intersection_index mod m]

                    new_cell ∪ {v}  *add v to new_cell*

                    second_intersection_index := second_intersection_index + 1

                new_cell ∪ {t}  *add t to new_cell*

        cell = new_cell

    cells ∪ {cell}  *add cell to cells*

---

OUTPUT:

cells