点が多角形内にあるかどうかを判断する方法
6851 ワード
このブログでは、3 Dポイント、すなわち空間ポイントがポリゴン(3 D空間のポリゴン)内にあるかどうかを判断する方法を示します.
一、二次元の場合、多角形内にある点をどのように判断するか
参照リンクさんこうりんく:点がポリゴンの内側にあるかどうかを判断てんがポリゴンの内側にあるかどうかをはんてい
ここでpythonを用いて、目標点とすべての頂点を接続し、隣接する両側の挟み角の和を計算して360°に等しいかどうかを判断します.もし、この点が多角形内にあれば、そうでなければ多角形内にはありません.この考えによれば、次のPythonコードに基づいて他の言語のコードに書き換えやすい.
二、どのように1つの3次元の点が1つの空間の中の多角形の中で判断します
アルゴリズム思想.
まずpointと多角形が存在する平面の距離を計算し、距離が0より大きいと平面上ではなく、多角形の内部では不可能である.次に、3 D平面を2 D平面に下げ(成分を直接削除)、3 D点を2 D点に下げ、2 D平面内で点がポリゴン内にあるかどうかを判断する方法によって、点が3 Dポリゴン内にあるかどうかを判断します.3 D平面を2 D平面に下げることができる理由は、ある座標面に1つの平面を投影すると、投影前の点がポリゴン内にあれば、投影後もポリゴン内にあるからです.もちろん、上記の結論の成立条件は、多角形のある平面Aが投影された座標面Bに垂直にならないことである.法ベクトルの成分が0の場合、多角形のある平面Aがある座標面Bに垂直であることを示し、多角形を座標面Bに投影し、投影結果が1本の線であると、点が多角形内にあるか否かを判断できない.
次に、投影方法について説明します.
特殊な場合、多角形が存在する平面Aの法線ベクトルが(0,0,a)、aが非0定数の場合、平面Aは座標面xOyに平行であるため、pointと頂点のz成分を削除すると、平面Aの座標面におけるxOyの投影が得られ、この場合、2次元の関数を呼び出して点が多角形内にあるか否かを判断することができる.同様に、平面Aの法線ベクトルが(0,a,0)、(a,0,0)、aが非ゼロ定数の場合、pointと頂点のy成分またはx成分を削除することによって、成分が投影される.
平面Aの法線ベクトルが(a,b,0)、a,bが非ゼロ定数の場合、平面Aは座標面xOyに垂直であるため、xOy面に投影することができず、他の2つの座標面に投影することができる.したがって、pointと頂点のxまたはy成分を削除することで、ポリゴンの投影を得ることができます.
平面Aの法線ベクトルの成分が0でなければ、任意に1つの成分を削除すれば投影が完了する.
以上より,投影を完了する方法はpointと頂点セットを削除し,法ベクトルが0のいずれの成分でもない.
次にPythonコードを示します.このPythonコードに基づいて他の言語のコードに書き換えることができます.
三、最後に、上述の2つのコードのテスト例を示す.
一、二次元の場合、多角形内にある点をどのように判断するか
参照リンクさんこうりんく:点がポリゴンの内側にあるかどうかを判断てんがポリゴンの内側にあるかどうかをはんてい
ここでpythonを用いて、目標点とすべての頂点を接続し、隣接する両側の挟み角の和を計算して360°に等しいかどうかを判断します.もし、この点が多角形内にあれば、そうでなければ多角形内にはありません.この考えによれば、次のPythonコードに基づいて他の言語のコードに書き換えやすい.
'''
@description point vertices
： point ， ，
360°， 。
：http://www.html-js.com/article/1538
@param point 。 List。
@param vertices ，
。3 List( List ) List。
@return ， True， False
'''
def is_in_2d_polygon(point, vertices):
px = point[0]
py = point[1]
angle_sum = 0
size = len(vertices)
if size < 3:
raise ValueError("len of vertices < 3")
j = size - 1
for i in range(0, size):
sx = vertices[i][0]
sy = vertices[i][1]
tx = vertices[j][0]
ty = vertices[j][1]
# 0
# y = kx + b, -y + kx + b = 0
k = (sy - ty) / (sx - tx + 0.000000000001) # 0
b = sy - k * sx
dis = fabs(k * px - 1 * py + b) / sqrt(k * k + 1)
if dis < 0.000001: #
if sx <= px <= tx or tx <= px <= sx: # ，
return True
#
angle = atan2(sy - py, sx - px) - atan2(ty - py, tx - px)
# angle -π π
if angle >= math.pi:
angle = angle - math.pi * 2
elif angle <= -math.pi:
angle = angle + math.pi * 2
#
angle_sum += angle
j = i
# 2*pi ， ，
return fabs(angle_sum - math.pi * 2) < 0.00000000001二、どのように1つの3次元の点が1つの空間の中の多角形の中で判断します
アルゴリズム思想.
まずpointと多角形が存在する平面の距離を計算し、距離が0より大きいと平面上ではなく、多角形の内部では不可能である.次に、3 D平面を2 D平面に下げ(成分を直接削除)、3 D点を2 D点に下げ、2 D平面内で点がポリゴン内にあるかどうかを判断する方法によって、点が3 Dポリゴン内にあるかどうかを判断します.3 D平面を2 D平面に下げることができる理由は、ある座標面に1つの平面を投影すると、投影前の点がポリゴン内にあれば、投影後もポリゴン内にあるからです.もちろん、上記の結論の成立条件は、多角形のある平面Aが投影された座標面Bに垂直にならないことである.法ベクトルの成分が0の場合、多角形のある平面Aがある座標面Bに垂直であることを示し、多角形を座標面Bに投影し、投影結果が1本の線であると、点が多角形内にあるか否かを判断できない.
次に、投影方法について説明します.
特殊な場合、多角形が存在する平面Aの法線ベクトルが(0,0,a)、aが非0定数の場合、平面Aは座標面xOyに平行であるため、pointと頂点のz成分を削除すると、平面Aの座標面におけるxOyの投影が得られ、この場合、2次元の関数を呼び出して点が多角形内にあるか否かを判断することができる.同様に、平面Aの法線ベクトルが(0,a,0)、(a,0,0)、aが非ゼロ定数の場合、pointと頂点のy成分またはx成分を削除することによって、成分が投影される.
平面Aの法線ベクトルが(a,b,0)、a,bが非ゼロ定数の場合、平面Aは座標面xOyに垂直であるため、xOy面に投影することができず、他の2つの座標面に投影することができる.したがって、pointと頂点のxまたはy成分を削除することで、ポリゴンの投影を得ることができます.
平面Aの法線ベクトルの成分が0でなければ、任意に1つの成分を削除すれば投影が完了する.
以上より,投影を完了する方法はpointと頂点セットを削除し,法ベクトルが0のいずれの成分でもない.
次にPythonコードを示します.このPythonコードに基づいて他の言語のコードに書き換えることができます.
'''
@description point vertices， normal
@param point List(3) List， 。
@param normal List(3) List， 。
@param vertices List(n>3)[List(3)] n List。
@return ， True， False。
'''
def is_in_3d_polygon(point, normal, vertices):
#
local_v = []
for v in vertices:
local_v.append(v.copy())
local_p = point.copy()
# ,
na = normal[0]
nb = normal[1]
nc = normal[2]
d = -(na * local_v[0][0] + nb * local_v[0][1] + nc * local_v[0][2])
distance = fabs(na * local_p[0] + nb * local_p[1] + nc * local_p[2] + d) \
/ (sqrt(na * na + nb * nb + nc * nc))
if distance > 0: # ，
# print('distance > 0')
return False
index = 2 # z
if normal[0] != 0: # x
index = 0
elif normal[1] != 0: # y
index = 1
elif normal[2] != 0: # z
index = 2
else:
raise ValueError('All elem in normal is zero')
# point
del local_p[index]
for i in range(0, len(local_v) - 1):
del local_v[i][index]
# 。
return is_in_2d_polygon(local_p, local_v)
三、最後に、上述の2つのコードのテスト例を示す.
def test_2d():
point1 = [0, 0] #
point2 = [-2, -2] #
point3 = [0, -2] #
point4 = [0, -2.1] #
#
vertices = [[-2, -2], [2, -2], [0, 4]]
assert is_in_2d_polygon(point1, vertices)
assert is_in_2d_polygon(point2, vertices)
assert is_in_2d_polygon(point3, vertices)
assert not is_in_2d_polygon(point4, vertices)
#
vertices = [[-2, -2], [2, -2], [2, 2], [-2, 2]]
assert is_in_2d_polygon(point1, vertices)
assert is_in_2d_polygon(point2, vertices)
assert is_in_2d_polygon(point3, vertices)
assert not is_in_2d_polygon(point4, vertices)
#
vertices = [[-2, -2], [2, -2], [2, 2], [0, 0], [-2, 2]]
point5 = [0, 1]
assert is_in_2d_polygon(point1, vertices)
assert is_in_2d_polygon(point2, vertices)
assert is_in_2d_polygon(point3, vertices)
assert not is_in_2d_polygon(point4, vertices)
assert not is_in_2d_polygon(point5, vertices)
print('test_2d：all tests passed')
def test_3d():
p1 = [0, 0, 1] #
p2 = [-2, -2, 1] #
p3 = [0, -2, 1] #
p4 = [0, -2.1, 1] #
# xOy
v = [[-2, -2, 1], [2, -2, 1], [0, 2, 1]] #
n = [0, 0, 1] #
assert is_in_3d_polygon(p1, n, v)
assert is_in_3d_polygon(p2, n, v)
assert is_in_3d_polygon(p3, n, v)
assert not is_in_3d_polygon(p4, n, v)
#
v = [[-2, -2, -1], [2, -2, -1], [2, 2, 1], [-2, 2, 1]] #
n = get_normal(v[0], v[1], v[2]) #
p1 = [0, 0, 0] #
p2 = [-2, -2, -1] #
p3 = [0, -2, -1] #
p4 = [0, -2.2, -1] #
p5 = [-3, -2, -1] # ，
assert is_in_3d_polygon(p1, n, v)
assert is_in_3d_polygon(p2, n, v)
assert is_in_3d_polygon(p3, n, v)
assert not is_in_3d_polygon(p4, n, v)
assert not is_in_3d_polygon(p5, n, v)
print('test_3d: all tests passed')
'''
。
'''
def get_normal(point_a, point_b, point_c):
a = [0, 0, 0]
b = [0, 0, 0]
# a
a[0] = point_a[0] - point_b[0]
a[1] = point_a[1] - point_b[1]
a[2] = point_a[2] - point_b[2]
# b
b[0] = point_a[0] - point_c[0]
b[1] = point_a[1] - point_c[1]
b[2] = point_a[2] - point_c[2]
#
normal = [0, 0, 0]
normal[0] = a[1] * b[2] - a[2] * b[1]
normal[1] = a[2] * b[0] - a[0] * b[2]
normal[2] = a[0] * b[1] - a[1] * b[0]
# 0，
if normal[0] == 0 and normal[1] == 0 and normal[2] == 0:
return None
else:
return normal
if __name__ == '__main__':
test_2d()
test_3d()