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;
...
}
9条答案
按热度按时间qpgpyjmq1#
本页:http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html显示了如何对任何多边形执行此操作。
我有一个Java实现,但是它太大了,不能完整地贴在这里。不过,你应该可以解决它:
下面是Point类的草图
at0kjp5o2#
对于那些想了解上面波维院长写的方法是如何工作的人,这里有一个解释:
该方法查看从测试点开始并向X轴右侧无限延伸的“射线”。对于每个多边形段,它检查射线是否穿过它。如果穿过段的总数为奇数,则测试点被视为多边形内部,否则-它位于多边形外部。
要了解交叉的计算方式,请考虑下图:
要使相交发生,tested.y必须介于线段折点的y值之间(v1和v2)。这是方法中if语句的第一个条件。如果这是发生的事情,则水平线必须与线段相交,只需要确定相交是发生在被测点的右边还是左边。这需要找到交点的x坐标,即:
剩下要做的就是研究其中的微妙之处:
现在,要验证它是否工作,请自己检查方法体中if条件为4个线段中的每一个返回的值。(A1,C1,C2)接收正结果,而低于它的那些(A2,B1,B2)得到一个负1,这意味着A顶点贡献一个奇数(1)贡献给交叉计数,而B和C贡献偶数(分别为0和2),这正是所期望的。A确实是多边形的真实的交叉,而B和C只是“飞越”的两种情况。
68de4m5k3#
假设你的点位于Y坐标y处,只需计算多边形的每条(非水平)线与y相交的x位置。计算小于你的点的x位置的x位置数。如果x位置数为奇数,则你的点位于多边形内部。注意:这适用于所有多边形,不仅仅是凸多边形。2这样想吧:从无限远的地方画一条直线到你的点。2当这条直线穿过多边形线时,它现在在多边形里面。3再穿过这条线,在外面。4再穿过,在里面(以此类推)。5希望这对你有帮助!
c6ubokkw4#
如果使用Polygon对象表示多边形,则
java.awt.Polygon
类具有许多contains(...)
方法。cbjzeqam5#
只是为了添加code suggested by @Dean Povey中C语言原始代码的一个(简单)Java实现(我不知道为什么@Dean Povey指的是一个大型实现):
我没有改变案例以符合Java规则,以显示所需的最小更改。我也在简单的案例中测试过它,它工作得很好。
zte4gxcn6#
检查它是否位于4个半平面的同一侧,这4个半平面由包含构成四边形各侧的线段的直线定义。
Here是一个很好的解释。
juud5qan7#
假设x[]是x点的数组,y[]是y点的数组。
如果点存在于多边形中,则返回1,否则返回2。其中(planeX,planeY)是需要检查的点。
4bbkushb8#
多边形横坐标
x_array: Array[Integer]
多边形纵坐标:
y_array: Array[Integer]
点:
x: Integer, y: Integer
在这个例子中,我们创建了一个对象
java.awt.Polygon
,并使用contains方法来检查坐标是否在您设计的形状中。我使用对象
java.awt.Point
来表示坐标,以使代码简洁,但这是可选的,您可以直接使用.contains(x, y)
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在多边形内部时才会发生。