I have a theory that the union of the edges of the RNG and EMSP could be used for automatic navigation between widgets in a GUI: combining the two, there's always between 1 and 4 edges coming out of every point, and so each of them could correspond to a direction key up/down/left/right according to some simple heuristic.
--
In 3D space the Delaunay triangulation would produce a bunch of irregular tetrahedra, so the edges coming out from every vertex would vary between a minimum of 3, and a maximum of 12, if I get it right (ref: [1] :-).
The 3D Voronoi cells are another story... I found some implementation that you can play with to see how it looks [2] [3], each cell is of a shape called "convex polytope". It feels like these cells are packed like each of the sub-cubes of a rubik, but I'm not 100% sure :-) ... if that's true, you could jump from each vertex to the next in at most 26 directions? (hand-waves :-p)
--
1: https://en.wikipedia.org/wiki/Tetrahedron#/media/File:M_tic....
The process to create it is as simple as you might think, select points, draw the center lines for all pairs of close neighbour points and the corners will appear naturally. Tape all edges and paint the wall starting with almost white, mix more of the three base colours into for each of the cells.
Bowyer-Watson (which is described in this article) seems very simple to implement when you start: just start with a "big triangle" and then add points iteratively to it, and perform the flips you need to do. To do it performant, you have to build up a tree structure as you go, but it's not very tricky.
However: almost every description (including on Wikipedia) and implementation of Bowyer-Watson I could find was wrong. There's an incredibly subtle and hard to deal with issue with the algorithm, which is the initial "big triangle". Most people who implement it (and indeed I did the same initally) just make the triangle big enough to contain all the points, but that's not enough: it needs to be big enough to contain all the points in all the circumcircles of the triangles. These circumcircles can get ENORMOUS: in the limit of three points on a line, it's an infinite half-plane. Even if they aren't literally collinear, just close, the triangle becomes way to huge to deal with.
The answer is that you have to put the points "at infinity", which is a very weird concept. Basically, you have to have special rules for these points when doing comparisons, it's really tricky and very hard to get right.
If I were doing this again, I wouldn't use Bowyer-Watson, this subtlety is too tricky and hard to get right. Fortune's sweep-line is more complex on the surface, but that's the one I would go with. Or the 3D convex hull technique (which I also wrote a library for, by the way [3]).
[1]: https://github.com/OskarSigvardsson/unity-delaunay
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.
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.
Suppose that you have a point that is inside of the convex hull of the mesh that you want to use for triangulation (we‘re talking hyper-triangles here). What are the best points to choose for your triangulation? Since there are a lot of candidates for hyper-triangles you cannot possibly store the set of triangles beforehand.
I approached this problem using linear programming using the distance to the mesh points to find the best triangle. Not sure if this is the best approach though.
Happy to hear if someone knows of a better approach.
https://ncar.ucar.edu/what-we-offer/models/model-prediction-... https://mpas-dev.github.io/
It requires sorting the points along one axis which already gives O(nlog(n)) as a lower bound, but I'd be interested in how the line-sweeping would need to be done to not go over that.
The number of points in the beach front should roughly scale with the square root of points, so a naive search/replace per point insertion would take sqrt(n) operations and a O(n*sqrt(n)) overall runtime.
> sorting the points along one axis which already gives O(nlog(n))
You're looking at it backwards, this is actually good news! It means that any subsequent work we do of similar or lower complexity doesn't change anything.
I never said that. I just mentioned that O(n log(n)) is the lower bound since sorting will already take that long.
What I'm concerned with is the complexity of the scanning step, which I think might be more than O(n log(n)) on its own (and therefore more than O(n log(n)) overall)
At least I'd like to see an explanation why it's <= O(n log(n))
