yatoom / foronoi Goto Github PK

I think there is an issue with the finishing step, namely the finish_edges function.
The following code shows a missing edge (P3/P1) which is removed in finish_edges. Diving in, it seems like an issue with _get_intersection_point.

from foronoi import Voronoi, Polygon

good = [(262, 90), (188, 204), (521, 360), (541, 329), (501, 154)]
bad =   [(262, 90), (188, 204), (521, 360), (541, 329), (500, 154)]  # last site differs by (1, 0) from the above
polygon = Polygon([(0, 720), (1280, 720), (1280, 0), (0, 0)])
v_good = Voronoi(polygon)
v_good.create_diagram(points=good)
v_bad = Voronoi(polygon)
v_bad.create_diagram(points=bad)

Here are the diagrams (bad to the left, good to the right)

I've tried and changed the _get_intersection_point into:

    def _get_intersection_point(self, orig, end):
        p = self.points + [self.points[0]]
        points = []

        point = None

        for i in range(0, len(p) - 1):
            intersection_point = Algebra.get_intersection(orig, end, p[i], p[i + 1])
            if intersection_point:
                points.append(intersection_point)

        if len(points) == 0:
            point = None
        elif len(points) == 1:  # this is the actual change
            point = points[0]
        else:
            max_distance = Algebra.distance(orig, end)

            # Find the intersection point that is furthest away from the start
            if points:
                distances = [Algebra.distance(orig, p) for p in points]
                distances = [i for i in distances if i <= max_distance]
                if distances:
                    point = points[np.argmax(distances)]

        return point

This change solves the above case, without breaking any tests.
@Yatoom Could you please take a look? Thanks for the lib btw!

self.beach_line: SmartNode = None
^
SyntaxError: invalid syntax

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)]

I am evaluating several voronoi libraries to be used in a Freecad add-on I am working on for generating frame structures based on voronoi patterns. Very early stage now, so far just flat surfaces, later to be mapped onto any surfaces hopefully. Anyway, your library looks like a very good fit for my needs, but I have some questions and a minor issue.

For my use case I need to get for each vertex every edge connected to that vertex. By looking at the examples and the code I did not find any straightforward way to do this. Is there an easy way to get those edges ? Otherwise I can scan all edges for every vertex, but that is very inefficient.

One minor issue I have: to make installation of my addon easy, I don't want any dependencies so I pack all sources into the addon. voronoi has some dependencies for the visualization (which i do not need). So I have to comment out the visualization import statements in alogrithm.py. Is there a better way to use barebone voronoi without visualization and its dependencies ?

And one last question: the way I access edges for drawing lines along them is just taken from the original visualization/visual.py:

...
v = Voronoi(bounding_poly)
v.create_diagram(points=points)
for edge in v.edges:
        y = -1000
        start = edge.get_origin(y, bounding_poly.max_y)
        end = edge.twin.get_origin(y, bounding_poly.max_y)

I do not fully understand (yet) what this does, but it provides the start and endpoint for the lines I am drawing. However the hardcoded y = -1000 looks a bit scary to me. So if the recommended way to iterate through all edges for line drawing looks different, please let me know.

And thanks for providing this great software

Hiya, lovely package.

Everything works nicely for my use-case, except where I try to define a 'heavily' concave polygon bounding box. The issue is that the input Polygon appears to be clockwise ordered after input: '_order_points' and a convex polygon bounding box seems to be assumed elsewhere too.

This is quite easy to see with a slight adjustment to the Quick Start example:

import foronoi

points = [(2.5, 2.5), (4, 7.5), (7.5, 2.5), (6, 7.5), (4, 4), (3, 3), (6, 3)]

poly_nodes = [(2.5, 10), (5, 10), (10, 5), (10, 2.5), (5, 0), (2.5, 0), (0, 2.5), (0, 5)]
poly_nodes.insert(3, (4, 3))

v = foronoi.Voronoi(foronoi.Polygon(poly_nodes))

v.create_diagram(points=points)
foronoi.Visualizer(v).plot_sites().plot_edges(show_labels=False).plot_vertices().show()

Is it possible to generalize this to allow for a Polygon with pre-ordered vertices (in any manner)? Additionally, not all of the interior regions appear to be clipped to the boundary box.

Cheers!

Hey,

