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

问题描述

我如何才能找到可以容纳一个凹多边形内的最大圆？

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

一个蛮力算法是OK，只要它可以处理多边形〜50顶点的实时性。

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. 在多边形;和
2. 从上多边形的边任意点最远。

为什么呢？因为上一圆的边缘的每个点是从该中心等距。根据定义，最大的圈将拥有最大的半径，将涉及至少两个点的多边形，所以如果你发现里面的多边形最远的你已经找到了圆心的位置。

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.

这个问题出现在地理和迭代求解到任意precision。其所谓的交通不便问题的波兰人。请参见交通不便的极点：一个计算算法地球最偏远的地方。

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.

基本算法是这样的：

1. 定义为r从（X <子>分，Y <子>分）到（x <子>最大的直线区域，Y <子>最大）;
2. 分割R插入点的任意数量。本文采用21启发式（意为除以20的高度和宽度）;
3. 在剪辑是多边形外的任何点;
4. 对于其余找到点说就是从最远的边缘任何一点;
5. 从该点定义了一个新的R较小的区间和范围，并重复步骤2去任意precision答案。纸由2的平方根的因子减少R上。

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. 点是垂直于该边缘（两个顶点的边界内）的一个点;或
2. 在事实并非如此。

（2）是容易的。至边缘的距离是最小的距离的两个顶点。对于（1），上边缘的最近点会相交的边缘离你正在测试的点开始90度角的位置。请参见一个点的距离光线或段。

(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屋！