3 ms·

Wow literally just what I needed to see for a project I’m working on, I love hacker news!

• fastball 3y ago
  Same for me! I just started working on a Voronoi-based experiment[1] yesterday. This is my progress so far. [1] https://7887885e.vorannoy.pages.dev/ https://7887885e.vorannoy.pages.dev/
  • Rhapso 3y ago
    It's all fun and games until you leave the euclidean plane and calculate the real distance.
    • amelius 3y ago
      Distance isn't so much a problem. The real problem is that the surface is closed.
      • Rhapso 3y ago
        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.
        • amelius 3y ago
          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.
          • Rhapso 3y ago
            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.
            • amelius 3y ago
              It's very easy to get 4 points on a circle. In 2d space just the four corners of a unit square would do it.
              • Rhapso 3y ago
                On a sphere or modulus space, that just becomes a K4, so it isn't even an edge case, it is the solution that the approximation would generate.
                • amelius 3y ago
                  Yes, you definitely have to deal with it, in virtually any setup.
• amelius 3y ago
  I'd advise to look into Jonathan Shewchuk's work which is very accessible. https://www.cs.cmu.edu/~quake/triangle.research.html https://www.cs.cmu.edu/~quake/triangle.research.html