Help with making Voronoi

[vectorvolt]

I’m making a Voronoi diagram using the Delaunay method, and I’ve managed to find the vertices for the Voronoi diagram, but I can’t figure out how to group them to the correct voronoi cell (the delaunay point they are closest to). The problem I’m having is that some Voronoi vertices are part of multiple cells. When I check which Delaunay point the vertex is closest to, I don’t know how to calculate which other Delaunay points it also belongs to. (well I kind of did it but it doesn’t always work, sometimes vertices that are not supposed to be part of a cell get added to it, and sometimes there’s not enough vertices to make the cell)

Here’s an image of it working properly:

But of course it doesn’t always work, and I end up getting some strange problems:


(there is also a slight problem with the ear clipping, but I’ll fix that later)

Pretty much what I did was, for every Voronoi edge (calculated by connecting adjacent Delaunay triangle centres) it looks for the closest Delaunay edge and then adds the Voronoi vertices to the cells of the two Delaunay points that make the edge. (then use ear clipping to create it)

I’ve tried other things like finding the closest Delaunay point to a Voronoi vertex. This was the closest I ever got, by comparing the closest point to all the other Delaunay points and seeing if the distance is equal, but even if the decimal is off by like .00000001 it will not count as equal. So I tried rounding it but then too many vertexes were equal. I also tried trimming the number down so instead of like 0.123456789 it would be 0.1234567 but this still doesn’t work for all cases (it was close though). It’s either too precise or not precise enough…

Sorry if this is doesn’t make sense, I wasn’t sure how to explain it

[Scottifly]

I only understood a fragment of that, but from what I read you are having issues comparing 2 values.
What if you use a range to compare them?

Basically
`if x >= (y - .0000001) and x <= (y + .0000001) then – use whatever decimal range you want)

There’s probably cleaner ways to write the code, but that’s the basic idea.

[vectorvolt]

Hey thanks for replying, basically the part where I was saying about comparing two values I was just explaining a way I tried to the “Voronoi grouping” but it didn’t work (I’ll explain what I mean by “Voronoi grouping” below). I’ve tried things like a range to compare the distances but the problem is it has to be exactly precise, and Roblox decimals for some reason are inconsistent even when I run the exact same code… I’ll try and explain it better -

This is a Voronoi diagram:

One method of creating a Voronoi diagram is through a “Delaunay triangulation”, which connects a set of points by forming triangles without any point inside the circumcircle of those triangles. A Voronoi diagram can be created by connecting the circumcircles of adjacent triangles.

Here’s a Delaunay triangulation:

Now here’s a Delaunay triangulation (far left) next to a Voronoi diagram (middle), and then both of them together at the far right:

So I’ve managed to create the Delaunay triangulation, and I’ve connect the centres and figured out all the vertex points of the Voronoi. I just don’t know how to figure out which “cell” each vertex point belongs to. For reference, here’s the Voronoi diagram but I’ve highlighted a single “cell” in black:

And finally, here are the “vertex points” of that single cell (the white dots):

As you can see, multiple cells use those vertex points. I just can’t seem to figure out which vertex points belong to which cells (because they can belong to multiple). The only way I managed to group some of them into cells is by seeing which Delaunay point (black dots in the picture above) each vertex is closest to, and that’s where all that number comparing came from.

To group vertices to cells I found the closest Delaunay point (black dots in image) to a vertex (white dots), then if any other Delaunay point has an equal distance then the cell for that Delaunay point also uses that vertex. That’s where I’m having problems with comparing, because it needs to be exact otherwise it’s not equal…

Thank you if you managed to read all this , and to anyone reading… is there any other way of figuring out which vertex belongs to which cell? Or does the method I’m using work and I’m just doing it wrong?

[Scottifly]

Ah, thanks, I understand it better.
The math involved is way above my pay scale…

How exact does the placement have to be? Is it just for a visual effect?

Can you assume that 2 points are the same distance away if you round their magnitudes to the black dots to a certain decimal place? If so then the math involved to create those points might produce different values but the rounded values could be used.
Either that or round the vertex X,Y,Z positions to a decimal place and calculate the magnitudes from that point?

If 2 points are rounded to within a few thousandths or ten thousandths apart it could balance out the way the vertex is calculated to black dots in other cells and allow those magnitudes to be within that rounded range as well.

[MysteriousVagabond]

What is the data structure you are using to store your vertices? While I haven’t worked specifically with Voronoi cells, I’ve used doubly connected edge lists to store faces in the past, and they worked well. It side-steps the issue of shared geometry by breaking edges into two half edges, one going one way and its “twin” going the other. These are not shared between faces; they belong to at most one face each.

By sorting outgoing edges from a vertex by angle, you can assign a half edge’s “next” half edge as the outgoing edge from the vertex you are traveling to that is adjacent to your current half edge’s twin. A face can subsequently be derived by walking along half edges with a consistent winding direction until you return to the one you started at. Every face generated this way should contain one and only one Delaunay point if your Voronoi edges are correct.

Also, for what it’s worth, the Voronoi cells should be convex, so you can use fan triangulation to draw them for a performance boost.

[tlr22 (FusionOak)]

As stated by MysteriousVagabond you should be sorting them so it’s just a table lookup.

The float solution has 2 flaws. Firstly fuzzy equal for floats should not be a static number (like 0.001) because floats can be incredibly small or incredibly large, so unless you have very specific constraints, you should likely do a percentage based comparison. But the larger issue is that you are measuring distances. While there are certainly ways to manage from doing it like that, unless you are specifically measuring distances to the nearest line segments, there are bad cases that will be exceptions to your rules. Like any site distance checks can’t work because there are cases that will have the real site further from the wrong site (like a very, very long thin shape)

bonus code stuff

Feel free to use the provided code (below) in any way you see fit. I’m primarily providing it in case you want to reference it, but feel free to just use my implementation if you think it’s easier. There is no super easy documentation though, so it might be easier to just finish your own.
It was never super polished and probably still has a ton of artifacts (like dead commented code) in it from my frustrating journey into making it work (so many edge cases). If you do try to use it, note that there is a bug in generation that I never quite solved, but it’s rare enough you can just pcall and retry with new or slightly shuffled in place points.

And inside our some modules with some geometry goodies if you want to go digging for them like the clipping algorithm I use, though it seems your code already clips
DiagramThing.rbxm (10.6 KB)

It assumes all inputed points fall within a 1x1 zone centered around the origin. Or at least it did, I recall working on making the super triangle generated by the convex hull of the input points, though I don’t remember if I ever actually implemented it. So probably assume you should scale the inputs and outputs to and from the unit square if you use this. The debug stuff does that automatically. And the data structures inside might be confusing enough it might be easiest just to continue writing your own if you were going to use mine. All variables inside the diagram objects though are intended to be public and referenced.

[vectorvolt]

Hello, thank you so much to everyone who replied, I really appreciate it I’ve been really struggling with this problem. I’m going to try all these methods, the problem kind of came from the way I created the Voronoi in the first place.

I’m going to mark this as solved, I think I can see a way of creating the Voronoi better while also knowing what vertices belong to what cell thanks to everyone’s help!