如何检查一个圆是否在凸多边形内部？

Question

我想检查一个圆是否与凸多边形相交或位于其内部。我找到了一种绝妙的方法来检测点是否在多边形内（来自这里）：

        public boolean insidePolygon(Vector2 [] vertices, Vector2 p)
        {
            int i, j;
            boolean c = false;
            int nvert = vertices.length;
            for (i = 0, j = nvert - 1; i < nvert; j = i++)
            {
                if (((vertices[i].Y > p.Y) != (vertices[j].Y > p.Y)) &&
                 (p.X < (vertices[j].X - vertices[i].X) * (p.Y - vertices[i].Y) / (vertices[j].Y - vertices[i].Y) + vertices[i].X))
                    c = !c;
            }
            return c;
        }

这对于单个点来说完美地工作，但我们是否可以修改它以检查给定半径的圆是否在多边形内？我想这是可能的，因为圆实际上就是一个更大的点，但我仍然没有成功...

- Savail

---

从几何角度来看，圆形绝对不仅仅是“一个点但更大”。一个点没有维度，而圆形有两个。你的问题有些类似于光线追踪中的“光线-球体相交”测试，其中多边形边缘类似于光线 - 试着看看那个。 - Alnitak

目前我正在处理圆相交和分别位于内部的情况。我只是好奇是否可以以某种方式扩展此方法以同时涵盖两种情况。但我必须承认，我的说法“圆就像一个点”有点幼稚... - Savail

我认为这个问题的答案可能取决于你的多边形是否保证是凸包。啊，我在问题中看到你已经这样说了...嗯。 - Alnitak

Answer 1

我可以想到两种方法：

第一种方法：
1）计算圆心到每条边和每个顶点的距离，找到最小和最大距离，分别表示为Dmin和Dmax。
2）使用insidePolygon()函数检查圆心是否在多边形内。
3）如果（R > Dmax），则圆包围多边形。
如果（Dmin < R < Dmax），则圆与多边形相交。
如果（R < Dmin && 圆心在多边形内），则圆在多边形内。
如果（R < Dmin && 圆心在多边形外），则圆在多边形外。

我必须承认，这与insidePolygon()使用的原始算法几乎没有关系。

第二种方法：
将多边形向内偏移距离=圆半径。如果结果多边形仍然是有效的多边形（即不自交）并且保持相同的顶点遍历方向，请检查圆心是否在偏移多边形内。如果是，则圆在原始多边形内。

第二种方法更符合原始算法，因为它通过偏移多边形使圆缩小到一个点。但从实现角度来看，第一种方法可能更容易。

- fang

Answer 2

有很多数学方法可以实现它，但我使用的方法是使用Area类。从性能角度来看，这可能不是最有效的方法，但速度对我的需求来说已经足够快了，而且由于我不是数学高手，没有数学部分是一个加分项 :)

public bool polygonContains circle (Shape poly, Shape circle){
    Area p = new Area(poly);
    if (!p.contains(circle.center)) return false;
    Area a = new Area(poly);        
    Area c = new Area(circle);
    a.add(c);
    //get the pathiterator of a and one for area p and compare the points they return
    // if there is a point in a not in p, it means circle jets out of polygon so return false.
    //if you care about the circle touching the inside of the polygon then 
    Area m = new Area(poly);
    Area s = m.substract(c);
    //repeat the pathiterator comparison for p and s , if there is a point in s not found in a
    //it means the circle touched the edge of the polygon return the value you see fit.
    return true;
}

- JTMon