计算 3D 平面的 Voronoi 图
是否有代码/库可以计算 3D 平面（平行四边形）的 Voronoi 图？我检查了 Qhull，它似乎只能处理点，在它的示例中，Voro++ 适用于不同大小的球体，但我找不到任何多边形。
在此图像中（3d 中的示例平面） 平行四边形是 3D 的，因为它们有厚度，但在在这种情况下，厚度将为零。！
Is there a code/library that can calculate a Voronoi diagram for planes (parallelograms) in 3D? I checked Qhull and it seems it can only work with points, in its examples Voro++ works with different size of spheres but I couldn't find anything for polygons.
In this image (sample planes in 3d) the parallelograms are 3D since they have a thickness, but in this case the thickness will be zero.!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
沃罗诺伊单元不是平行四边形。您对您发布的图片感到困惑。沃罗诺伊单元边界是分隔各个均值的超平面的一部分。
查看此网站讨论和可视化 3D voronoi 图：
http://www.wblut.com/2009/04/28/ooh-ooh-ooh-3d-voronoi/
为了计算对于voronoi单元，常见的方法是首先构建Delaunay三角剖分。有多种算法可以在 2D 中执行此操作，而在 3D 中则变得更加复杂。但你应该还是能找到一些东西。 qhull 可能是正确的方法。
当您进行 Delaunay 三角剖分时，计算每个四面体的中心。这些是您需要绘制的多边形的角。对于 Delaunay 三角剖分中的任何边，绘制连接相邻中心的多边形。这应该是一个超平面。
现在您需要做的就是绘制属于凸包一部分的边的超平面。为此，您需要将已经拥有的超平面从内部延续到无限外部。
我强烈建议首先从 2d 开始。一旦您有了 2D 的工作代码，请了解如何在 3D 中执行相同的操作。如果你想让它更快，这在 2D 中已经相当棘手了。
这是维基百科上的一张图表，直观地展示了 Delaunay 和 Voronoi 图：
黑线是 Delaunay 三角剖分。棕色线与此正交，并形成 Voronoi 图。 Delaunay 三角剖分可用于各种很酷的可视化事物：计算凸包、voronoi 图和 alpha 形状：http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html
Voronoi cells are not parallelograms. You are confused here by the image you posted. Voronoi cell borders are parts of the hyperplanes that are separating the individual means.
Check out this website discussing and visualizing 3D voronoi diagrams:
http://www.wblut.com/2009/04/28/ooh-ooh-ooh-3d-voronoi/
In order to compute the voronoi cells, the common way is to first build the Delaunay Triangulation. There are a number of algorithms to do this in 2D, while in 3D it gets significantly more complex. But you should still be able to find something.
qhullmight be the proper way to go.When you have the Delaunay triangulation, compute the center of each tetraeder. These are the corners of the polygons that you need to draw. For any edge in the Delaunay triangulation, draw a polygon connecting the adjacent centers. This should be a hyperplane.
Now all you need to do is also draw the Hyperplanes for edges that are part of the convex hull. For this you need to continue the hyperplanes that you should already have from the inside to the infinite outside.
I strongly recommend to start with 2d first. Once you have a working code for 2D, see how to do the same in 3D. This is already pretty tricky in 2D if you want it to be fast.
This is a graphic from Wikipedia visualizing both Delaunay and Voronoi diagrams:
The black lines are the Delaunay Triangulation. The brown lines are orthogonal to this, and form the Voronoi diagram. Delaunay triangulation can be used for various cool visualization things: computing the convex hull, the voronoi diagrams and alpha shapes: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html
Bowyer-Watson 通常是推荐的算法。
大多数论文/算法的问题在于，它们没有解决当点在空间中彼此靠近（因此四面体很薄）、当 voronoi 单元最终应该大部分平坦以及当多个点同时存在时出现的棘手情况。同一个球体。再加上处理不准确的数学和舍入的数字复杂性，您就会陷入无休止的调试。
我的建议是，如果可以接受，请先过滤数据。否则，您最终将在算法中编写大量特殊情况。
不久前，也有一篇日本论文声称有一种不同的方法来解决这些情况，从德劳内三角剖分开始，由此计算出沃罗诺伊单元，但它也有缺陷。
成为一名研究人员一定很高兴，提出广泛的算法并让研究助理担心细节......
Bowyer-Watson is usually the recommended algorithm.
The problem with most papers/algorithms is that they don't address the tricky situations that arise when points are close to each other in space (so the tetrahedrons are thin), when voronoi cells should end up mostly flat and when multiple points are on the same sphere. Add to that the numerical complexity of dealing with inaccurate math and rounding and you have yourself a recipe for endless debugging.
My recommendation is that you filter your data first if that's acceptable. Otherwise, you will end up coding an enormous amount of special cases in your algorithm.
A while ago, there was also a Japanese paper that claimed to have a different approach for resolving these situations by starting from the delaunay triangulation and working out the voronoi cells from that, but it too was flawed.
It must be nice to be a researcher, coming up with the broad lines of algorithms and letting the research assistants worry about the details...