21–30 of 34 posts
Earlier quoted context omitted.
It's all fun and games until you leave the euclidean plane and calculate the real distance.
Distance isn't so much a problem. The real problem is that the surface is closed.
My favorite algorithm for generating Voronoi diagrams is the Jumping flood algorithm: https://en.wikipedia.org/wiki/Jump_flooding_algorithm This is an approximate algorithm that only works in pixel space, but it's lots of fun to implement (simpler to implement than Fortune's algorithm).
Earlier quoted context omitted.
Distance isn't so much a problem. The real problem is that the surface is closed.
Being closed really isn't an obstacle. For example you can solve a euclidean modulus toroid by just tiling the space once more around itself, running a vanilla euclidean solver and then unioning the 9 copies of the space.
One of the things I really want to work on in the next few months is a path intersection implementation that's robust by construction, backed up both by a convincing (if not formal) argument and tests crafted to shake out robustness issues. I have a bunch of ideas, largely motivated by the need to generalize well to curves - Shewchuk's work, cited elsethread, is impressive but I'm not smart enough to figure out how to make it work for arbitrary Béziers.
There's an issue[277] to track the work, and that has pointers to some of the ideas. If anyone is interested in working with me on this, please get in touch. If successful, I think it'll result in a nice code base and also likely a publishable paper.
Earlier quoted context omitted.
Being closed really isn't an obstacle. For example you can solve a euclidean modulus toroid by just tiling the space once more around itself, running a vanilla euclidean solver and then unioning the 9 copies of the space.
If the pointset is degenerate (e.g. 4 points on a circle), then you may get different local results in different copies of the space and the unioning may be difficult.
Wait until you see the actual heuristic I use for solving voronoi/delaunay in arbitrary topologies. I need to write a blog post on it anyways.
Earlier quoted context omitted.
If the pointset is degenerate (e.g. 4 points on a circle), then you may get different local results in different copies of the space and the unioning may be difficult.
Ah, I'm an engineer not a theorist. Such degenerate input is unlikely to be a valid use case, can be detected, and I can reject it. Wait until you see the actual heuristic I use for solving voronoi/delaunay in arbitrary topologies. I need to write a blog post on it anyways.
https://ncar.ucar.edu/what-we-offer/models/model-prediction-... https://mpas-dev.github.io/
My favorite algorithm for generating Voronoi diagrams is the Jumping flood algorithm: https://en.wikipedia.org/wiki/Jump_flooding_algorithm This is an approximate algorithm that only works in pixel space, but it's lots of fun to implement (simpler to implement than Fortune's algorithm).
Just ignore Big O analysis. I guarantee any kind of GPU will blow all CPU algorithms out of the water. This has been known for at least 30 years - I believe there was an SGI demo of it back in the day.
OpenGL can also do edge detection image processing (Laplacian convolution) and give you the line boundaries, if that's what you need. Perhaps a jittered double-rendering can give the same result.
If the resolution is not enough, just multiply the canvas size - x2, x4 ... it will still be faster.
I wrote a moderately popular Delaunay/Voronoi library for Unity a few years back [1] with a neat little demo video [2]. I implemented the incremental Bowyer-Watson algorithm for generating the triangulations, and then took the dual to generate the Voronoi tesselation (I also added a "clipper" that clips the voronoi diagram to a convex outline, which was fun, I haven't seen that anywhere else before and had to figure…
Earlier quoted context omitted.
Could you not do dimensional reduction first, run the algorithm on the first X components, map the result back onto the loadings?
Most triangulation algorithms are designed for the two-dimensional plane, so this only works if the first two components are sufficient.