Duplicate points returned by get_coordinates()

[Penniman]

When I run v.create_diagram(points=points) with points = [(0.,0.), (1.,0.), (0.,1.), (1.,1.)] the graph looks okay, four quadrants that are nice and square, but the output of get_coordinates() returns duplicate points:

#!/usr/bin/env python3
from voronoi.algorithm import Algorithm
from voronoi import BoundingBox
import numpy as np

if __name__ == "__main__":
    polygon = BoundingBox(0, 1, 0, 1)

    # Initial Points
    points = [(0.,0.), (1.,0.), (0.,1.), (1.,1.)]

    v = Algorithm(polygon)
    v.create_diagram(points=points)

    for p in v.points:
        print(f"Point: {p} ({p.x}, {p.y});  Coordinates: {p.get_coordinates()}")

Notice the duplicated coordinate points for C and B:

Point: C (0.0, 0.0); Coordinates: [(0.0, 0.5), (0.5, 0.5), (0.5, 0.5), (0.5, 0.0), (0, 0)]
Point: D (1.0, 0.0); Coordinates: [(0.5, 0.5), (1.0, 0.5), (1, 0), (0.5, 0.0)]
Point: A (0.0, 1.0); Coordinates: [(0.5, 1.0), (0.5, 0.5), (0.0, 0.5), (0, 1)]
Point: B (1.0, 1.0); Coordinates: [(0.5, 0.5), (0.5, 1.0), (1, 1), (1.0, 0.5), (0.5, 0.5)]

[Yatoom]

Hi Penniman, thanks for reporting your issue. I will first explain why you get these results and then provide a possible fix.

Explanation
This is a result of the underlying algorithm. When the sweep line goes down and reaches the first two points, two arcs are inserted. When we reach the second two points, another two arcs are inserted. We then reach the following situation:

Here, two arcs are going to disappear at the exact same time. The algorithm is however going to handle this as two separate steps: first the left arc is going to disappear and so a point will be inserted there, and then we do the same for the right arc. So what we end up with is two points with the same coordinates and a zero-length edge.

(For more information:)

Possible fix
We could update the get_coordinates() to check for succeeding (and also first and last) points with the same coordinates, and exclude those from the result.

[Penniman]

Thank you, Yatoom. You provided an exceptional explanation.