by cpp_frog on 10/24/23, 1:29 PM with 33 comments
by emmanueloga_ on 10/25/23, 5:08 AM
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.
--
by TomK32 on 10/25/23, 10:01 AM
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.
by OskarS on 10/25/23, 9:20 AM
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
by omoikane on 10/25/23, 4:32 AM
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).
by raphlinus on 10/25/23, 2:15 PM
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.
by loehnsberg on 10/25/23, 7:34 AM
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.
by lispisok on 10/25/23, 4:32 PM
https://ncar.ucar.edu/what-we-offer/models/model-prediction-... https://mpas-dev.github.io/
by ginko on 10/25/23, 7:56 AM
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.
by ad-astra on 10/25/23, 6:20 AM
