numpy に座標の点群があります。ポイントの数が多い場合、ポイントがポイント クラウドの凸包内にあるかどうかを確認したいと考えています。
pyhull を試しましたが、ポイントが にあるかどうかを確認する方法がわかりませんConvexHull:
hull = ConvexHull(np.array([(1, 2), (3, 4), (3, 6)]))
for s in hull.simplices:
s.in_simplex(np.array([2, 3]))
LinAlgError が発生します: 配列は正方形でなければなりません。
scipy のみを必要とする簡単なソリューションを次に示します。
def in_hull(p, hull):
"""
Test if points in `p` are in `hull`
`p` should be a `NxK` coordinates of `N` points in `K` dimensions
`hull` is either a scipy.spatial.Delaunay object or the `MxK` array of the
coordinates of `M` points in `K`dimensions for which Delaunay triangulation
will be computed
"""
from scipy.spatial import Delaunay
if not isinstance(hull,Delaunay):
hull = Delaunay(hull)
return hull.find_simplex(p)>=0
True値が指定された凸包内にあるポイントを示すブール配列を返します。次のように使用できます。
tested = np.random.rand(20,3)
cloud = np.random.rand(50,3)
print in_hull(tested,cloud)
matplotlib がインストールされている場合は、最初の関数を呼び出して結果をプロットする次の関数を使用することもできます。Nx2配列で指定された 2D データのみ:
def plot_in_hull(p, hull):
"""
plot relative to `in_hull` for 2d data
"""
import matplotlib.pyplot as plt
from matplotlib.collections import PolyCollection, LineCollection
from scipy.spatial import Delaunay
if not isinstance(hull,Delaunay):
hull = Delaunay(hull)
# plot triangulation
poly = PolyCollection(hull.points[hull.vertices], facecolors='w', edgecolors='b')
plt.clf()
plt.title('in hull')
plt.gca().add_collection(poly)
plt.plot(hull.points[:,0], hull.points[:,1], 'o', hold=1)
# plot the convex hull
edges = set()
edge_points = []
def add_edge(i, j):
"""Add a line between the i-th and j-th points, if not in the list already"""
if (i, j) in edges or (j, i) in edges:
# already added
return
edges.add( (i, j) )
edge_points.append(hull.points[ [i, j] ])
for ia, ib in hull.convex_hull:
add_edge(ia, ib)
lines = LineCollection(edge_points, color='g')
plt.gca().add_collection(lines)
plt.show()
# plot tested points `p` - black are inside hull, red outside
inside = in_hull(p,hull)
plt.plot(p[ inside,0],p[ inside,1],'.k')
plt.plot(p[-inside,0],p[-inside,1],'.r')
こんにちは、プログラム ライブラリを使用してこれを達成する方法がわかりません。しかし、言葉で説明されたこれを達成するための簡単なアルゴリズムがあります。
まず、点群の凸包を取得します。
次に、凸包のすべてのエッジを反時計回りにループします。エッジごとに、ターゲット ポイントがそのエッジの「左」にあるかどうかを確認します。これを行うときは、エッジを凸包の周りを反時計回りに指すベクトルとして扱います。ターゲット ポイントがすべてのベクトルの「左」にある場合、そのポイントはポリゴンに含まれます。それ以外の場合は、ポリゴンの外側にあります。
この他のスタック オーバーフロー トピックには、点が線の どちらの側にあるかを見つけるための解決策が含まれています。
これは凸多角形に対してのみ機能することに注意してください。しかし、あなたは凸包を扱っているので、あなたのニーズに合うはずです。
点群の凸包を取得する方法が既にあるようです。しかし、独自に実装する必要がある場合は、ウィキペディアに凸包アルゴリズムの優れたリストがあります: 凸包 アルゴリズム
完全を期すために、貧乏人の解決策を次に示します。
import pylab
import numpy
from scipy.spatial import ConvexHull
def is_p_inside_points_hull(points, p):
global hull, new_points # Remove this line! Just for plotting!
hull = ConvexHull(points)
new_points = numpy.append(points, p, axis=0)
new_hull = ConvexHull(new_points)
if list(hull.vertices) == list(new_hull.vertices):
return True
else:
return False
# Test:
points = numpy.random.rand(10, 2) # 30 random points in 2-D
# Note: the number of points must be greater than the dimention.
p = numpy.random.rand(1, 2) # 1 random point in 2-D
print is_p_inside_points_hull(points, p)
# Plot:
pylab.plot(points[:,0], points[:,1], 'o')
for simplex in hull.simplices:
pylab.plot(points[simplex,0], points[simplex,1], 'k-')
pylab.plot(p[:,0], p[:,1], '^r')
pylab.show()
アイデアは単純です。凸包の「内側」に位置する点を追加しても、一連の点の凸包の頂点はP変化しません。とpの凸包の頂点は同じです。ただし、「外側」にある場合は、頂点を変更する必要があります。これは n 次元で機能しますが、2 回計算する必要があります。[P1, P2, ..., Pn][P1, P2, ..., Pn, p]pConvexHull
2 次元での 2 つのプロット例:
間違い：
真実：
@Charlie Brummitt の作業に基づいて、複数の点が同時に凸包内にあるかどうかを確認し、ループをより高速な線形代数に置き換えることができる、より効率的なバージョンを実装しました。
import numpy as np
from scipy.spatial.qhull import _Qhull
def in_hull(points, queries):
hull = _Qhull(b"i", points,
options=b"",
furthest_site=False,
incremental=False,
interior_point=None)
equations = hull.get_simplex_facet_array()[2].T
return np.all(queries @ equations[:-1] < - equations[-1], axis=1)
# ============== Demonstration ================
points = np.random.rand(8, 2)
queries = np.random.rand(3, 2)
print(in_hull(points, queries))
_Qhull効率のために下位クラスを使用していることに注意してください。
scipy を維持したい場合は、凸包にする必要があります (そうしました)。
>>> from scipy.spatial import ConvexHull
>>> points = np.random.rand(30, 2) # 30 random points in 2-D
>>> hull = ConvexHull(points)
次に、船体上のポイントのリストを作成します。船体をプロットするためのドキュメントのコードは次のとおりです
>>> import matplotlib.pyplot as plt
>>> plt.plot(points[:,0], points[:,1], 'o')
>>> for simplex in hull.simplices:
>>> plt.plot(points[simplex,0], points[simplex,1], 'k-')
それから始めて、船体上のポイントのリストを計算することを提案します
pts_hull = [(points[simplex,0], points[simplex,1])
for simplex in hull.simplices]
（私は試していませんが）
また、船体を計算して x、y ポイントを返す独自のコードを用意することもできます。
元のデータセットのポイントが船体上にあるかどうかを知りたい場合は、これで完了です。
あなたが望むのは、任意の点が船体の内側にあるか外側にあるかを知ることです。もう少し作業を行う必要があります。あなたがしなければならないことは
ハルの 2 つのシンプリスを結合するすべてのエッジに対して: ポイントが上か下かを決定します。
ポイントがすべての線の下またはすべての線の上にある場合、それは船体の外側にあります
スピードアップとして、ポイントが 1 つのラインより上にあり、互いに下にあるとすぐに、船体の内側になります。