Message Boards Message Boards

GeoVoronoi (and GeoDelaunay)

Christopher Wolfram, WOLFRAM
Posted 4 years ago

An example of a GeoVoronoi

POSTED BY: Christopher Wolfram
8 Replies
Sort By:
J. M.
J. M.
Posted 4 years ago

This is very nice. I note that the spherical Voronoi implementation in my posts was written quite a while ago, and using undocumented properties like "VertexFaceConnectivity" was the easiest method. Nowadays, I would say it's more advisable to use MeshConnectivityGraph[]:

With[{mcg = MeshConnectivityGraph[chm, {2, 0}, 0]},
     Table[EdgeList[mcg, DirectedEdge[_, {0, k}]][[All, 1]][[All, 2]],
           {k, MeshCellCount[chm, 0]}]]

but of course you should do your own comparisons against your DualPolyhedron[] approach.

A good survey paper to read about all these things is this paper by Sugihara, which has also nice pointers to other literature.
POSTED BY: J. M.

Thanks. The issue with MeshConnectivityGraph is that it destroys the ordering information. That is, it can tell you which faces are adjacent to which vertices, but not the order in which they are around it, and so it is difficult to use them to construct a polygon. (This is the same as the issue with AdjacentMeshCells).

Thanks for the paper as well. My original goal was to implement geo power diagrams (also known as Laguerre Voronoi diagrams), and I was referencing this paper which happens to be by the same author. The paper you sent, however, looks like it has some other information about computing the power diagram using only 3D convex hulls, which would be great, so I'll have to look into it.
POSTED BY: Christopher Wolfram
J. M.
J. M.
Posted 4 years ago

I agree; in a sense, that's what made the undocumented functions a little more convenient to use, since they were (apparently) orientation-preserving. In the planar case, you can do a reconstitution with ConvexHullMesh[], but it is murkier in the spherical case.
POSTED BY: J. M.

enter image description here -- you have earned Featured Contributor Badge enter image description here

Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!
POSTED BY: EDITORIAL BOARD

POSTED BY: Richard Hennigan

Ah, that makes a lot of sense. You are basically getting only the "outer" hull (a bit like the upper/lower hull) instead of the full convex hull. I'll make that change if I submit these to the function repository.

Edit: I wonder why GeoVoronoi seems to work without that extra vertex.
POSTED BY: Christopher Wolfram
J. M.
J. M.
Posted 4 years ago

That's because Voronoi already naturally wraps around, similar to how a planar Delaunay is bounded, but a planar Voronoi covers all of the plane.
POSTED BY: J. M.

Congratulations! Your post was highlighted on the Wolfram's official social media channels. Thank you for your contribution. We are looking forward to your future posts.
POSTED BY: EDITORIAL BOARD
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract