search

gorhill / Javascript-Voronoi

A Javascript implementation of Fortune's algorithm to compute Voronoi cells
http://www.raymondhill.net/voronoi/
Other
1.02k stars 166 forks source link

Duplicate vertices on bounding box #19

Open m-ender opened 10 years ago

m-ender commented 10 years ago

I noticed that all vertices on the bounding box (except the four corners) are duplicated (once for each cell sharing the vertex, I suppose).

Is that a bug or a necessity due to the algorithm used? I couldn't find a previous issue on this, so I thought I'd ask.

If it's a necessity, are the coordinates of duplicates always guaranteed to be numerically identical or could they differ due to some floating-point foo?

gorhill commented 10 years ago

I would say it's more because how the algorithm works. When the cells are intersected with the bounding box, new "border" edges are created for each cell which needs closing, without really caring about the adjacent cells.

I suppose a better cell-closing algorithm could be written in order to ensure that conceptually shared vertices are actually really shared in the implementation.

As it is now, they should be identical up to epsilon.

m-ender commented 10 years ago

By "up to epsilon", do you mean they could differ in the least significant bit, or that they'll be identical to machine precision?

gorhill commented 10 years ago

If I look at the code (sorry it has been a while), down to Voronoi.ε -- just to be safe.

Anyway, I am looking at the code now, and I suspect with a smarter logic I could have reused the existing vertices instead of creating new ones. I don't like the inconsistency you mention and which I hadn't thought about when I created this code.

So, let's consider this a bug which hopefully eventually I will get around to fix.

m-ender commented 10 years ago

Ah right, I wasn't aware of ε in your code. (lol, Unicode indentifiers :))

For now, I'll just try to stitch the vertices together if I need to, but thanks for looking into it!

darabos commented 8 years ago

I think it may be worth fixing the documentation in the meanwhile. It's downright misleading:

An array of unordered, unique Voronoi.Vertex objects making up the Voronoi diagram.

They are not unique.

(Thanks for the library anyway!)

eranimo commented 7 years ago

Any chance this could be fixed? It's preventing me from being able to walk along the edges of the graph by matching vertices.