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

Question

我有一个凸多边形（通常只是一个旋转的正方形），我知道所有4个点。如何确定给定的点（黄色/绿色）是否在多边形内部？

编辑：对于这个特定的项目，我没有访问JDK的所有库，例如AWT。

- NPike

---

您的标题是不是应该是“凸优化”？ - Kavka

您可以使用 java.awt 库中的多边形和点：new Polygon(x_coordinates, y_coordinates, coordinates.length).contains(new Point(x, y))，其中 x_coordinates 和 y_coordinates 的类型为 Array[Integer]。 - Seraf

Answer 1

这个页面：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

---

你能解释一下 (points[i].y > test.y) != (points[j].y > test.y) 这部分的含义吗？ - Seraf

它确保points[i].y和points[j].y不在test.y的同一侧。 - Dean Povey

看起来这适用于凸多边形和凹多边形？OP 仅要求凸多边形，这应该会产生更快的算法。 - Rodrigo

是的，你说得对。对于凸多边形，可以按逆时针顺序计算点与每条边的方向。如果所有边的方向都在左侧（方向为正/顺时针），则它在内部。方向可以根据以下公式计算：(y2 - y1)(x3 - x2) - (y3 - y2)(x2 - x1)。如果为0，则点共线，如果为正，则点定向顺时针，如果为负，则定向逆时针。 - Dean Povey

数组中的点必须按顺序排列吗？ - jpell

Answer 2

For those who would like to understand how the method written by Dean Povey above works, here is the explanation:

The method looks at a "ray" that starts at the tested spot and extends to infinity to the right side of the X axis. For each polygon segment, it checks if the ray crosses it. If the total number of segment crossing is odd then the tested point is considered inside the polygon, otherwise - it is outside.

To understand the way the crossing is calculated, consider the following figure:

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

For the intersection to occur, tested.y must be between the y values of the segment's vertices (v1 and v2). This is the first condition of the if statement in the method. If this is what happens, then the horizontal line must intersect the segment. It only remains to establish whether the intersection happens to the right of the tested point or to the left of it. This requires finding the x coordinate of the intersection point, which is:

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

All that remains to be done is examining the subtleties:

• If v1.y == v2.y then the ray goes along the segment and therefore the segment has no influence on the outcome. Indeed, the first part of the if statement returns false in that case.
• The code first multiplies and only then divides. This is done to support very small differences between v1.x and v2.x, which might lead to a zero after the division, due to rounding.
• Finally, the problem of crossing exactly on a vertex should be addressed. Consider the following two cases:

         o                    o
         |                     \     o
         | A1                C1 \   /
         |                       \ / C2  
o--------x-----------x------------x--------> to infinity
        /           / \
    A2 /        B1 /   \ B2
      /           /     \ 
     o           /       o
                o

Now, to verify if it works, check for yourself what is returned for each of the 4 segments by the if condition in the method body. You should find that the segments above the ray (A1, C1, C2) receive a positive result, while those below it (A2, B1, B2) receive a negative one. This means that the A vertex contributes an odd number (1) to the crossing count, while B and C contribute an even number (0 and 2, respectively), which is exactly what is desired. A is indeed a real crossing of the polygon, while B and C are just two cases of "fly-by".

- Nadav

---

好的艺术作品和解释！+1 :) - Márkó Invasion

Answer 3

假设您的点位于Y坐标y处，只需计算每个多边形（非水平）线段穿过y时的x位置。计算小于您点的x位置数量。如果x位置数量为奇数，则您的点在多边形内部。注意：这适用于所有多边形，而不仅仅是凸多边形。可以这样想：从无限远的地方画一条直线到您的点，当该线穿过多边形线时，它就在多边形内部。再次穿过该线，就在外面。再穿过，就在内部（等等）。希望这能帮到您！

- Jim

---

顺便说一下，这就是Dean Povey的回答在做什么。 - Jim

是的，但这是一个不错的解释 :-) - Dean Povey

Answer 4

如果您使用Polygon对象来表示您的多边形，那么java.awt.Polygon类有许多contains(...)方法可供使用。

- Kavka

Answer 5

这里提供一个简单的Java实现，原始代码来自C语言版本的@Dean Povey的建议（我不知道为什么@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规则，只是为了展示所需的最小更改。我还在简单情况下测试过它，它可以正常工作。

- Eypros

Answer 6

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

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

- Apoorva Ambhoj

Answer 7

检查它是否在由包含四边形边缘线段的直线定义的 4 个半平面的同一侧。

这里 是一个很好的解释。

- user1118321

Answer 8

多边形的横坐标：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)。

- Seraf

Answer 9

许多答案都基于交点。这里有一个简单的算法，不基于交点，只使用向量积。 这种方法比基于交点的方法更简单，但只适用于凸多边形。由于问题是关于凸多边形的，应该优先选择这种更简单的方法。

想象一下，你的凸多边形（P0，P1，...，Pn），其中（Pi-1，Pi）是它的线段，就像一个指针时钟，而你要检查的点C在时钟内部。点（Pi）要么顺时针转动，要么逆时针转动。想象一个连接到C的指针，当顺时针转动时，它会给出小时数。向量CP0→，CP1→，CP2→，CP...→，CPn→都会顺时针或逆时针转动。这意味着向量积CP0→⨯CP1→，CP1→⨯CP2→，CP2→⨯CP...→，CPn-1→⨯CPn→和CPn→⨯CP0→的方向都相同。由于它们也共线，它们的方向由两两取出的标量积的符号来定义。 只有当C在多边形内部时，才会出现这种属性。因此，如果向量积的标量积的符号是恒定的，那么C就在多边形内部。

- Alexandre Fenyo