Я ищу алгоритм для проверки, находится ли точка внутри полигона или нет.Использование matplotlib для решения точки в Polygone
В настоящее время я использую mplPath и contains_point(), но в некоторых случаях он не работает.
EDIT 16 Сентябрь 2016:
Хорошо, так я imporved мой код, просто проверяя, если в точке, где также по краям. Я до сих пор есть некоторые проблемы с прямоугольником и лук галстук пример, хотя:
НОВЫЙ КОД:
#for PIP problem
import matplotlib.path as mplPath
import numpy as np
#for plot
import matplotlib.pyplot as plt
def plot(poly,points):
bbPath = mplPath.Path(poly)
#plot polygon
plt.plot(*zip(*poly))
#plot points
xs,ys,cs = [],[],[]
for point in points:
xs.append(point[0])
ys.append(point[1])
color = inPoly(poly,point)
cs.append(color)
print point,":", color
plt.scatter(xs,ys, c = cs , s = 20*4*2)
#setting limits
axes = plt.gca()
axes.set_xlim([min(xs)-5,max(xs)+50])
axes.set_ylim([min(ys)-5,max(ys)+10])
plt.show()
def isBetween(a, b, c): #is c between a and b ?
crossproduct = (c[1] - a[1]) * (b[0] - a[0]) - (c[0] - a[0]) * (b[1] - a[1])
if abs(crossproduct) > 0.01 : return False # (or != 0 if using integers)
dotproduct = (c[0] - a[0]) * (b[0] - a[0]) + (c[1] - a[1])*(b[1] - a[1])
if dotproduct < 0 : return False
squaredlengthba = (b[0] - a[0])*(b[0] - a[0]) + (b[1] - a[1])*(b[1] - a[1])
if dotproduct > squaredlengthba: return False
return True
def get_edges(poly):
# get edges
edges = []
for i in range(len(poly)-1):
t = [poly[i],poly[i+1]]
edges.append(t)
return edges
def inPoly(poly,point):
if bbPath.contains_point(point) == True:
return 1
else:
for e in get_edges(poly):
if isBetween(e[0],e[1],point):
return 1
return 0
# TESTS ========================================================================
#set up poly
polys = {
1 : [[10,10],[10,50],[50,50],[50,80],[100,80],[100,10],[10,10]], # test rectangulary shape
2 : [[20,10],[10,20],[30,20],[20,10]], # test triangle
3 : [[0,0],[0,10],[20,0],[20,10],[0,0]], # test bow-tie
4 : [[0,0],[0,10],[20,10],[20,0],[0,0]] # test rect
}
#points to check
points = {
1 : [(10,25),(50,75),(60,10),(20,20),(20,60),(40,50)], # rectangulary shape test pts
2 : [[20,10],[10,20],[30,20],[-5,0],[20,15]] , # triangle test pts
3 : [[0,0],[0,10],[20,0],[20,10],[10,0],[10,5],[15,5]], # bow-tie shape test pts
4 : [[0,0],[0,10],[20,0],[20,10],[10,0],[10,5],[15,5]] # rect shape test pts
}
#print bbPath.contains_points(points) #0 if outside, 1 if inside
for data in zip(polys.itervalues(),points.itervalues()):
plot(data[0],data[1])
Выходы из нового кода:
СТАРЫЙ КОД:
#for PIP problem
import matplotlib.path as mplPath
import numpy as np
#for plot
import matplotlib.pyplot as plt
#set up poly
array = np.array([[10,10],[10,50],[50,50],[50,80],[100,80],[100,10]])
bbPath = mplPath.Path(array)
#points to check
points = [(10,25),(50,75),(60,10),(20,20),(20,60),(40,50)]
print bbPath.contains_points(points) #0 if outside, 1 if inside
#plot polygon
plt.plot(*zip(*array))
#plot points
xs,ys,cs = [],[],[]
for point in points:
xs.append(point[0])
ys.append(point[1])
cs.append(bbPath.contains_point(point))
plt.scatter(xs,ys, c = cs)
#setting limits
axes = plt.gca()
axes.set_xlim([0,120])
axes.set_ylim([0,100])
plt.show()
Я придумываю следующие . Как вы можете видеть, три точки, окруженные красным цветом, обозначены как находящиеся вне полигона (синим цветом), когда я ожидаю, что они будут внутри.
Я также попытался изменить значение радиуса пути bbPath.contains_points(points, radius = 1.)
, но это не имело никакого значения.
Любая помощь будет радушна.
EDIT:
скриншоты из предложенного алгоритма в ответ на этот вопрос, видимо, чтобы показать, что она не для других случаев.
привет, спасибо за попытку. Тем не менее, я провел еще несколько тестов, и большинство из них не смогли сформировать точки, не расположенные точно на краях многоугольника. Поскольку я не могу добавить изображения здесь, я редактировал свой вопрос с помощью снимков экрана. – Sorade