Some user questions about foronoi HOT 15 OPEN

Hi @rsaccon, sounds like a cool project 😄

• The vertices (v.vertices) have an attribute connected_edges that contains a list of all the half-edges that have their origin at this vertex. Hope that helps.
• I think the parameters for edge.get_origin() can be removed or None. If I remember correctly, they are only used for intermediary steps, where the Voronoi diagram is not fully complete. During construction of the Voronoi diagram, not all the edges originate in a vertex yet, so there is some calculation involved to find out where the lines should point to. But with a completed Voronoi diagram, everything should originate in a vertex.

I don't have a solution yet for the barebone Voronoi. I guess the visualization and voronoi algorithm should then be decoupled, so that you can pass the Voronoi diagram into a visualizer, but it would be nice to still be able to see a step-wise progress of the algorithm. Not sure yet how to do that, but feel free to send me suggestions 😄

from foronoi.

Thanks a lot for the clarifications. When I have something to show, I will post it here.

from foronoi.

I tried to implement the access to connectd_edges for every vertice in v.vertices, but I ran into several issues. I used the same data as in the examples/bounding_polygon.py, but for integration reasons I scaled up the numbers:

                        bounding_points=[
                             (250, 1000),
                             (500, 1000),
                             (1000, 500),
                             (1000, 250),
                             (500, 0),
                             (250, 0),
                             (0, 205),
                             (0, 500),
                         ],
                         cell_points=[
                             (250, 250),
                             (400, 750),
                             (750, 250),
                             (600, 750),
                             (400, 400),
                             (300, 300),
                             (600, 300),

I iterate over all vertices:

v = Voronoi(bounding)
v.create_diagram(points=cell_points)
for index, vertex in enumerate(v.vertices):
    ...

there are 21 vertices, the first 14 vertices are on the bounding envelope, the remaining ones are inside. The first and the 14th vertex are begin and end of the bounding, they are identical (by vertex object comparison), so I just filter out the duplicate.

The next issue is a bit more complicated. 3rd and 4th vertex have the same position. And some of their connected edges have same start and end. So I collect all valid edges from these same-position vertices and I have all connected edges for that position.

The last issue is the worst and I have not found any workaround for it yet. Inside the bounding every vertex has three connected edges. The first two seem to be ok, but the third one is always wrong, as vector it is always -1 * first_connected_vertex. The screenshot below shows the issue:

Is there anything I am doing wrong in dealing with connected edges ?

from foronoi.

Update on wrong connected edge:

I digged a bit into the voronoi code, changed the following :
https://github.com/Yatoom/voronoi/blob/45d27f8790d43502fb8cff9ace54e042663e5f46/voronoi/algorithm.py#L292-L293
to:

        new_edge = HalfEdge(B, origin=updated, twin=HalfEdge(C, origin=v))
        v.connected_edges.append(new_edge.twin)

Now it seems to work as expected, at least at the first example I tried.

from foronoi.

Hi @rsaccon, thank you for reporting this. I checked it, and indeed new_edge.twin seems to be the correct edge to add.

Before:

After:

Let me dive a bit deeper into it, and I will get back to you.

from foronoi.

Hi @rsaccon, your fix is included in the code now. Thank you very much!
Please let me know if there are still issues that are not solved with this, or if you find any new issues! 😄

from foronoi.

It works perfect now. The only issue I still have to work around is the second one, neighbouring vertices on boundary, which have identical position. I collect all their connected edges and I treat those neighbouring vertices as one single vertice.

But i guess this issue only applies to my special use case and I am fine if it does not get handled in the voronoi lib.

Here is the ugly WORKAROUND I am doing inside my app:

for index, vertex in enumerate(v.vertices):
    # WORKAROUND STEP 1
    # skip neighbouring vertex with identical position
    if index < (len(v.vertices) - 1) and \
            vertex.position.x == v.vertices[index+1].position.x and \
            vertex.position.y == v.vertices[index+1].position.y:
        continue

    # WORKAROUND STEP 2
    # handle the connected edges of the skipped vertex
    if index > 0 and \
            vertex.position.x == v.vertices[index-1].position.x and \
            vertex.position.y == v.vertices[index-1].position.y:
        for edge in v.vertices[index-1].connected_edges:
            start = edge.get_origin()
            end = edge.twin.get_origin()
            if end.x != start.x or end.y != start.y:
                # DO SOMETHING
                ...

    for edge in vertex.connected_edges:
        start = edge.get_origin()
        end = edge.twin.get_origin()
        if end.x != start.x or end.y != start.y:
            # DO SOMETHING
            ...

from foronoi.

Hi @rsaccon, just letting you know that this is going to be fixed in the upcoming version. I have created a new method to clean up zero length edges, that are constructed when two events happen at the same time. The method also cleans up the duplicate vertices. https://github.com/Yatoom/voronoi/blob/ca6aaeff3f712ec5ce2fb1b9cf2ed9aa5384175c/voronoi/algorithm.py#L403

from foronoi.

Great, thanks, looking forward to update it to the latest !

from foronoi.

@Yatoom, I am having one more question:

is there a way voronoi can help in setting a constraint for a user specified minimum edge length ? I have been experimenting with various approaches, but I am either ending up in endless-loops when repeating random voronoi creation until it fits my criteria for minimum edge length or I split the bounding area into a grid and create the random points inside the grid cells, but with that approach I am currently facing the problem that the shapes I get don't look much random anymore. I will tweak this second approach a bit more, but maybe there is a better way to get length constrained edges.

from foronoi.

@Yatoom, I updated to latest release. All seems to work perfectly except the old issue Number 1): if I loop through vertices, the very first and the last of the bounding are identical and show up twice. If I remember properly, after initially reporting this, you made some changes, I updated to latest master, and those duplicates did not show up anymore. But now somehow those duplicates are back ...

