指向二维多边形内

Question

下面的一段 java 代码是确定 2D 点是否在多边形内的解决方案（摘自 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);

它 returns 对于 (76,82) 是正确的（内部），但是这个点在边缘上（代码 returns false 对于边缘上的另一个点是正确的：（45,17）） . 对于 (45,90) 也是 returns false（不在内部），但它在多边形内部。有什么问题？

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

Answer 1

这个算法

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

打印出错误。

指向二维多边形内

Point inside a 2D Polygon

java

point-in-polygon