如何确定点是否在2D凸多边形内？
我有一个凸多边形（通常只是一个旋转的方形），我知道所有4个点。 如何确定给定点（黄色/绿色）是否在多边形内？
编辑：对于这个特定的项目，我无法访问JDK的所有库，例如AWT。
此页面： 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; ... }
对于那些想要了解Dean Povey编写的方法如何工作的人，这里是解释：
该方法查看从测试点开始的“射线”，并延伸到X轴右侧的无穷大。 对于每个多边形线段，它会检查光线是否穿过它。 如果段交叉的总数是奇数，那么测试点被认为是在多边形内部，否则 – 它在外面。
要了解计算交叉的方式，请考虑下图：
v2 o / / c (intersection) o--------x----------------------> to infinity t / / / o v1
对于要发生的交集，tests.y必须在段的顶点（v1和v2）的y值之间。 这是方法中if语句的第一个条件。 如果发生这种情况，那么水平线必须与段相交。 它只是确定交叉点是在测试点的右侧还是在测试点的左侧。 这需要找到交点的x坐标，即：
ty - v1.y cx = v1.x + ----------- * (v2.x - v1.x) v2.y - v1.y
还有待完成的是检查细微之处：
- 如果v1.y == v2.y则光线沿着该段传播，因此该段对结果没有影响。 实际上，if语句的第一部分在这种情况下返回false。
- 代码首先相乘，然后才分开。 这样做是为了支持v1.x和v2.x之间的非常小的差异，由于四舍五入，这可能导致除法后的零。
- 最后，应该解决在顶点上精确交叉的问题。 考虑以下两种情况：
oo | \ o | A1 C1 \ / | \ / C2 o--------x-----------x------------x--------> to infinity / / \ A2 / B1 / \ B2 / / \ o / o o
现在，要validation它是否有效，请检查方法体中if条件为每个4段返回的内容。 您应该会发现光线上方的线段（A1，C1，C2）会收到一个阳性结果，而低于它的线圈（A2，B1，B2）会收到负值。 这意味着A顶点为交叉计数提供奇数（1），而B和C提供偶数（分别为0和2），这正是所需的。 A确实是多边形的真正交叉，而B和C只是两个“飞越”的情况。
假设您的点位于Y坐标y，只需计算每个多边形（非水平）线与y交叉的x位置。 计算小于点的x位置的x位置数。 如果x位置的数量是奇数，则您的点在多边形内。 注意：这适用于所有多边形，而不仅仅是凸面。 可以这样想：从无限遥远的地方画一条直线到你的观点。 当该线穿过多边形线时，它现在位于多边形内。 在外面再次越线。 再次交叉，内部（等等）。 希望这可以帮助！
如果使用Polygon对象表示多边形，则java.awt.Polygon类有许多contains(...)方法。
只是从@Dean Povey建议的代码中添加原始代码的（简单）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规则以显示所需的最小更改。 我也在简单的情况下测试它，它工作正常。
检查它是否位于由包含构成四边形边的线段的线所定义的4个半平面的同一侧。
这是一个很好的解释。
比如，x []是x点的数组，y []是y点的数组。
如果点存在于多边形中，则返回1，否则返回2。 其中（planeX，planeY）是您需要检查的点。
//check like this return new Polygon(x,y,x.length).contains(planeX, planeY)?1:2;
Polygon的横坐标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)