Picked out this new mission while waiting for my flight home. One look and this is going to involve geometry, that means Cartesian coordinate system, vectors, edges, and angles sort of things. To kill time, I started drawing out my thought on the phone...
There are three ways to solve this problem:
1. The easiest one is to pluck and use one of the many Python packages for manipulation and analysis of geometric objects on the Cartesian plane.
2. The challenging one will be to find your own algorithm (excluding known ones) to determine that a point is inside or outside a polygon.
3. The last and extreme one will be to explore certain machine learning techniques such as neural network to learn and classify a point to be either inside or outside of a polygon. This is time-consuming, as it will need a big data set of polygons and points with known results for the computer to learn. I will not be attempting it here.
Let's begin...
The Easiest One
I am using the
Shapely 1.6b2[
^] for this demo. The code below is commented with URLs that point to the respective online references:
"""
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):
return point.within(polygon)
def polygonContainsPoint(point, polygon):
return polygon.contains(point)
def main():
polygon = Polygon([(2,0), (4,1), (4,4), (2,5), (1,2)])
while True:
coords = input("Input the x y coordinates of a point separated by space: ").split()
if len(coords) != 2:
break
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()
An example output:
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:
You will have to install the shapely package from
Shapely 1.6b2 : Python Package Index[
^] prior to running this program.
The Challenging One
As I was exploring the different polygons and points on the phone, I observed one trait that seems to prevail only when a point is inside a polygon--The sum of all angles from the point to adjacent vertices of the encompassing polygon is always 2pi in radians (or 360 degrees). I wrote the following code to implement this assumption:
"""
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):
if point in polygon:
return False
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():
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:
break
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()
An example output is shown below:
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:
So far so good, my assumption seems to hold true. Anyone have time to spare? Please help to test it out.
Submit an article or tip