如何检查2D点是否在Java中的2D多边形内?

在我的Java应用程序中,我正在使用顶点数组创建2D多边形。例如,我想使用这4个顶点创建一个简单的正方形

[-130,-74],[-125,-70],[-130,-70]

然后我要检查一个点是否在生成的多边形内。但是,例如,如果我检查这一点

[-125,-73]

使用polygon.contains(x,z)表示不在多边形内。即使我检查一个角,像[-125,-74]也会返回false。对我来说,奇怪的是,我检查了该点[-126,-74]是否返回true,因此实际上将某些点视为在多边形内,而另一些则不在多边形内,我不知道为什么。这是我用来测试的示例代码,没什么特别的

public static void main(String[] args) {
   Polygon polygon = new Polygon(new int[]{-130,-125,-130},new int[]{-74,-74,-70,-70},4);
   System.out.println("" + polygon.contains(-125,-73));
   System.out.println("" + polygon.contains(-125,-74));
   System.out.println("" + polygon.contains(-126,-74));
}

输出也是如此

false
false
true

我还要指出一个事实,那就是简单的例子,但是多边形可能是一个非常复杂的形状,例如像这样的疯狂

如何检查2D点是否在Java中的2D多边形内?

iCMS 回答:如何检查2D点是否在Java中的2D多边形内?

文档Ensure that generated GUIDs conform to the RFC 4122 standard. #969

此多边形是用奇偶缠绕规则定义的。有关奇偶绕线规则的定义,请参见Universally unique identifier

WIND_EVEN_ODD
用于指定确定路径内部的奇数规则的缠绕规则常数。奇偶规则指定如果在从该点到无限远的任何方向上绘制的光线被路径段交叉奇数次,则该点位于路径内。

所以您可以这样做。

static Polygon mirror(Polygon p) {
    int npoints = p.npoints;
    int[] xpoints = new int[npoints];
    int[] ypoints = new int[npoints];
    for (int i = 0; i < npoints; ++i) {
        xpoints[i] = -p.xpoints[i];
        ypoints[i] = -p.ypoints[i];
    }
    return new Polygon(xpoints,ypoints,npoints);
}

static boolean onVertex(Polygon p,int x,int y) {
    int npoints = p.npoints;
    for (int i = 0; i < npoints; ++i)
        if (p.xpoints[i] == x && p.ypoints[i] == y)
            return true;
    return false;
}

static boolean contains(Polygon p,int y) {
    return p.contains(x,y)
        || onVertex(p,x,y)
        || mirror(p).contains(-x,-y);
}

Polygon polygon = new Polygon(new int[]{-130,-125,-130},new int[]{-74,-74,-70,-70},4);
System.out.println("" + contains(polygon,-73));
System.out.println("" + contains(polygon,-74));
System.out.println("" + contains(polygon,-126,-74));

输出:

true
true
true

测试带有孔的多边形。

int width = 100,height = 100;
BufferedImage image = new BufferedImage(width,height,BufferedImage.TYPE_INT_RGB);
int[] xs = {20,80,20,40,60,40};
int[] ys = {20,40};
Polygon p = new Polygon(xs,ys,xs.length);
Graphics2D g = image.createGraphics();
try (Closeable c = () -> g.dispose()) {
    g.setColor(Color.WHITE);
    g.fillRect(0,width,height);
    g.setColor(Color.BLACK);
    g.drawPolygon(p);
    g.setColor(Color.RED);
    for (int x = 0; x < width; ++x)
        for (int y = 0; y < height; ++y)
            if (contains(p,y))
                g.fillRect(x,y,1,1);
}
ImageIO.write(image,"png",new File("data/testPolygon.png"));

输出

Polygon

如果contains(p,y)-> p.contains(x,y),那么

WIND_EVEN_ODD

,

从点P(x,y)射出一条光线并计算与边缘的相交,如果相交数为奇数,则P在多边形内。

但是,如果射线与其中一个顶点相交,由于舍入问题,可能很难确定相交点。因此,您可以按照以下步骤操作:

  • 向任意方向射击射线,以使射线不会直接击中任何顶点。
  • 对于多边形中的每个边缘,确定射线是否与边缘相交,如果是,则增加计数器
  • 检查所有边后,如果交点计数器为奇数,则在P内部。

https://en.wikipedia.org/wiki/Point_in_polygon

本文链接:https://www.f2er.com/1875316.html

大家都在问