Using PyGame to show Sci Py voronoi edges creates weird "star" effect

Question

I am trying to use SciPy and PyGame to create and display a Voronoi Diagram over my randomly generated world map.

The problem that I'm running into, is that there's always one point that has weird lines that ignore anything else and spread out across the map like a star or something. As can be seen on the top left and bottom left corners, they don't head off into infinity.

How can I get rid of it?

What's Shown:

My Code:

import numpy
import random
import pygame
from scipy.spatial import Voronoi


def __generate_voronoi():
    """
    Randomly chooses various points within the x and y dimensions of the map.
    Then, uses SciPy to generate a voronoi diagram with them, and returns it.

    :return: SciPy voronoi diagram
    """

    point_arr = numpy.zeros([900, 2], numpy.uint16)

    for i in range(900):
        point_arr[i][0] = numpy.uint16(random.randint(0, 1600))
        point_arr[i][1] = numpy.uint16(random.randint(0, 900))

    return Voronoi(point_arr)


def draw_voronoi(pygame_surface):
    # generate voronoi diagram
    vor = __generate_voronoi()

    # draw all the edges
    for indx_pair in vor.ridge_vertices:
        start_pos = vor.vertices[indx_pair[0]]
        end_pos = vor.vertices[indx_pair[1]]

        pygame.draw.line(pygame_surface, (0, 0, 0), start_pos, end_pos)

It's not a solution, but the code could check the line length `start_pos` -> `end_pos` and discard any line longer than some calibrated maximum. — Kingsley, Mar 19 '19 at 01:35
@Kingsley thank you, but I'd like to see if I can find something that would work even if the point was near the border of the map. — LuminousNutria, Mar 19 '19 at 01:37
The indexes in `ridge_vertices` can include -1 values, indicating a line at the edge of the diagram that heads off to infinity, rather than connecting to another point in `vertices`. You're blindly treating these values as indexes, resulting in a line to whatever vertex happened to be last in the list. Generating a meaningful far endpoint to represent these infinite lines requires some additional calculation - I would suggest looking at the source code for `scipy.spatial.voronoi_plot_2d` as a starting point. — jasonharper, Mar 19 '19 at 02:21
@jasonharper Thank you, but I think you made a mistake about the infinity thing. The lines don't actually head off into infininity. Take a look at the top left and bottom left corners of the image. — LuminousNutria, Mar 19 '19 at 18:58
@LuminousNutria they are lines that *Should* be heading to infinity, so they are given an index of -1. In many languages this is a simple way to return an error rather than in index, but in python -1 is a valid index. Take a look at "*/python_location/Lib/site-packages/scipy/spatial/_plotutils.py*" line 173-188 to see how the builtin utility does is. — Aaron, Mar 19 '19 at 19:13
@Aaron Thank you! I had forgotten that -1 is an index in python. — LuminousNutria, Mar 20 '19 at 17:08

LuminousNutria · Accepted Answer · 2019-03-22T00:04:40.767

3

Thanks to the patient commenters here, I have learned that vor.vertices will return -1 for the first index of a point that goes to infinity. This creates a problem, since python treats -1 as the index of the last element of a list or array.

The solution to my problem was not to draw any lines that had a -1 index from vor.vertices.

I implemented that by replacing the draw_voronoi() function with this code:

def draw_voronoi(pygame_surface):

    # generate voronoi diagram
    vor = __generate_voronoi()

    # draw all the edges
    for indx_pair in vor.ridge_vertices:

        if -1 not in indx_pair:

            start_pos = vor.vertices[indx_pair[0]]
            end_pos = vor.vertices[indx_pair[1]]

            pygame.draw.line(pygame_surface, (0, 0, 0), start_pos, end_pos)

That produced this image:

edited Mar 22 '19 at 00:04

answered Mar 20 '19 at 17:07

LuminousNutria

1,883
2
18
44

1

This question (and answer) remind me slightly of [This](https://stackoverflow.com/questions/28665491/getting-a-bounded-polygon-coordinates-from-voronoi-cells/33602171#33602171) answer to another question that helped me solve another [question](https://stackoverflow.com/questions/55026022/integrating-2d-data-over-an-irregular-grid-in-python) as well. I believe they may help you in your understanding of voronoi charts a little bit, and might be of some use in your game. – Aaron Mar 20 '19 at 17:20
@Aaron I was going to try and figure out how to make those infinite lines appear to go off the edge of the map. Thanks again! – LuminousNutria Mar 20 '19 at 17:26
1

that or you could re-implement the builtin scipy implementation I mentioned in my first comment. – Aaron Mar 20 '19 at 18:24
@Aaron I think we might have different versions of `_plotutils.py`. In mine line 173-188 are just part of the doc string of the `voronoi_plot_2d()` function. I'm not sure what they indicate in-particular. They say, "Specifies the size of points Returns ------- fig : matplotlib.figure.Figure instance Figure for the plot See Also -------- Voronoi Notes ----- Requires Matplotlib. " – LuminousNutria Mar 20 '19 at 18:33
1

Well, I was basically just trying to reference that function. I figured it wasn't something that changed that often. The relevant bits are how that function identifies `finite_segments` and `infinite_segments`, and how it calculates a finite point (fairly far away) to represent the infinite line. – Aaron Mar 20 '19 at 18:42
Oh! I see. I will take a closer look at it. – LuminousNutria Mar 20 '19 at 18:44

Using PyGame to show Sci Py voronoi edges creates weird "star" effect

1 Answers1