點在二維多邊形內

下面的一段java代碼是確定二維點是否在多邊形內的解決方案（取自here）。我認爲這段代碼有一些問題。例如，對於這個多邊形：點在二維多邊形內

Point[] polygon = new Point[5]; 
polygon[0] = new Point(30,20); 
polygon[1] = new Point(80,10); 
polygon[2] = new Point(75,100); 
polygon[3] = new Point(40,100); 
polygon[4] = new Point(55,65);

它返回true（內部）爲（76,82），但這點在邊緣（代碼返回false正確的邊上另一點：（45,17））。另外它返回false（不在裏面）（45,90），但它在多邊形內。問題是什麼？

public boolean IsPointInPolygon(Point p, Point[] polygon) 
{ 
    double minX = polygon[0].x; 
    double maxX = polygon[0].x; 
    double minY = polygon[0].y; 
    double maxY = polygon[0].y; 
    for (int i = 1 ; i < polygon.length; i++) 
    { 
     Point q = polygon[i]; 
     minX = Math.min(q.x, minX); 
     maxX = Math.max(q.x, maxX); 
     minY = Math.min(q.y, minY); 
     maxY = Math.max(q.y, maxY); 
    } 

    if (p.x <= minX || p.x >= maxX || p.y <= minY || p.y >= maxY) 
    { 
     return false; 
    } 

    boolean inside = false; 
    int j = polygon.length - 1; 
    for (int i = 0 ;i < polygon.length ; j = i++) 
    { 
     if ((polygon[i].y > p.y) != (polygon[j].y > p.y) && 
       p.x <= (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y)/(polygon[j].y - polygon[i].y) + polygon[i].x) 
     { 
      inside = !inside; 
     } 
    } 
    return inside; 
}

我想我應該我的代碼更改爲以下，但我不知道！

float tempX = ((float)((polygon[i].x - polygon[j].x) * (p.y - polygon[i].y))/(polygon[i].y - polygon[j].y)) + polygon[i].x; 
if (p.x < tempX) { 
    inside = !inside; 
} 
else if (p.x == tempX) { 
    return false; 
}

來源

2017-08-13 hamed

我建議你逐行使用調試器和步驟，直到找到不符合你想法的操作。 – user1803551

（1）鏈接頁面的作者寫道，對於邊緣點，結果是真或假。因此，您的前兩個測試用例的行爲是可以預料的。（2）您正在使用'p.x <= ...'，其中原始代碼使用'<'。（3）你是否嘗試在數組的最後重複第一點？作者寫道，你的情況是可選的，但我仍然會嘗試。 –

（2）我使用p.x <= ...因爲我的代碼在某些情況下不起作用，例如（45,17）（3）是的，我再重複一遍。 – hamed

該算法

if (p.x <= minX || p.x >= maxX || p.y <= minY || p.y >= maxY) 
{ 
     return false; 
}

是錯誤的。它只檢查點是否在一個矩形內，以minX, maxX, minY, maxY 爲界不能測試一個點是否在多邊形內而不使用所有的多邊形頂點。

使用java.awt.Polygon：

public boolean isPointInPolygon(Point p, Point[] points) 
    { 

     Polygon polygon = new Polygon();//java.awt.Polygon 

     for(Point point : points) { 

      polygon.addPoint(point.x, point.y); 
     } 

     return polygon.contains(p); 
    }

測試它與

Point[] points = new Point[5]; 
    points[0] = new Point(30,20); 
    points[1] = new Point(80,10); 
    points[2] = new Point(75,100); 
    points[3] = new Point(40,100); 
    points[4] = new Point(55,65); 

    System.out.println(isPointInPolygon(new Point(76,82), points));

打印出假的。

來源

2017-08-13 16:05:49 c0der

但是，您可以通過這種方式快速確定點在多邊形中不是**。例如，如果多邊形的所有頂點都具有「x」座標> = 0並且測試點的「x」座標爲-2，那麼肯定該點位於多邊形之外。 – Kirby

是的，我同意。 – c0der

這段代碼對邊上的點返回true，但我想返回false。 – hamed

點在二維多邊形內

回答

相關問題