anyway, here is my WORKAROUND I had to activate again:

for index, vertex in enumerate(voronoi.vertices):
    if index > 0 and vertex == voronoi.vertices[0]:
        continue

    # DO SOMETHING

from foronoi.

Hi @rsaccon, thanks again for making me aware of this issue! My latest commit 9b7875e should deal with this problem. Hope this helps! 😄

For your other question about minimum edge length, I'm not sure if I understand the question. Could you maybe give an example or draw it, and show what you would want to happen if an user sets a minimum edge length, and which edges (bounding polygon or voronoi edges) it would apply to?

from foronoi.

@Yatoom, latest commit solved the issue, thanks.

Let me try to explain about the minimum edge length. Let's assume the user has a function to create random points (it can be simple like in your triangle example or it could be weighted, to achieve some specific distribution pattern). With the current way voronoi works, the user provides a pre-generated list of such random points. Now, if after voronoi diagram creation, the user detects that some edges are shorter than a minimal edge length, all what could be done is just a complete new diagram creation with different points (finding better "random" points for those which affected the too short edges). This is very inefficient.

So my idea is, instead of just taking a list of voronoi points at create_diagram, alternatively also accepting a callback, where the user can provide his custom defined voronoi point creation. Now if the algorithm creates an edge shorter than the user defined minimal edge, it will redo the last steps and invoke the callback again and hopefully getting a "better" voronoi point (however I am not familiar enough with the internals of the fortune algorithm, to determine whether this makes any sense at all), and when running again it will provide feedback to the callback (I mean calling the callback with the voronoi point in question as argument). Of course an unrealistic large minimal edge will cause trouble in form of endless loop, so the maximal number of callback repetitions for one voronoi point need to be limited to a user definable value. And if that limit is reached, the minimal edge length is just too minimal.

This would apply to bounding polygon and voronoi edges.

Maybe there is an easier way I am not aware of yet, on how one can create a randomly looking voronoi pattern where no edge is shorter than a minimal length ?

Update:
I found an article which mentions constraining the voronoi cell with a Lloyd algorithm. My first question about that was whether it can be integrated with the fortune algorithm. The implementation from that article uses delaunay-triangulation based approach from scipy, but I found another software (written in Rust) which seems to use both, fortune algorithm and loyd iteration, so I will try to figure out whether those approaches might help to get my problem of minimal edge length solved.

Update 2
My first attempt with Lloyd iterations looks promising, I haven't implemented all suggestions from that article, once I have I think my minimal edge length problem will be solved.

However I noticed one possible issue with voronoi. I run voronoi.createDiagram in a loop, once for each Lloyd iteration. The bounding polygon remains the same. So my assumption was, I instantiate once the voronoi class and then I can reuse the instance in the loop, but unfortunately voronoi throws errors if I do so. As workaround I re-instantiate the class in each iteration of the loop, then everything seems to be fine.

boundary = Polygon(my_list_of_boundary_points)
voronoi = Voronoi(boundary)
voronoi.create_diagram(points=my_list_of_initial_random_voronoi_points)
for index in range(my_number_of_lloyd_iterations):
    relaxed_voronoi_points =  my_lloyd_iteration_algorithm(voronoi)
    voronoi = Voronoi(boundary)  # WORKAROUND: RE_CREATE INSTANCE HERE !!!!!!!!!
    voronoi.create_diagram(points=relaxed_voronoi_points)

from foronoi.

While investigating the previous issue (previous post, Update2. @Yatoom do you have anything to comment on that ?) I noticed in my setup, that the elements of voronoi.vertices (for a fixed boundary and set of voronoi points) will not be in the same order if I re-run create_diagram. Is that intended behaviour ? If so, possibly caused by some randomness somewhere in the fortune algorithm.

from foronoi.

Hi @rsaccon, I think I replaced lists with sets somewhere which might cause the randomness. I'll look into it when I have some time.

Nice work on those updates by the way! I hadn't seen them yet. I'll read these also in more detail when I have some more time :)

from foronoi.