1. Distance from point to point
First of all, the simplest is the distance between two points, just use the distance formula directly
import math
import matplotlib.pyplot as plt
def point_to_point(x1, y1, x2, y2):
lineMagnitude = math.sqrt(math.pow((x2 - x1), 2) + math.pow((y2 - y1), 2))
return lineMagnitude
2. Distance from point to line segment
The key is to judge whether the projection of the point on the straight line is outside the line segment or inside the line segment (the projection u of AP on AB is calculated by the vector method). If it is inside the line segment (0≤u≤1), the distance from the point to the line is returned; if Outside the line segment (u<0 or u>1), directly calculate the distance from the point to the two ends and take the minimum value
# Calculate the shortest distance between point P(px,py) and line segment A(x1,y1)B(x2,y2)
def point_to_line(px, py, x1, y1, x2, y2):
line_magnitude = point_to_point(x1, y1, x2, y2)
if line_magnitude < 0.00000001:
#If the line segment is very close, directly return the distance from P to A
return point_to_point(px, py, x1, y1)
u1 = (((px - x1) * (x2 - x1)) + ((py - y1) * (y2 - y1))) #vector AB · vector AP
u = u1 / (line_magnitude * line_magnitude) #The ratio of the projection of vector AP in the direction of vector AB to the modulus of vector AB
if (u < 0) or (u > 1):
# The projection from a point to a straight line is not within the line segment, and the minimum distance between the calculated point and the two endpoints is "minimum distance from point to line segment"
return min(point_to_point(px, py, x1, y1), point_to_point_distance(px, py, x2, y2))
# The projection point is inside the line segment, the calculation method is the same as the distance from the point to the line, u is the ratio of the projection point distance x1 to x1x2, and the coordinates of the projection point are calculated
ix = x1 + u * (x2 - x1)
iy = y1 + u * (y2 - y1)
return point_to_point(px, py, ix, iy)
3. The shortest distance between a point and a vertical rectangle
A vertical rectangle means that each side of the rectangle is perpendicular to the coordinate axis, and can be determined by the coordinates of the upper left and lower right points
First judge whether the point is inside the rectangle or on the side of the rectangle. If so, the distance is 0. If the point is outside the rectangle, the minimum distance from the point to the four sides of the rectangle is the minimum distance from the point to the rectangle.
# Calculate the shortest distance between point P(px,py) and vertical rectangle A(x1,y1)B(x2,y2)
def point_to_rectangle(px, py, x1, y1, x2, y2):
if px > min(x1,x2) and px < max(x1,x2) and py > min(y1,y2) and py < max(y1,y2):
# point inside the rectangle
return 0
distance1 = point_to_line(px, py, x1, y1, x1, y2)
distance2 = point_to_line(px, py, x1, y1, x2, y1)
distance3 = point_to_line(px, py, x2, y2, x1, y2)
distance4 = point_to_line(px, py, x2, y2, x2, y1)
return min(distance1,distance2,distance3,distance4)
4. The shortest distance from a point to any convex polygon
In a more general situation, it is necessary to calculate the shortest distance from a point to any convex polygon. The definition of a convex polygon is: a polygon without any interior angle being a reflexive angle, as shown in the figure below
#Polygon drawing display
import matplotlib.pyplot as plt
poly1 = ((1,0.5),(1.5,2.5),(2,2),(1.5,3),(0.1,1))
poly2 = ((1,0.5),(1.8,1),(2,2),(1.5,3),(0.1,1))
fig = plt.figure(figsize=(10,5))
plt.rcParams['font.sans-serif']=['SimHei'] # used to display Chinese labels normally
plt.rcParams['axes.unicode_minus']=False # used to display the negative sign normally
ax1 = fig.add_subplot(1,2,1)
plt.title('concave polygon')
polygon = plt.Polygon(xy=poly1, color='blue', alpha=0.3)
ax1. add_patch(polygon)
xylim = max(max(i) for i in poly1)*1.1
ax1.set_ylim(0,xylim)
ax1.set_xlim(0,xylim)
ax2 = fig.add_subplot(1,2,2)
plt.title('convex polygon')
polygon2 = plt.Polygon(xy=poly2, color='blue', alpha=0.3)
ax2. add_patch(polygon2)
xylim = max(max(i) for i in poly2)*1.1
ax2.set_ylim(0,xylim)
ax2.set_xlim(0,xylim)
plt.savefig('poly.png')
plt. show()
The calculation idea is similar to that of a rectangle. First, determine whether the point is inside the polygon or on the side of the polygon. If so, the distance is 0. If the point is outside the polygon, the minimum distance from the point to each side of the polygon is the minimum distance from the point to the polygon.
4.1 Determine whether it is a convex polygon
Judging according to the characteristics of a convex polygon: if one of the sides of a polygon is infinitely extended to both sides to form a straight line, and the other sides are on the same side of the straight line, then the polygon is called a convex polygon.
#Calculate the line expression, return the category of the line and its description parameters
def kb(vertex1, vertex2):
x1,y1 = vertex1
x2,y2 = vertex2
if x1==x2:
return (0, x1) # 0-vertical line
if y1==y2:
return (1, y1) # 1-horizontal straight line
else:
k = (y1-y2)/(x1-x2)
b = y1 - k*x1
return (2, k, b) # 2-slope straight line
#Determine that the polygon is a convex polygon
def isConvex(poly):
# Default is convex polygon
convex = True
poly_num = len(poly)
# Make a judgment on the straight line formed by every two points
for i in range(poly_num):
j = (i + 1)%poly_num
# get straight line
line = kb(poly[i], poly[j])
# Calculate the distance between all points and the line (may be positive or negative)
if line[0]==0:
offset = [vertex[0]-poly[i][0] for vertex in poly]
elif line[0]==1:
offset = [vertex[1]-poly[i][1] for vertex in poly]
else:
k, b = line[1], line[2]
offset = [k*vertex[0] + b-vertex[1] for vertex in poly]
# Calculate the product of pairwise distances. If there is a negative number, there are two points on both sides of the line, so it is a concave polygon
for o in range(len(offset)-1):
if offset[o]*offset[o + 1] < 0:
convex = False
break
if convex==False:
break
if convex==False:
#drawing display
fig = plt.figure(figsize=(5,5))
ax1 = fig.add_subplot(1,1,1)
polygon = plt.Polygon(xy=poly, color='blue', alpha=0.3)
ax1. add_patch(polygon)
X = [point[0] for point in poly]
Y = [point[1] for point in poly]
plt.scatter(X,Y,c='blue')
# plt. scatter([px],[py],c='red')
xylim = max(max(i) for i in poly)*1.1
ax1.set_ylim(0,xylim)
ax1.set_xlim(0,xylim)
plt. show()
return convex
4.2 Judgment point is within the polygon
Use the method of vector cross product to judge:
#Determine whether the point is inside the convex polygon
def isinpolygon(px, py, poly):
#poly is the polygon coordinates, arranged clockwise or counterclockwise
z=[] #The cross product of the connection vector between each vertex and P point and the fixed point and the next vertex vector
poly_num = len(poly) #The number of sides of the polygon
if poly_num <=1:
return False
for i in range(poly_num):
j = (i + 1)%(poly_num) #j is the next vertex number
z.append((poly[j][0]-poly[i][0])*(py-poly[i][1]) - (px-poly[i][0])*(poly[j ][1]-poly[i][1])) #Calculate cross product
#If all the results of the cross product have the same sign, return true, otherwise return false
for k in range(len(z)-1):
if z[k]*z[k + 1] < 0:
return False
return True
4.3 Calculate the distance from a point to a polygon
# Calculate the shortest distance between point P(px,py) and any convex polygon
def point_to_polygon(px, py, poly):
if not isConvex(poly):
raise ValueError("Concave polygon cannot be calculated!")
if isinpolygon(px, py, poly):
min_distance = 0
else:
distance = [] #The shortest distance from a point to each side
poly_num = len(poly) #The number of sides of the polygon
for i in range(poly_num):
j = (i + 1)%(poly_num) #j is the next vertex number
distance.append(point_to_line(px, py, poly[i][0], poly[i][1], poly[j][0], poly[j][1]))
min_distance = min(distance)
#drawing display
fig = plt.figure(figsize=(5,5))
ax1 = fig.add_subplot(1,1,1)
polygon = plt.Polygon(xy=poly, color='blue', alpha=0.5)
ax1. add_patch(polygon)
X = [point[0] for point in poly]
Y = [point[1] for point in poly]
plt.scatter(X,Y,c='blue')
plt.scatter([px],[py],c='red')
xylim = max(px,py,max(max(i) for i in poly))*1.1
ax1.set_ylim(0,xylim)
ax1.set_xlim(0,xylim)
plt. show()
return min_distance
5. Test:
point_to_polygon(1,1,((1,0.5),(2,1),(2,2),(1.5,3),(0.1,1)))
output: 0
point_to_polygon(2.5,0.5,((1,0.5),(2,1),(2,2),(1.5,3),(0.1,1)))
Output: 0.7071067811865476
point_to_polygon(1,1,((1,0.5),(1.5,1.8),(2,2),(1.5,3),(0.1,1)))
Output: ValueError: concave polygon cannot be computed!
#The polygon of two points is the distance from the point to the line segment point_to_polygon(0.5,0.5,[[1,0.2],[2,2]])
Output: 0.5827715174143584
#1 point polygon, which is the distance from point to point point_to_polygon(0.5,0.5,[[1,0.5]])
Output: 0.5
Special vertical rectangles can also be computed using the general point-to-polygon method:
# Calculate the shortest distance between point P(px,py) and vertical rectangle A(x1,y1)B(x2,y2) by point-to-polygon method
def point_to_rectangle2(px, py, x1, y1, x2, y2):
poly = ((x1,y1),(x1,y2),(x2,y2),(x2,y1))
return point_to_polygon(px,py,poly)