Как определить наличие точки внутри полигона?

Question

[Кирилл Кудрявцев]

Есть два полигона, нужно определить находится ли точка в полигоне или нет.
В данный момент сделано что бы определить находится точка или нет в простом полигоне (без перекрытия самого себя). Как можно определить находится ли точка при перекрытии самого себя, средставми numpy/matplot.

Создание полигонов:

from matplotlib.patches import Polygon
polygons = [
    {
        'label': 'first',
        'cors': [
            [0.85157715, 0.53259596],
            [0.47351539, 0.78381185],
            [0.63767088, 0.07172642]
        ]
    },
    {
        'label': 'second',
        'cors': [
            [0.82024332, 0.60039117],
            [1, 1.80039117],
            [1.19215456, 0.62590895],
            [1.4, 0.81912354],
            [0.83599825, 1.12872215]
        ]
    }
]
for poly in polygons:
    polygon = Polygon(poly['cors'], False)
    polygon.set_label(poly['label'])
    patches.append(polygon)

Пример вывода

Comments

[AlphaSomeone]

Можно через pillow. Как-то так:

import pygame, PIL.Image
pygame.init()

def collidepointInPolygon(point_pos, polygon_pos):
    start = time.time()
    a = pygame.Surface(size=(point_pos[0] + 1, point_pos[1] + 1))
    a.fill((0, 0, 0))
    pygame.draw.polygon(a, (255, 255, 255), polygon_pos)
    a = pygame.image.tostring(a, "RGB")
    a = PIL.Image.frombytes("RGB", (point_pos[0] + 1, point_pos[1] + 1), a)
    a = a.getpixel((point_pos[0], point_pos[1])) == (255, 255, 255)
    
    return a

collidepointInPolygon([0, 0], [[100, 100], [200, 200], [200, 100]])

Answer 1

[d0lph1n]

https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...
https://habr.com/post/301102/
https://habr.com/post/125356/

Answer 2

[Karpion]

Проведём из нашей точки прямые линии ко всем вершинам полигона. Теперь пойдём по всем вершинам полигона по очереди.
Если точка внутри полигона - то мы сделаем полный круг. Если снаружи - то пойдём сначала вправо, потом влево (ну или наоборот) и так вернёмся обратно, не описав круга.

В общем случае - количество оборотов вокруг внутренней точки будет нечётным: ...,-3,-1,1,3,...
А если точка снаружи - то число оборотов будет чётным: -4,-2,0,2,4,...

Там надо будет суммировать углы. Лучше всего вычислить синус угла - через векторное произведение векторов и взять от него арксинус: при этом чётко определяется и знак угла. При суммировании плавающих числе могут накапливаться ошибки.

Answer 3

[Вадим Шаталов]

https://github.com/Toblerity/Shapely