非凸多边形内的最大圆 [英] Largest circle inside a non-convex polygon

问题描述

如何找到可以容纳在凹多边形内的最大圆?

蛮力算法是可以的，只要它可以实时处理约 50 个顶点的多边形.

解决方案

解决这个问题的关键是首先进行观察:适合任意多边形内的最大圆的中心是:

>

1. 多边形内部；和
2. 距离多边形边缘的任意点最远.

为什么?因为圆边缘上的每个点都与该中心等距.根据定义，最大的圆将具有最大的半径，并且至少会在两个点上与多边形相接触，因此如果您找到距离多边形最远的点，您就找到了圆的中心.

这个问题出现在地理学中，并以任意精度迭代解决.它被称为无法进入的极点问题.见 无法到达的极点:地球上最偏远地区的计算算法.

基本算法如下:

1. 将 R 定义为从 (x_min,y_min) 到 (x_max,y_max);
2. 将 R 分成任意数量的点.论文使用21作为启发式(意思是将高度和宽度除以20)；
3. 剪切多边形外的任何点；
4. 对于余数，找到离边上任何一点最远的点；
5. 从那时起，定义一个具有更小的间隔和边界的新 R，并从第 2 步开始重复以获得任意精度的答案.该论文将 R 减少了 2 的平方根.

一个注意，如何测试一个点是否在多边形内:解决这部分问题的最简单的方法是在点的右侧投射一条射线.如果它穿过奇数条边，则它在多边形内.如果是偶数，则在外面.

此外，就测试到任何边缘的距离而言，您需要考虑两种情况:

1. 该点垂直于该边上的一个点(在两个顶点的边界内)；或
2. 不是.

(2) 很简单.到边的距离是到两个顶点的距离中的最小值.对于 (1)，该边上的最近点将是从您正在测试的点开始以 90 度角与边相交的点.请参阅点到射线或线段的距离.

How can I find the largest circle that can fit inside a concave polygon?

A brute force algorithm is OK as long as it can handle polygons with ~50 vertices in real-time.

解决方案

The key to solving this problem is first making an observation: the center of the largest circle that will fit inside an arbitrary polygon is the point that is:

1. Inside the polygon; and
2. Furthest from any point on the edges of the polygon.

Why? Because every point on the edge of a circle is equidistant from that center. By definition, the largest circle will have the largest radius and will touch the polygon on at least two points so if you find the point inside furthest from the polygon you've found the center of the circle.

This problem appears in geography and is solved iteratively to any arbitrary precision. Its called the Poles of Inaccessibility problem. See Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth.

The basic algorithm works like this:

1. Define R as a rectilinear region from (x_min,y_min) to (x_max,y_max);
2. Divide R into an arbitrary number of points. The paper uses 21 as a heuristic (meaning divide the height and width by 20);
3. Clip any points that are outside the polygon;
4. For the remainder find the point that is furthest from any point on the edge;
5. From that point define a new R with smaller intervals and bounds and repeat from step 2 to get to any arbitrary precision answer. The paper reduces R by a factor of the square root of 2.

One note, How to test if a point is inside the polygon or not: The simplest solution to this part of the problem is to cast a ray to the right of the point. If it crosses an odd number of edges, it's within the polygon. If it's an even number, it's outside.

Also, as far as testing the distance to any edge there are two cases you need to consider:

1. The point is perpendicular to a point on that edge (within the bounds of the two vertices); or
2. It isn't.

(2) is easy. The distance to the edge is the minimum of the distances to the two vertices. For (1), the closest point on that edge will be the point that intersects the edge at a 90 degree angle starting from the point you're testing. See Distance of a Point to a Ray or Segment.

这篇关于非凸多边形内的最大圆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！