对Delaunay三角剖分和最大内切圆的困惑 [英] Confusion on Delaunay Triangulation and Largest inscribed circle

问题描述

我需要找到一个凸多边形的最大内接圆，我已经搜索了很多网站，并且我知道这可以通过使用Delaunay三角网来完成。我在。后来中找到。

简单&快速实现。一个更简单的计算Voronoi图的算法是由直骨骼 。对于凸多边形，Voronoi图和直骨架是相同的。

直骨骼实现背后的算法 Stalgo 基本上模拟了波前结构的演变（灰色偏移曲线）。对于凸多边形，这可以简化为找到塌陷边的序列。

所以一个简单的O（n log n）算法可能如下所示：

1. 构造多边形边的圆形列表。计算波前传播过程中每个边的崩溃时间，并将此事件插入优先级队列中。
   
2. 直到队列为空：取出下一个边崩溃事件：将边从圆形结构并更新被删除边缘的相邻边的倒塌时间。
   实际上，您可以进一步简化上述算法：您不需要更新优先级队列中的边缘折叠，而只需插入新的边缘折叠：由于边缘的新崩溃时间严格较低，因此您始终首先获得正确的事件并消除其他事件，并且队列的增长不会超过2n。因此，您不会损失O（n log n）的时间复杂度。对于最大内切圆问题，您可以进一步简化上述算法：Voronoi节点（你需要寻找的是最后一个三角形在优先级队列结束时崩溃。
   
   
   

   这个算法应该是快速的练习和只有几行代码。

   
   

   I need to find a largest inscribed circle of a convex polygon, I've searched many sites and I get that this can be done by using Delaunay triangulation. I found a thread in CGAL discussion with an algorithm using CGAL:

   You can compute this easily with CGAL:

   First, compute the Delaunay triangulation of the points.

   Then, iterate on all the finite faces of the triangulation. For each finite face f

   • compute its circumcenter c
   • locate c in the triangulation (to speed up things, you can give one vertex of f as starting hint for the point location)
   • if the face returned by locate(c,hint) is finite, then the circumcenter c lies in the convex hull of the points, so, f is a candidate
   • if f is such a candidate face, compute its squared circumradius keep only the face with minimum squared circumradius

   The CGAL manual (chapter 2D triangulation, together with a few things from the kernel) shows every basic function to do this.

   I was a bit confused with the last part of this algorithm. When I read it what I understand from it is that the minimum circumradius of the triangulation face is the radius for the largest inscibed circle. But from examples of polygon with Delaunay triangulation, it seems that even the smallest circumcircle sometimes cannot fit inside the polygon, so how can this has the same radius as the largest inscribed circle?

   解决方案

   Maximum inscribed circle in polygons. The classical computational-geometry solution to the maximum inscribed circle problem for polygons is to use the generalized Voronoi diagram of the polygon's faces resp. the medial axis of the polygon. This approach works in a more general setting like polygons with holes, see this stackoverflow answer to a similar question.

   Convex input. The convexity of your input polygon, however, gives the problem more structure, which I would like to comment on. Consider the following convex input polygon (black), the Voronoi diagram (blue), and the maximum inscribed circle (green) centered on a Voronoi node.

   The classical Voronoi-based solution is to (i) compute the Voronoi diagram and (ii) take the Voronoi node with largest clearance (i.e., distance to its defining faces).

   The Voronoi diagram of a polygon with holes (i.e., the set of vertices and edges) can be computed in O(n log n) time, c.f. Fortune's algorithm (1986). Later Chin et alii (1999) gave an O(n) algorithm for the medial axis of a simple polygon.

   For convex polygons, however, a time-optimal algorithm for Voronoi diagram that runs in O(n) time was already known in 1989 due to Aggarwal et alii. This algorithm follows basically the following idea: Consider the grey offset curves moving inwards at unit speed. If you project this movement into three-space where the z-axis is time you get a unit-slop roof over the polygon:

   This roof model could also be characterized as follows: Put a half-space on each polygon edge at 45° slope with polygon (such that they contain the polygon) and intersect them all. So if you can quickly compute the intersect of half-spaces then you can also quickly compute Voronoi diagrams of convex polygons. Actually, for the maximum inscribed circle problem we do not need to go back to the Voronoi diagram but take the one peak of the roof, which marks the center of the maximum inscribed circle.

   Now the half-spaces are dualized to points, and then the intersection of half-spaces corresponds the convex hull of its dual points. Aggarwal et al. now found an O(n) algorithm for the convex hull of points that stem from this setting.

   A summary of this construction that leads to a Voronoi diagram algorithm for convex polyhedra in any dimension can be found in a blog article of mine.

   Simple & fast implementation. A simpler algorithm to compute the Voronoi diagram is motivated by straight skeletons. For convex polygons the Voronoi diagram and the straight skeleton are the same.

   The algorithm behind the straight-skeleton implementation Stalgo basically simulates the evolution of the wavefront structure (the grey offset curves). For convex polygons this reduces to finding the sequence of edges that collapse.

   So a simple O(n log n) algorithm could look like this:

   1. Construct a circular list of the polygon edges. Compute the collapse time of each edge during wavefront propagation, and insert this event into a priority queue.
   2. Until the queue is empty: Take out the next edge-collapse event: Remove the edge from the circular structure and update the collapse times of the neighboring edges of the removed edge.

   Actually, you can simplify the above algorithm further: You do not need to update edge collapses in the priority queue but simply insert new ones: Since the new collapse time of edges are strictly lower, you always get the right event first and dismiss the others and the queue is not growing larger than 2n. Hence, you do not compromise the O(n log n) time complexity.

   For the maximum inscribed circle problem you can simplify the above algorithm even further: The Voronoi node (resp. straight skeleton node) you look for is due to the collapse of the final triangle at the end of the loop over the priority queue.

   This algorithm should be quick in practice and only a few lines of code.

   这篇关于对Delaunay三角剖分和最大内切圆的困惑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！