java 如何确定一个点是否在二维凸多边形内?

nzk0hqpo  于 2022-12-21  发布在  Java
关注(0)|答案(9)|浏览(118)

我有一个凸多边形(通常只是一个旋转的正方形),我知道所有的4个点。我如何确定一个给定的点(黄色/绿色)是否在多边形内?

编辑:对于这个特定的项目,我不能访问JDK的所有库,比如AWT。

qpgpyjmq

qpgpyjmq1#

本页:http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html显示了如何对任何多边形执行此操作。
我有一个Java实现,但是它太大了,不能完整地贴在这里。不过,你应该可以解决它:

class Boundary {
    private final Point[] points; // Points making up the boundary
    ...

    /**
     * Return true if the given point is contained inside the boundary.
     * See: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
     * @param test The point to check
     * @return true if the point is inside the boundary, false otherwise
     *
     */
    public boolean contains(Point test) {
      int i;
      int j;
      boolean result = false;
      for (i = 0, j = points.length - 1; i < points.length; j = i++) {
        if ((points[i].y > test.y) != (points[j].y > test.y) &&
            (test.x < (points[j].x - points[i].x) * (test.y - points[i].y) / (points[j].y-points[i].y) + points[i].x)) {
          result = !result;
         }
      }
      return result;
    }
}

下面是Point类的草图

/**
 * Two dimensional cartesian point.
 */
public class Point {
  public final double x;
  public final double y;
  ...
}
at0kjp5o

at0kjp5o2#

对于那些想了解上面波维院长写的方法是如何工作的人,这里有一个解释:
该方法查看从测试点开始并向X轴右侧无限延伸的“射线”。对于每个多边形段,它检查射线是否穿过它。如果穿过段的总数为奇数,则测试点被视为多边形内部,否则-它位于多边形外部。
要了解交叉的计算方式,请考虑下图:

v2
            o
           /
          / c (intersection)
o--------x----------------------> to infinity
t       /
       /   
      /
     o
     v1

要使相交发生,tested.y必须介于线段折点的y值之间(v1和v2)。这是方法中if语句的第一个条件。如果这是发生的事情,则水平线必须与线段相交,只需要确定相交是发生在被测点的右边还是左边。这需要找到交点的x坐标,即:

t.y - v1.y
c.x = v1.x + ----------- * (v2.x - v1.x)
             v2.y - v1.y

剩下要做的就是研究其中的微妙之处:

  • 如果v1.y == v2.y,那么光线沿着线段传播,因此线段对结果没有影响,事实上,在这种情况下if语句的第一部分返回false。
  • 代码先乘,然后再除。这样做是为了支持v1.x和v2.x之间非常小的差异,由于舍入,这可能导致除法后为零。
  • 最后,需要解决的是在顶点上精确相交的问题,考虑以下两种情况:
o                    o
         |                     \     o
         | A1                C1 \   /
         |                       \ / C2  
o--------x-----------x------------x--------> to infinity
        /           / \
    A2 /        B1 /   \ B2
      /           /     \ 
     o           /       o
                o

现在,要验证它是否工作,请自己检查方法体中if条件为4个线段中的每一个返回的值。(A1,C1,C2)接收正结果,而低于它的那些(A2,B1,B2)得到一个负1,这意味着A顶点贡献一个奇数(1)贡献给交叉计数,而B和C贡献偶数(分别为0和2),这正是所期望的。A确实是多边形的真实的交叉,而B和C只是“飞越”的两种情况。

68de4m5k

68de4m5k3#

假设你的点位于Y坐标y处,只需计算多边形的每条(非水平)线与y相交的x位置。计算小于你的点的x位置的x位置数。如果x位置数为奇数,则你的点位于多边形内部。注意:这适用于所有多边形,不仅仅是凸多边形。2这样想吧:从无限远的地方画一条直线到你的点。2当这条直线穿过多边形线时,它现在在多边形里面。3再穿过这条线,在外面。4再穿过,在里面(以此类推)。5希望这对你有帮助!

c6ubokkw

c6ubokkw4#

如果使用Polygon对象表示多边形,则java.awt.Polygon类具有许多contains(...)方法。

cbjzeqam

cbjzeqam5#

只是为了添加code suggested by @Dean Povey中C语言原始代码的一个(简单)Java实现(我不知道为什么@Dean Povey指的是一个大型实现):

static boolean pnpoly(double[] vertx, double[] verty, double testx, double testy)
{
    int nvert = vertx.length;
    int i, j;
    boolean c = false;
    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) &&
                (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
            c = !c;
    }
    return c;
}

我没有改变案例以符合Java规则,以显示所需的最小更改。我也在简单的案例中测试过它,它工作得很好。

zte4gxcn

zte4gxcn6#

检查它是否位于4个半平面的同一侧,这4个半平面由包含构成四边形各侧的线段的直线定义。
Here是一个很好的解释。

juud5qan

juud5qan7#

假设x[]是x点的数组,y[]是y点的数组。
如果点存在于多边形中,则返回1,否则返回2。其中(planeX,planeY)是需要检查的点。

//check like this
return new Polygon(x,y,x.length).contains(planeX, planeY)?1:2;
4bbkushb

4bbkushb8#

多边形横坐标x_array: Array[Integer]
多边形纵坐标:y_array: Array[Integer]
点:x: Integer, y: Integer

import java.awt.Polygon
import java.awt.Point
...

final boolean isInPolygon = 
    new Polygon(x_array,y_array,x_array.length).contains(new Point(x, y));

在这个例子中,我们创建了一个对象java.awt.Polygon,并使用contains方法来检查坐标是否在您设计的形状中。
我使用对象java.awt.Point来表示坐标,以使代码简洁,但这是可选的,您可以直接使用.contains(x, y)

ljsrvy3e

ljsrvy3e9#

许多答案都是基于交集的。这里有一个简单的算法,它不基于交集,而只使用向量积。这个方法比基于交集的方法简单,但只适用于凸多边形。由于问题是关于凸多边形的,所以应该首选这个简单的方法。
假设你的凸多边形(P0,P1,...,Pn),其中(Pi-1,Pi)是它的线段,是一个指针时钟,你要检查的点C在时钟内部。(Pi)要么顺时针转动,要么逆时针转动,想象一根针连在C上,顺时针转动时给出小时,向量CP 0 →,CP 1 →,CP 2 →,CP...... →,CPn→都是顺时针或逆时针旋转的,这意味着向量积CP 0 → CP 1 →、CP 1 → CP 2 →、CP 2 → CP... →、CPn-1→ CPn→和CPn→ CP 0 →都有相同的符号,这个性质只有当C在多边形内部时才会发生。

相关问题