Peter Leow
Выбрал это новое задание, пока ждал своего рейса домой. Один взгляд, и это будет включать геометрию, то есть декартову систему координат, векторы, ребра и углы. Чтобы убить время, я начал излагать свои мысли по телефону...
Есть три способа решить эту проблему:
1. Самый простой из них-взять и использовать один из многочисленных пакетов Python для манипулирования и анализа геометрических объектов на декартовой плоскости.
2. Самым сложным будет найти свой собственный алгоритм (исключая известные), чтобы определить, находится ли точка внутри или снаружи многоугольника.
3. последним и крайним будет изучение некоторых методов машинного обучения, таких как нейронная сеть, чтобы узнать и классифицировать точку, находящуюся внутри или снаружи многоугольника. Это отнимает много времени, так как для изучения компьютера потребуется большой набор данных полигонов и точек с известными результатами. Я не буду пытаться сделать это здесь.
Давайте начнем...
Самый Простой
Я использую Стройная 1. 6b2[^] для этой демонстрации. Приведенный ниже код комментируется URL-адресами, указывающими на соответствующие онлайн-ссылки:
"""
IsPointInPolygon_1.py
The easier way using shapely package
by Peter Leow the point seeker
"""
from shapely.geometry.polygon import Polygon
from shapely.geometry.point import Point
def pointWithinPolygon(point, polygon):
# http://toblerity.org/shapely/manual.html#object.within
return point.within(polygon)
def polygonContainsPoint(point, polygon):
# http://toblerity.org/shapely/manual.html#object.contains
return polygon.contains(point)
def main():
# http://toblerity.org/shapely/manual.html#polygons
polygon = Polygon([(2,0), (4,1), (4,4), (2,5), (1,2)])
while True:
# http://toblerity.org/shapely/manual.html#points
coords = input("Input the x y coordinates of a point separated by space: ").split()
if len(coords) != 2:
break
# Numeric validation omitted
point= Point(float(coords[0]), float(coords[1]))
resultWithin = 'Is {} within {}? {}.'.format(point, polygon, pointWithinPolygon(point, polygon))
resultContains = 'Does {} contain {}? {}.'.format(polygon, point, polygonContainsPoint(point, polygon))
print(resultWithin)
print(resultContains)
main()
Пример вывода:
Input the x y coordinates of a point separated by space: 3 3
Is POINT (3 3) within POLYGON ((2 0, 4 1, 4 4, 2 5, 1 2, 2 0))? True.
Does POLYGON ((2 0, 4 1, 4 4, 2 5, 1 2, 2 0)) contain POINT (3 3)? True.
Input the x y coordinates of a point separated by space: 5 4
Is POINT (5 4) within POLYGON ((2 0, 4 1, 4 4, 2 5, 1 2, 2 0))? False.
Does POLYGON ((2 0, 4 1, 4 4, 2 5, 1 2, 2 0)) contain POINT (5 4)? False.
Input the x y coordinates of a point separated by space: 4 4
Is POINT (4 4) within POLYGON ((2 0, 4 1, 4 4, 2 5, 1 2, 2 0))? False.
Does POLYGON ((2 0, 4 1, 4 4, 2 5, 1 2, 2 0)) contain POINT (4 4)? False.
Input the x y coordinates of a point separated by space:
Вы будете иметь, чтобы установить стройная пакет из
Shapely 1. 6b2 : индекс пакета Python[
^] до запуска этой программы.
Тот Самый Сложный
Когда я изучал различные многоугольники и точки по телефону, я заметил одну особенность, которая, кажется, преобладает только тогда, когда точка находится внутри многоугольника-сумма всех углов от точки до соседних вершин охватывающего многоугольника всегда равна 2pi в радианах (или 360 градусов). Для реализации этого предположения я написал следующий код:
"""
IsPointInPolygon_2.py
The pain-in-the-a** way
by Peter Leow the point seeker
"""
import math
def offsetCoords(polygon, newOrigin):
offsetPolygon = []
for v in polygon:
offsetPolygon.append((v[0]-newOrigin[0], v[1]-newOrigin[1]))
return offsetPolygon
def dotProduct(v1, v2):
return v1[0]*v2[0]+v1[1]*v2[1]
def vectorLen(v):
return (v[0]**2+v[1]**2)**.5
def angleBetweenVectors(v1, v2):
cosine = dotProduct(v1, v2) / (vectorLen(v1) * vectorLen(v2))
return math.acos(cosine)
def isWithin(point, polygon):
# weed out the obvious
if point in polygon:
return False
# Find angle of each adjacent vectors
sumAngles = 0
for i in range(len(polygon) - 1):
sumAngles += angleBetweenVectors(polygon[i], polygon[i+1])
if math.isclose(sumAngles, math.pi*2):
return True
else:
return False
def main():
# A list of coords tuples
polygon = [(2,0), (4,1), (4,4), (2,5), (1,2), (2,0)]
while True:
coords = input("Input the x y coordinates of a point separated by space: ").split()
if len(coords) != 2: # Exit on Enter key
break
# Numeric validation omitted
point = (float(coords[0]), float(coords[1]))
'''
Set this point as the origin (0 0) of the cartesian coordinate plane
by offsetting all vertices of the polygon against it
'''
offsetPolygon = offsetCoords(polygon, point)
offsetPoint = (0, 0)
result = 'Is POINT {} within POLYGON {}? {}.'.format(point, polygon, isWithin(offsetPoint, offsetPolygon))
print(result)
main()
Пример вывода показан ниже:
Input the x y coordinates of a point separated by space: 3 3
Is POINT (3.0, 3.0) within POLYGON [(2, 0), (4, 1), (4, 4), (2, 5), (1, 2), (2, 0)]? True.
Input the x y coordinates of a point separated by space: 5 4
Is POINT (5.0, 4.0) within POLYGON [(2, 0), (4, 1), (4, 4), (2, 5), (1, 2), (2, 0)]? False.
Input the x y coordinates of a point separated by space: 4 4
Is POINT (4.0, 4.0) within POLYGON [(2, 0), (4, 1), (4, 4), (2, 5), (1, 2), (2, 0)]? False.
Input the x y coordinates of a point separated by space:
Пока все идет так хорошо, что мое предположение, похоже, остается верным. У кого-нибудь есть свободное время? Пожалуйста, помогите проверить это.