Как определить, находится ли точка внутри двумерного выпуклого многоугольника?

Question

У меня выпуклый многоугольник (обычно это просто повернутый квадрат), и я знаю все 4 точки. Как определить, является ли данная точка (желтая / зеленая) внутри многоугольника?

РЕДАКТИРОВАТЬ: Для этого конкретного проекта у меня нет доступа ко всем библиотекам JDK, например, AWT.

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;
  ...
}

Answer 2

Для тех, кто хотел бы понять, как работает метод, написанный Дином Пови выше, вот объяснение:

Метод смотрит на «луч», который начинается в тестируемом месте и простирается до бесконечности справа.оси XДля каждого сегмента полигона он проверяет, пересекает ли его луч.Если общее количество пересечений сегмента нечетное, то проверяемая точка считается внутри многоугольника, в противном случае - снаружи.

Чтобы понять, как рассчитывается пересечение, рассмотрим следующий рисунок:

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

Для того, чтобы произошло пересечение, tests.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

Теперь, чтобы проверить, работает ли он, проверьте сами, что возвращается для каждого из 4 сегментов условием if в теле метода.Вы должны обнаружить, что сегменты выше луча (A1, C1, C2) получают положительный результат, а сегменты ниже него (A2, B1, B2) - отрицательный.Это означает, что вершина A добавляет нечетное число (1) к счету пересечений, в то время как B и C дают четное число (0 и 2 соответственно), что является именно тем, что требуется.A действительно является реальным пересечением многоугольника, в то время как B и C являются всего лишь двумя случаями «пролета».

Answer 3

Предполагая, что ваша точка находится в координате Y, просто вычислите позиции х, где каждый (не горизонтальные) линии многоугольника пересекают у. Подсчитайте количество позиций х, которые меньше, чем позиция х вашей точки. Если количество позиций х нечетно, ваша точка внутри многоугольника. Примечание: это работает для всех многоугольников, а не только для выпуклых. Думайте об этом так: Нарисуйте линию от бесконечно далеко прямо к вашей точке. Когда эта линия пересекает линия многоугольника, теперь она внутри многоугольника. Пересеките линию снова, снаружи. Крест снова, внутри (и пр.). Надеюсь, это поможет!

Answer 4

Класс java.awt.Polygon имеет несколько методов contains(...), если вы используете Polygon объекты для представления вашего полигона.

Answer 5

Просто чтобы добавить (простую) реализацию Java исходного кода на C из кода, предложенного @Dean Povey (я не знаю, почему @Dean Povey ссылается на большую реализацию): 1003 *

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, чтобы показать минимальные требуемые изменения. Я также проверил его в простых случаях, и он отлично работает.

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;

Answer 7

Проверьте, находится ли он на той же стороне 4-х полуплоскостей, определенных линиями, которые содержат отрезки, составляющие стороны четырехугольника.

Здесь - этохорошее объяснение.

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 и используем метод содержит, чтобы проверить, находятся ли ваши координаты в форме, которую вы разработали.

Я использую объект java.awt.Point для представления координат, чтобы сделать код элегантным, но это необязательно, вы можете напрямую использовать .contains(x, y)