I searched a lot and cant find any practical answer to my question. I have a polygon. For example:
我找了很多，找不到任何实际的答案来回答我的问题。我有一个多边形。例如:
[(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)]
I want to get a list of all the points inside this border polygon. I heard alot about polygon triangulation techniques or linear/flood/intersection/... filling algorithms. but i cant really come up with an efficient way of implementing this. This poly is small, imagine a polygon with 1 billion points. I am now using PIL draw polygon to fill the poly with red color and loop inside it to find red points. This is a horribly slow technique:
我想要得到这个边界多边形内所有点的列表。我听过很多关于多边形三角剖分技术或线性/洪水/交叉点/…填充算法。但是我真的不能想出一个有效的方法来实现它。这个多边形很小，想象一个有10亿个点的多边形。我现在用PIL绘制多边形来填充红色的多边形，并在里面循环找到红色的点。这是一个非常缓慢的技术:
def render(poly, 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 polygons]
i = Image.new("RGB", (X, Y))
draw = ImageDraw.Draw(i)
draw.polygon(newPoly, fill="red")
# i.show()
tiles = list()
w, h = i.size
print w, h
for x in range(w):
for y in range(h):
data = i.getpixel((x, y))
if data != (0, 0, 0):
tiles.append((x + minx, y + miny))
return tiles
I am searching for a Pythonic way of solving this problem. Thank you all.
我正在寻找一个解决这个问题的python方法。谢谢大家。
5 个解决方案
#1
4
I suggest to use matplotlib contains_points()
我建议使用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
#2
2
I think drawing the polygon and filling it is a good start, you're going to need something like that anyway and those algorithms are usually fine tuned in C. But don't use a RGB image, use a black/white image, and use numpy.where() to find the pixels where it's 1.
我认为绘制多边形并填充它是一个很好的开始，无论如何，您都需要这样的东西，而且这些算法通常在c中得到很好的调优，但是不要使用RGB图像，使用黑白图像，并使用numpi .where()来找到像素的1。
According to this question, the mahotas library has a fill_polygon function that works with numpy arrays.
根据这个问题，mahotas库有一个fill_polygon函数，它与numpy数组一起工作。
I'm starting the following code from your function (I would subtract the minx and maxx too) but note that I can't test it at all, I'm not on my dev machine.
我正在从您的函数中启动以下代码(我也要减去minx和maxx)，但是请注意，我根本不能测试它，我不在我的开发机器上。
import numpy as np
import mahotas
def render(poly, 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 polygons]
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)]
#3
2
You can use a numpy matrix like a binary image, which can be used with Opencv for example or other image processing libs, Solution 1 So a matrix which size is L x H where
你可以使用一个numpy矩阵像一个二进制图像，它可以用于Opencv例如其他图像处理libs，解决方案1，一个大小为lxh的矩阵
L=max(x) - min (x)
H=max(y) - min (y)
As entry we have your list of tuple(x,y) you gave above which name is poly for example :
作为条目，我们有你在上面给出的tuple(x,y)的列表，例如:
import numpy as np
matrix =np.zeros((L,H),dtype=np.int32) # you can use np.uint8 if unsigned x ,y
So we have now a matrix of Size L x H filled with 0, we put now 1 at polygon points positions
现在我们有一个大小为lxh的矩阵，填充为0，我们现在把1放在多边形点的位置上
I think you can simple do that
我觉得你可以这么做
matrix[poly]=1 # which will put 1 at each (x,y) of the list **poly**
we interpret this as a binary (black/white) image which have a contour drawn on it Assume we want to detect this new contour
我们将它解释为一个带有轮廓的二进制(黑白)图像，假设我们想要检测这个新的轮廓
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
Note : poly2 is containing a list of points of your polygon and all points forming it, i mean all points of each vertices of your polygon which is what you need can find useful !! you can use cv2.CHAIN_APPROX_SIMPLE parameter to get poly2 containing only end points of the polygon lines which is lighter and which was our input :) important :the type of poly2 is numpy array ,its shape is (n,1,2) and not (n,2)
注意:poly2包含了你的多边形的所有点和组成它的所有点的列表，我的意思是你的多边形的每个顶点的所有点都是你可以找到有用的!您可以使用cv2。CHAIN_APPROX_SIMPLE参数获取只包含多边形线端点的poly2，它更轻，是我们的输入)重要:poly2的类型为numpy数组，其形状为(n,1,2)而不是(n,2)
Now we draw this contour on this image(matrix) and will fill it too :)
现在我们在这张图(矩阵)上画出轮廓并将它填满:
cv2.drawContours(matrix,[poly2],-1,(1),thickness=-1) thickness=-1
cv2.drawContours(矩阵,[poly2],1,(1),厚度= 1)厚度= 1
now we have a matrix where there is 1 on each points forming and filling the polygon , "thickness=-1" has forced to fill this contour, you can put set thickness = 1 to get only the borders if you want to translate, you can do it by adding parameter offset(xtran,ytrans)
现在我们有一个矩阵，每个点上都有1个点形成并填充多边形，"厚度=-1"必须填充这个轮廓，你可以设置厚度= 1来得到只有边框如果你想平移，你可以通过添加参数偏移量(xtran,ytrans)
to get the indices of all theses points simply call
要得到所有这些点的指数，只需调用。
list_of_points_indices=numpy.nonzero(matrix)
Solution 2
解决方案2
Which is smarter is to directly transform your list of points (poly) to a contour format (poly2) and draw it on the matrix
哪一种更聪明的方法是直接将你的点列表(poly)转换成等高线格式(poly2)并在矩阵上画出来
poly2=poly.reshape(-1,1,2).astype(np.int32)
and draw it on the Matrix matrix
在矩阵上画出来
matrix =np.zeros((L,H),dtype=np.int32)
cv2.drawContours(matrix,[poly2],-1,(1),thickness=-1)
And get the list of this points with :
并将这些点的列表如下:
list_of_points_indices=numpy.nonzero(matrix)
Play with thickness to fill or not the polygon , see solution 1 for more details.
选择填充或不填充多边形的厚度，请参阅解决方案1了解更多细节。
#4
1
Building upon RemcoGerlich's answer here's a validated function:
根据RemcoGerlich的回答，这里有一个经过验证的功能:
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))]
Example:
例子:
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()
#5
0
Try this code. poly_coords are the coordinates of your polygon, 'coord' is coordinate of point you want to check if it is inside the polygon.
试试这个代码。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
If you want to make it even faster, take out the part of algo related to polygon, slope and offset and run the rest of code using 'map' function. Something like this:
如果你想让它变得更快，那就拿出与多边形、坡度和偏移有关的algo部分，使用“map”函数运行剩下的代码。是这样的:
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)
You can remove 'print' commands if you want. This code is made for python 2.7
如果需要，可以删除'print'命令。这段代码是为python 2.7编写的
#1
4
I suggest to use matplotlib contains_points()
我建议使用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
#2
2
I think drawing the polygon and filling it is a good start, you're going to need something like that anyway and those algorithms are usually fine tuned in C. But don't use a RGB image, use a black/white image, and use numpy.where() to find the pixels where it's 1.
我认为绘制多边形并填充它是一个很好的开始，无论如何，您都需要这样的东西，而且这些算法通常在c中得到很好的调优，但是不要使用RGB图像，使用黑白图像，并使用numpi .where()来找到像素的1。
According to this question, the mahotas library has a fill_polygon function that works with numpy arrays.
根据这个问题，mahotas库有一个fill_polygon函数，它与numpy数组一起工作。
I'm starting the following code from your function (I would subtract the minx and maxx too) but note that I can't test it at all, I'm not on my dev machine.
我正在从您的函数中启动以下代码(我也要减去minx和maxx)，但是请注意，我根本不能测试它，我不在我的开发机器上。
import numpy as np
import mahotas
def render(poly, 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 polygons]
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)]
#3
2
You can use a numpy matrix like a binary image, which can be used with Opencv for example or other image processing libs, Solution 1 So a matrix which size is L x H where
你可以使用一个numpy矩阵像一个二进制图像，它可以用于Opencv例如其他图像处理libs，解决方案1，一个大小为lxh的矩阵
L=max(x) - min (x)
H=max(y) - min (y)
As entry we have your list of tuple(x,y) you gave above which name is poly for example :
作为条目，我们有你在上面给出的tuple(x,y)的列表，例如:
import numpy as np
matrix =np.zeros((L,H),dtype=np.int32) # you can use np.uint8 if unsigned x ,y
So we have now a matrix of Size L x H filled with 0, we put now 1 at polygon points positions
现在我们有一个大小为lxh的矩阵，填充为0，我们现在把1放在多边形点的位置上
I think you can simple do that
我觉得你可以这么做
matrix[poly]=1 # which will put 1 at each (x,y) of the list **poly**
we interpret this as a binary (black/white) image which have a contour drawn on it Assume we want to detect this new contour
我们将它解释为一个带有轮廓的二进制(黑白)图像，假设我们想要检测这个新的轮廓
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
Note : poly2 is containing a list of points of your polygon and all points forming it, i mean all points of each vertices of your polygon which is what you need can find useful !! you can use cv2.CHAIN_APPROX_SIMPLE parameter to get poly2 containing only end points of the polygon lines which is lighter and which was our input :) important :the type of poly2 is numpy array ,its shape is (n,1,2) and not (n,2)
注意:poly2包含了你的多边形的所有点和组成它的所有点的列表，我的意思是你的多边形的每个顶点的所有点都是你可以找到有用的!您可以使用cv2。CHAIN_APPROX_SIMPLE参数获取只包含多边形线端点的poly2，它更轻，是我们的输入)重要:poly2的类型为numpy数组，其形状为(n,1,2)而不是(n,2)
Now we draw this contour on this image(matrix) and will fill it too :)
现在我们在这张图(矩阵)上画出轮廓并将它填满:
cv2.drawContours(matrix,[poly2],-1,(1),thickness=-1) thickness=-1
cv2.drawContours(矩阵,[poly2],1,(1),厚度= 1)厚度= 1
now we have a matrix where there is 1 on each points forming and filling the polygon , "thickness=-1" has forced to fill this contour, you can put set thickness = 1 to get only the borders if you want to translate, you can do it by adding parameter offset(xtran,ytrans)
现在我们有一个矩阵，每个点上都有1个点形成并填充多边形，"厚度=-1"必须填充这个轮廓，你可以设置厚度= 1来得到只有边框如果你想平移，你可以通过添加参数偏移量(xtran,ytrans)
to get the indices of all theses points simply call
要得到所有这些点的指数，只需调用。
list_of_points_indices=numpy.nonzero(matrix)
Solution 2
解决方案2
Which is smarter is to directly transform your list of points (poly) to a contour format (poly2) and draw it on the matrix
哪一种更聪明的方法是直接将你的点列表(poly)转换成等高线格式(poly2)并在矩阵上画出来
poly2=poly.reshape(-1,1,2).astype(np.int32)
and draw it on the Matrix matrix
在矩阵上画出来
matrix =np.zeros((L,H),dtype=np.int32)
cv2.drawContours(matrix,[poly2],-1,(1),thickness=-1)
And get the list of this points with :
并将这些点的列表如下:
list_of_points_indices=numpy.nonzero(matrix)
Play with thickness to fill or not the polygon , see solution 1 for more details.
选择填充或不填充多边形的厚度，请参阅解决方案1了解更多细节。
#4
1
Building upon RemcoGerlich's answer here's a validated function:
根据RemcoGerlich的回答，这里有一个经过验证的功能:
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))]
Example:
例子:
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()
#5
0
Try this code. poly_coords are the coordinates of your polygon, 'coord' is coordinate of point you want to check if it is inside the polygon.
试试这个代码。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
If you want to make it even faster, take out the part of algo related to polygon, slope and offset and run the rest of code using 'map' function. Something like this:
如果你想让它变得更快，那就拿出与多边形、坡度和偏移有关的algo部分，使用“map”函数运行剩下的代码。是这样的:
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)
You can remove 'print' commands if you want. This code is made for python 2.7
如果需要，可以删除'print'命令。这段代码是为python 2.7编写的