如何检查一个圆是否位于凸多边形的内部

我想检查一个圆是相交还是位于凸多边形的内部。我发现了一个辉煌的方法来检测一个点是多边形内（从here）：如何检查一个圆是否位于凸多边形的内部

 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; 
     }

这完全适用于单点，但有什么办法，我们可以修改这个检查，如果有一个圆给定的半径是在多边形内？我想这是可能的，因为一个圆实际上是一个点，但更大，但我还没有设法取得成功......

来源

2014-09-06 Savail

几何上圆是重点**不**只是“一个点，但更大”。一个点有零维，一个圆有两个维。你的问题有点类似于光线追踪“射线球面相交”测试，其中多边形边缘类似于射线 - 尝试着看。 – Alnitak 2014-09-06 14:48:56

目前我正在处理圆圈相交并且分别位于内侧的情况。我只是好奇，如果这种方法可以以某种方式扩展到一次覆盖两种情况。但我必须承认，我的说法“圈子就像一个点”有点幼稚...... – Savail 2014-09-06 14:59:59

我认为这可能取决于你的多边形是否保证是凸包或不。啊 - 我看到你在问题中这么说......嗯。 – Alnitak 2014-09-06 15:08:40

有很多方法可以做数学计算，但我做的方法是使用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; 
}

来源

2014-09-06 15:23:44 JTMon

我能想到的两种方法可以做到这一点：

第一种方式：从圆的中心到每个边缘
1）计算距离和每一个顶点，并找到最小和最大距离，分别表示为Dmin和Dmax。
2）使用insidePolygon（）函数检查圆的中心是否位于多边形内部。 3）如果（R> Dmax），则圆包围多边形。
如果（Dmin < R < Dmax），那么该圆与该多边形相交。
if（R < Dmin & &圆心位于多边形的内部），则圆是多边形的内部。
if（R < Dmin & &圆心位于多边形之外），则圆是多边形的外部。

我不得不承认，这几乎与insidePolygon（）使用的原始算法无关。

第二种方式：
向内偏移多边形的距离=圆的半径。如果生成的多边形仍然是有效的多边形（即，不是自相交）并且保持相同的顶点横切方向，请检查圆的中心是否位于偏移多边形内。如果是，则该圆在原始多边形内。

第二种方法与原始算法更接近，因为它将向内偏移了圆的半径量，因此实际上减少了回到一个点的圆。但是，实施方面，第一种方法可能更容易。

来源

2014-09-07 20:18:15 fang

如何检查一个圆是否位于凸多边形的内部

回答

相关问题