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

Я предлагаю использовать matplotlib contains_points()

from matplotlib.path import Path

tupVerts=[(86, 52), (85, 52), (81, 53), (80, 52), (79, 48), (81, 49), (86, 53),
 (85, 51), (82, 54), (84, 54), (83, 49), (81, 52), (80, 50), (81, 48),
 (85, 50), (86, 54), (85, 54), (80, 48), (79, 50), (85, 49), (80, 51),
 (85, 53), (82, 49), (83, 54), (82, 53), (84, 49), (79, 49)]


x, y = np.meshgrid(np.arange(300), np.arange(300)) # make a canvas with coordinates
x, y = x.flatten(), y.flatten()
points = np.vstack((x,y)).T 

p = Path(tupVerts) # make a polygon
grid = p.contains_points(points)
mask = grid.reshape(300,300) # now you have a mask with points inside a polygon

Основываясь на ответе РемкоГерлиха, вот проверенная функция:

import numpy as np
import mahotas

def render(poly):
    """Return polygon as grid of points inside polygon.

    Input : poly (list of lists)
    Output : output (list of lists)
    """
    xs, ys = zip(*poly)
    minx, maxx = min(xs), max(xs)
    miny, maxy = min(ys), max(ys)

    newPoly = [(int(x - minx), int(y - miny)) for (x, y) in poly]

    X = maxx - minx + 1
    Y = maxy - miny + 1

    grid = np.zeros((X, Y), dtype=np.int8)
    mahotas.polygon.fill_polygon(newPoly, grid)

    return [(x + minx, y + miny) for (x, y) in zip(*np.nonzero(grid))]

Пример:

poly = [
    [0, 0],
    [0, 10],
    [10, 10],
    [10, 0]
]

plt.figure(None, (5, 5))
x, y = zip(*render(poly))
plt.scatter(x, y)
x, y = zip(*poly)
plt.plot(x, y, c="r")
plt.show()

Я думаю, что рисование многоугольника и его заполнение — хорошее начало, вам все равно понадобится что-то подобное, и эти алгоритмы обычно точно настроены в C. Но не используйте изображение RGB, используйте черно-белое изображение и используйте numpy.where(), чтобы найти пиксели, где это 1.

Согласно этому вопросу, в библиотеке mahotas есть функция fill_polygon, которая работает с массивами numpy.

Я начинаю следующий код из вашей функции (я бы тоже вычел minx и maxx), но обратите внимание, что я вообще не могу его протестировать, я не на своей машине разработки.

import numpy as np
import mahotas

def render(poly): # removed parameter 'z'
    xs = [i[0] for i in poly]
    ys = [i[1] for i in poly]
    minx, maxx = min(xs), max(xs)
    miny, maxy = min(ys), max(ys)
    X = maxx - minx + 1
    Y = maxy - miny + 1
    newPoly = [(x - minx, y - miny) for (x, y) in poly]           

    grid = np.zeros((X, Y), dtype=np.int8)
    mahotas.polygon.fill_polygon(newPoly, grid)

    return [(x + minx, y + miny) for (x, y) in np.where(grid)]

Вы можете использовать пустую матрицу, такую ​​как двоичное изображение, которое можно использовать, например, с Opencv или другими библиотеками обработки изображений, Решение 1. Итак, матрица размером L x H, где

L=max(x) - min (x)
H=max(y) - min (y)

В качестве записи у нас есть ваш список кортежей (x, y), которые вы указали выше, имя которых poly, например:

import numpy as np
matrix =np.zeros((L,H),dtype=np.int32) # you can use np.uint8 if unsigned x ,y

Итак, теперь у нас есть матрица размера L x H, заполненная 0, теперь мы помещаем 1 в позиции точек многоугольника.

Я думаю, вы можете просто сделать это

matrix[poly]=1  # which will put 1 at each (x,y) of the list **poly**

мы интерпретируем это как бинарное (черно-белое) изображение, на котором нарисован контур. Предположим, мы хотим обнаружить этот новый контур.

import cv2 # opencv import
ContoursListe,hierarchy = cv2.findContours(self.thresh,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_NONE)
poly2=ContoursListe[0] # we take the first only contour

Примечание: poly2 содержит список точек вашего многоугольника и всех точек, образующих его, я имею в виду все точки каждой вершины вашего многоугольника, что вам нужно, может оказаться полезным !! вы можете использовать параметр cv2.CHAIN_APPROX_SIMPLE, чтобы получить poly2, содержащий только конечные точки линий многоугольника, которые светлее и которые были введены нами :) важно: тип poly2 - numpy массив, его форма (n,1,2), а не (n,2)

Теперь нарисуем этот контур на этом изображении(матрице) и заполним и его :)

cv2.drawContours(matrix,[poly2],-1,(1),thickness=-1) thickness=-1

теперь у нас есть матрица, в которой есть 1 в каждой точке, формирующей и заполняющей многоугольник, "толщина = -1" заставила заполнить этот контур, вы можете установить толщину = 1, чтобы получить только границы если вы хотите перевести, вы можете сделать это, добавив параметр offset(xtran,ytrans)

чтобы получить индексы всех этих точек, просто позвоните

list_of_points_indices=numpy.nonzero(matrix)

Решение 2

Что умнее, так это напрямую преобразовать ваш список точек (poly) в формат контура (poly2) и нарисовать его на матрице.

poly2=poly.reshape(-1,1,2).astype(np.int32)

и нарисуйте его на матричной матрице

matrix =np.zeros((L,H),dtype=np.int32)

cv2.drawContours(matrix,[poly2],-1,(1),thickness=-1)

И получите список этих точек с помощью:

list_of_points_indices=numpy.nonzero(matrix)

Поэкспериментируйте с толщиной, чтобы заполнить или не заполнить многоугольник . Дополнительные сведения см. в решении 1.

Попробуйте этот код. poly_coords — это координаты вашего полигона, «coord» — это координаты точки, которую вы хотите проверить, находится ли она внутри полигона.

def testP(coord, poly_coords):
    """
    The coordinates should be in the form of list of x and y
    """
    test1 = n.array(poly_coords)
    test2 = n.vstack((poly_coords[1:], poly_coords[:1]))
    test  = test2-test1
    m = test[:,1]/test[:,0]
    c = test1[:,1]-m*test1[:,0]
    xval = (coord[1]-c)/m
    print 'xVal:\t'; print xval
    print (test1[:,0]-xval)*(test2[:,0]-xval)
    check = n.where((xval>=coord[0])&((test1[:,0]-xval)*(test2[:,0]-xval)<0))[0]
    print check
    print len(check)
    if len(check)%2==0:
        return False
    else:
        return True

Если вы хотите сделать это еще быстрее, удалите часть алгоритма, связанную с многоугольником, наклоном и смещением, и запустите остальную часть кода, используя функцию «карта». Что-то вроде этого:

test1 = n.array( your polygon)
test2 = n.vstack((test1[1:], test1[:1]))
test  = test2-test1
m = test[:,1]/test[:,0]
c = test1[:,1]-m*test1[:,0]

def testP(coord):
    """
    The coordinates should be in the form of list of x and y
    """
    global test, test1, test2, m,c
    xval = (coord[1]-c)/m
    check = n.where((xval>=coord[0])&((test1[:,0]-xval)*(test2[:,0]-xval)<0))[0]
    if len(check)%2==0:
        return False
    else:
        return True
coords = n.array(( your coords in x,y ))
map (testP, coords)

Вы можете удалить команды «печать», если хотите. Этот код сделан для Python 2.7.