算法：PIP 多邊形與點位置關系
- 純手撸代碼解決PIP問題
-
- 面向對象
- 射線法解決PIP問題
- 結果
純手撸代碼解決PIP問題
程式設計語言為Python
面向對象
建立一個geometry類，其中包括點、線、多邊形對象。
class Geometry:
def __init__(self, name):
self.__name = name
def get_name(self):
return self.__name
class Point(Geometry):
# contains X/Y
def __init__(self, name, x, y):
super().__init__(name)
self.__x = x
self.__y = y
def get_x(self):
return float(self.__x)
def get_y(self):
return float(self.__y)
class Line(Geometry):
# contains 2 points
def __init__(self, name, p1: Point, p2: Point):
super().__init__(name)
if not isinstance(p1, Point) or not isinstance(p2, Point):
raise ValueError("point must be an object of " + str(type(Point)))
self.__p1 = p1
self.__p2 = p2
self.__len = ((p1.get_x() - p2.get_x()) ** 2 + (p1.get_y() - p2.get_y()) ** 2) ** 0.5
def get_length(self):
return self.__len
def get_points(self):
return self.__p1, self.__p2
class Polygon(Geometry):
# contains many points
def __init__(self, name, points):
super().__init__(name)
self.__points = points
def get_points(self):
return self.__points
def get_lines(self):
line_set = []
points = self.__points
line_length = len(points)
for i in range(line_length - 1):
line_set.append(Line(points[i].get_name() + "-" + points[i + 1].get_name(), points[i], points[i + 1]))
line_set.append(Line(points[-1].get_name() + "-" + points[0].get_name(), points[-1], points[0]))
return line_set
射線法解決PIP問題
射線法理論不再贅述，感興趣可以自行百度，在這裡需要讨論幾個特殊情況：
a、b 兩種情況下都不算射線穿越多邊形矩陣邊界，而 c、d 兩種情況下需要記錄一次穿越。
def is_ray_cross(point: Point, line: Line, last_line_position):
start_point, end_point = line.get_points() # define direct for each line
if point.get_y() > max(start_point.get_y(), end_point.get_y()):
return False, 0
elif point.get_y() < min(start_point.get_y(), end_point.get_y()):
return False, 0
elif point.get_x() > max(start_point.get_x(), end_point.get_x()): # the ray is on the right of the line
return False, 0
elif point.get_y() == start_point.get_y() and (point.get_y() - end_point.get_y()) * last_line_position >= 0:
if start_point.get_y() == end_point.get_y():
return False, last_line_position
else:
return False, 0
elif point.get_y() == end_point.get_y(): # exclude the situation of overlaps and intersects at the end point
if point.get_y() - start_point.get_y() < 0: # use mark to handle the situation that ray passes through a vertex
mark = -1
else:
mark = 1
return False, mark
intersect_x = end_point.get_x() - (end_point.get_x() - start_point.get_x()) * (
end_point.get_y() - point.get_y()) / (end_point.get_y() - start_point.get_y())
if intersect_x < point.get_x(): # the intersect is at the left of the point
return False, 0
return True, 0
射線法的核心思想為：從待判斷點引出一條射線，該射線與多邊形相交的次數（奇/偶）決定了點與多邊形的位置關系。
# implement RCA (method, need to be transfer into oop)
def rca(polygon: Polygon, *test_points):
res = []
lines = polygon.get_lines()
is_boundary = False
for point in test_points:
count = 0
mark = 0
start_point, end_point = lines[-1].get_points()
if end_point.get_y() == point.get_y(): # use mark to handle the situation that ray passes through a vertex
if point.get_y() - start_point.get_y() < 0:
mark = -1
else:
mark = 1
for line in lines:
if is_on_boundary(point, line):
res.append('boundary')
is_boundary = True
break
is_cross, mark = is_ray_cross(point,line,mark)
if is_cross:
count += 1
if is_boundary:
is_boundary = False
else:
if count % 2 == 1:
res.append('inside')
else:
res.append('outside')
return res
結果
