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

У меня есть класс, описывающий точку (имеет 2 координаты x и y) и класс, описывающий многоугольник, который имеет список точек, которые соответствуют углам (self.corners). Мне нужно проверить, находится ли точка в многоугольнике

Вот функция, которая должна проверять, есть ли точка в многоугольнике. Я использую метод лучевого литья

def in_me(self, point):
        result = False
        n = len(self.corners)
        p1x = int(self.corners[0].x)
        p1y = int(self.corners[0].y)
        for i in range(n+1):
            p2x = int(self.corners[i % n].x)
            p2y = int(self.corners[i % n].y)
            if point.y > min(p1y,p2y):
                if point.x 
 martineau14 июл. 2014 г., 15:22
@Ulrich & Елена: разделение Python 3 можно включить в Python 2, используяfrom __future__ import division, Другой альтернативой является простоfloat() либо числитель или знаменатель (или термин в одном из них в данном случае).
 chepner18 мая 2013 г., 18:19
Еще лучше: не делайт делить на всех. Вместо вычисленийxinters, проверить, если(point.x - p1x)*(p2y-p1y)
 Armin Rigo18 мая 2013 г., 17:04
Может быть потому, что тыповторное использование "/" на целых числах, которое возвращает целое число (округленное в меньшую сторону). Вместо этого вы должны делать все вычисления с помощью float. Кроме того, если p1y == p2y, xinters не могут быть определены, но все еще используются только после этого.
 Helena18 мая 2013 г., 19:41
как бы с помощью(point.x - p1x)*(p2y-p1y)
 Ulrich Eckhardt18 мая 2013 г., 18:56
... или использовать Python 3, который необрезать до целых чисел при делении.

Ответы на вопрос(3)

Я бы предложил использоватьPath класс отmatplotlib

import matplotlib.path as mplPath
import numpy as np

poly = [190, 50, 500, 310]
bbPath = mplPath.Path(np.array([[poly[0], poly[1]],
                     [poly[1], poly[2]],
                     [poly[2], poly[3]],
                     [poly[3], poly[0]]]))

bbPath.contains_point((200, 100))

(Существует такжеcontains_points функция, если вы хотите проверить на несколько точек)

 P.R.11 февр. 2019 г., 13:07
bb означает ограничивающий прямоугольник, хотя многоугольник очень похож на прямоугольник :)
 Martin Burch06 мар. 2015 г., 17:54
Чтобы это работало, вы должны сначалаimport numpy as np
 Noah07 февр. 2019 г., 03:46
Почему имя переменной?bbPath»? if (делает 'бб» что-то сокращать?)бб» сокращайте?
 Maciek10 мар. 2018 г., 13:00
Что-то'неправильно, используя массив = [[100,100], [200,100], [200,200], [100,200], [100,100]], он дает False для точки 100,100 и true для точки 200,200
 Christophe Roussy11 июл. 2016 г., 10:18
Кто-нибудь проверял работоспособностьcontains_points против чистой реализации Python?

Итерация по всем сегментам в многоугольникеПроверьте, пересекаются ли они с лучом, идущим в направлении увеличения-x

С использованиемintersect функция отЭто ТАК Вопрос

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

def point_in_polygon(pt, poly, inf):
    result = False
    for i in range(len(poly.corners)-1):
        if intersect((poly.corners[i].x, poly.corners[i].y), ( poly.corners[i+1].x, poly.corners[i+1].y), (pt.x, pt.y), (inf, pt.y)):
            result = not result
    if intersect((poly.corners[-1].x, poly.corners[-1].y), (poly.corners[0].x, poly.corners[0].y), (pt.x, pt.y), (inf, pt.y)):
        result = not result
    return result

Обратите внимание, чтоinf Параметр должен быть максимальной точкой на оси х на вашей фигуре.

 h345k34cr04 июл. 2017 г., 14:35
Это неправильно, не так лиработать с точкой [2, 5] с многоугольником [8, 6], [11, 10], [16, 5], [11, 3]. Правка: Вероятно, проблема в том, что луч проходит непосредственно через точку многоугольник, вызывая переключение двух отрезков многоугольникаresult, возвращая его в прежнее состояние

Я хотел бы предложить некоторые другие изменения:

def contains(self, point):
    if not self.corners:
        return False

    def lines():
        p0 = self.corners[-1]
        for p1 in self.corners:
            yield p0, p1
            p0 = p1

    for p1, p2 in lines():
        ... # perform actual checks here

Заметки:

Многоугольник с 5 углами также имеет 5 ограничивающих линий, а не 6, ваш цикл один раз.Использование отдельного выражения генератора дает понять, что вы проверяете каждую строку по очереди.Добавлена проверка на пустое количество строк. Однако, как обрабатывать линии и многоугольники нулевой длины с одним углом, все еще открыто.Также рассмотрите возможность сделать функцию lines () нормальным членом вместо вложенной утилиты.Вместо множества вложенных структур if можно также проверить обратное, а затемcontinue или использовать.and

Ваш ответ на вопрос