Punkt in einem 2D-Polygon

Question

Der folgende Teil des Java-Codes ist eine Lösung, um zu bestimmen, ob ein 2D-Punkt innerhalb eines Polygons liegt oder nicht (aus here). Ich denke, dieser Code hat einige Probleme. Zum Beispiel für dieses Polygon:

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

Es true zurück (innen) für (76,82), aber dieser Punkt ist auf dem Rand (-Code false zurück richtig für einen anderen Punkt auf der Kante (45,17)) . Auch gibt es falsch (nicht innerhalb) für (45,90) zurück, aber es ist innerhalb des Polygons. Was ist das Problem?

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

---

Ich glaube, ich sollte meinen Code unten ändern, aber ich bin mir nicht sicher!

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

Answer 1

Dieser Algorithmus

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

ist falsch. Es wird nur überprüft, ob der Punkt innerhalb eines durch minX, maxX, minY, maxY begrenzten Rechtecks ​​liegt. Sie können nicht testen, ob ein Punkt innerhalb eines Polygons liegt, ohne alle Polygonscheitelpunkte zu verwenden.

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

Testing mit

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

druckt falsch.