Great library, saved me a lot of headache trying to implement Lloyd's algorithm.
While implementing it, I ran into a quite severe issue though. While I iterate through the relaxation, I create a new Voronoi object every step, and if I use a global variable as the bounding region parameter, I inherit points from the edge from my previous iteration. So if I use a global variable at initialization, after the 1st iteration I get an increased number of vertices in my Voronoi sites.

As an example, see the code below:

from foronoi import Voronoi, Polygon, Visualizer, VoronoiObserver
import numpy as np

DIM_X = 10
DIM_Y = 10
N_of_P = 5
BBOX = Polygon([(0,0), (DIM_X,0), (0,DIM_Y), (DIM_X, DIM_Y)])
ITERATION = 10

def initialize_voronoi(n):
    rng = np.random.default_rng()
    numbers = rng.choice(DIM_X*DIM_Y, size=n, replace=False)
    points = []
    for number in numbers:
        y = number//DIM_X
        x = number%DIM_X
        points.append((x,y))
    return points

def create_foronoi(points):
    v = Voronoi(BBOX)
    v.create_diagram(points=points)
    return v

for i in range(ITERATION):
    points = initialize_voronoi(N_of_P)
    vor = create_foronoi(points)
    acc = 0
    for site in vor.sites:
        acc += len(site.vertices())
    print(f"{i}.: {acc}")
    Visualizer(vor, canvas_offset=1)\
        .plot_sites(show_labels=True)\
        .plot_edges(show_labels=True)\
        .plot_vertices()\
        .plot_border_to_site()\
        .show()

If at line 21 you change Voronoi(BBOX) to Voronoi(Polygon([(0,0), (DIM_X,0), (0,DIM_Y), (DIM_X, DIM_Y)])) it works perfectly.

Hi, I was trying out this Polygon-bounded Voronoi which is pretty cool but I run into issues from time to time as the algorithm does not seem to find Voronoi polygons for some of the points in the data (points that are within the bounding polygon).

Below is a reproducible example:

import numpy as np
from voronoi import Voronoi, Polygon

# These points were initially taken at random with np.random.rand
pts = [
    (0.17094288, 0.96789158),
    (0.55449063, 0.72159817),
    (0.94036409, 0.82856818),
]
# A square bounding box
polygon = Polygon([
    (0., 0.),
    (0., 1.),
    (1., 1.),
    (1., 0.),
])
# Initialise the voronoi object
v = Voronoi(polygon)
# Create the diagram
v.create_diagram(points=pts, vis_steps=False, verbose=False, vis_result=False, vis_tree=False)

# Print 
for i, pt in enumerate(v.points):
    print(i, pt.get_coordinates())
# Notice that in the output, the first two polygons are the same (with permutation):
# 0 [(0.685, 1.0), (0.962, 0.0), (0.0, 0.0), (0.0, 0.28), (0.462, 1.0)]
# 1 [(0.0, 0.28), (0.462, 1.0), (0.685, 1.0), (0.962, 0.0), (0.0, 0.0)]
# 2 [(0.962, 0.0), (0.685, 1.0), (1.0, 1.0), (1.0, 0.0)]

And if I try to plot them I get the following:

When point number is too large (around 30) Algorithm stops workin, and i can see this error

Traceback (most recent call last):
  File "VoronoiGraph.py", line 206, in <module>
    v.testVoronoi()
  File "VoronoiGraph.py", line 184, in testVoronoi
    v.create_diagram(points=points, vis_steps=False,
  File "/usr/local/lib/python3.8/dist-packages/voronoi-0.9-py3.8.egg/voronoi/algorithm.py", line 99, in create_diagram
  File "/usr/local/lib/python3.8/dist-packages/voronoi-0.9-py3.8.egg/voronoi/algorithm.py", line 271, in handle_circle_event
AttributeError: 'NoneType' object has no attribute 'edge'

After limiting the number of points graph is computed properly

Hi, I have an issue when trying to use get_coordinate() as it returns None for some of the set of points that I use. To reproduce the problem, here is the code that I use

points = [(3.45, 3.66), (6.0, 4.54), (7.82, 5.35), (5.65, 3.09), (1.99, 4.66)]
The_grid = Polygon([
    (0, 0),
    (0, 6),
    (9, 0),
    (9, 6)
])
v = Voronoi(The_grid)
v.create_diagram(points=points, vis_steps=False, verbose=False, vis_result=True, vis_tree=True)
points = v.points
points[2].get_coordinates()

I don't understand why the first_edge attribute present a Nonetype object in next.

I am trying to get all the vertices for each polygon formed by the Voronoi tesselation
Thank you for your help.