如何檢查一個圓是否位於凸多邊形的內部

我想檢查一個圓是相交還是位於凸多邊形的內部。我發現了一個輝煌的方法來檢測一個點是多邊形內（從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

如何檢查一個圓是否位於凸多邊形的內部

回答

相關問題