Итак, ответ для 2D и 3D задачи аналогичен. Поскольку это здания, мы можем разделить 3D-модель на две 2D-модели с основанием здания и крышей (и все, что находится между ними, также считается крышей).
Затем мы ищем четырехугольник для приближения точки в (приблизительно) плоскости. Нам нужно найти центр (не в среднем по всем точкам, но (max + min) / 2 в обоих направлениях). Мы перемещаем начало координат в центр, вычисляя точки - центр. Затем точки должны быть разделены на квадранты (x> 0 & y> 0, x <0, & y> 0, x <0, & y <0, x> 0, & y <0), и для каждого квадранта мы вычисляем самая отдаленная точка (если есть nan, мы берем начало координат [0,0]). </p>
Используя формулу Шнурка, мы вычисляем площадь, взятую этими 4 точками из каждого квадранта, сохраняя это значение. После этого мы поворачиваем точки вокруг начала координат на 1 градус до 90 градусов. Каждый раз мы рассчитываем площадь и ищем максимальную площадь. Точки, выставляющие максимальную площадь, являются желаемыми точками. Код (я знаю, что это не гладкий код, может быть оптимизирован. Но он работает !!):
def getCorners(points):
maxPoint = np.max(points[:,0])
mayPoint = np.max(points[:,1])
minPoint = np.min(points[:,0])
miyPoint = np.min(points[:,1])
meanPoint = np.array([(maxPoint + minPoint)/2, (mayPoint + miyPoint)/2])
normPoints = points[:,0:2] - meanPoint[0:2]
areaMaximum = -1
finID1 = 0
finID2 = 1
finID3 = 2
finID4 = 3
numrot = 360
for alpha in range(0,numrot):
topright = np.where((normPoints[:,0] > 0) & (normPoints[:,1] > 0))
topleft = np.where((normPoints[:,0] < 0) & (normPoints[:,1] > 0))
bottomleft = np.where((normPoints[:,0] < 0) & (normPoints[:,1] < 0))
bottomright = np.where((normPoints[:,0] > 0) & (normPoints[:,1] < 0))
q1 = normPoints[topright]
q2 = normPoints[topleft]
q3 = normPoints[bottomleft]
q4 = normPoints[bottomright]
if len(q1) == 0:
q1 = np.array([[0,0],[0,0]])
if len(q2) == 0:
q2 = np.array([[0,0],[0,0]])
if len(q3) == 0:
q3 = np.array([[0,0],[0,0]])
if len(q4) == 0:
q4 = np.array([[0,0],[0,0]])
D1 = q1[:,0]*q1[:,0] + q1[:,1]*q1[:,1]
D2 = q2[:,0]*q2[:,0] + q2[:,1]*q2[:,1]
D3 = q3[:,0]*q3[:,0] + q3[:,1]*q3[:,1]
D4 = q4[:,0]*q4[:,0] + q4[:,1]*q4[:,1]
ID1 = np.argmax(D1)
ID2 = np.argmax(D2)
ID3 = np.argmax(D3)
ID4 = np.argmax(D4)
vertices = [[q1[ID1,0],q1[ID1,1]],[q2[ID2,0],q2[ID2,1]],[q3[ID3,0],q3[ID3,1]],[q4[ID4,0],q4[ID4,1]]]
area = polygonArea(vertices)
if area > areaMaximum:
areaMaximum = area
if len(topright[0]) == 0:
finID1 = 0
else:
finID1 = topright[0][ID1]
if len(topleft[0]) == 0:
finID2 = 0
else:
finID2 = topleft[0][ID2]
if len(bottomleft[0]) == 0:
finID3 = 0
else:
finID3 = bottomleft[0][ID3]
if len(bottomright[0]) == 0:
finID4 = 0
else:
finID4 = bottomright[0][ID4]
# rotate
for opi in range(0,len(normPoints)):
normPoints[opi] = rotate_origin_only(normPoints[opi], 90/numrot/180*np.pi)
return [finID1,finID2,finID3,finID4]
def rotate_origin_only(xy, radians):
"""Only rotate a point around the origin (0, 0)."""
x, y = xy
xx = x * math.cos(radians) + y * math.sin(radians)
yy = -x * math.sin(radians) + y * math.cos(radians)
return xx, yy
def polygonArea(vertices):
#A function to apply the Shoelace algorithm
numberOfVertices = len(vertices)
sum1 = 0
sum2 = 0
for i in range(0,numberOfVertices-1):
sum1 = sum1 + vertices[i][0] * vertices[i+1][1]
sum2 = sum2 + vertices[i][1] * vertices[i+1][0]
#Add xn.y1
sum1 = sum1 + vertices[numberOfVertices-1][0]*vertices[0][1]
#Add x1.yn
sum2 = sum2 + vertices[0][0]*vertices[numberOfVertices-1][1]
area = abs(sum1 - sum2) / 2
return area