2

2セットの2Dポイントのセットがあります。ユークリッド座標に従って、集合Bが集合Aの凸包に完全にまたは部分的に含まれているかどうかを確認したいと思います。

包含を説明するために、次の例が役立つかもしれません

次のセットを考えてみましょう

   A={(5,5),(10,10),(5,10),(0,5)}

   B={(3,3),(5,8)} partially included in convex hull of A

   C={(1,5),(5,8)} fully included in convex hull of A

   D={(1,1),(3,3)} is not included in convex hull of A

どうもありがとう

4

2 に答える 2

2

Matplotlibには、かなり高速なpoint_in_poly関数があります。これはmatplotlibのドキュメントから直接引用されています：nxutils

[25]の場合：numpyをnpとしてインポートします
[26]の場合：matplotlib.nxutilsをnxとしてインポートします
[27]の場合：verts = np.array（[[0,0]、[0、1]、[1、1]、[1,0]]、float）
[28]の場合：nx.pnpoly（0.5、0.5、verts）
アウト[28]：1
[29]の場合：nx.pnpoly（0.5、1.5、verts）
Out [29]：0
[30]の場合：points = np.random.rand（10,2）* 2
[31]：ポイント
Out [31]：
配列（[[1.03597426、0.61029911]、
       [1.94061056、0.65233947]、
       [1.08593748、1.16010789]、
       [0.9255139、1.79098751]、
       [1.54564936、1.15604046]、
       [1.71514397、1.26147554]、
       [1.19133536、0.56787764]、
       [0.40939549、0.35190339]、
       [1.8944715、0.61785408]、
       [0.03128518、0.48144145]]）
[32]の場合：nx.points_inside_poly（points、verts）
Out [32]：array（[False、False、False、False、False、False、False、True、False、True]、dtype = bool）

その後、セット内の各ポイントをテストし、両方、一方、またはどちらも頂点の内側にないかどうかを判断するだけです。

于 2012-07-24T13:46:08.293 に答える
2

Pythonで点のセットの凸包を見つける1つの方法は、でDelaunay三角測量関数を使用することscipy.spatialです。ポイントのセットが与えられると、属性を持つオブジェクトを返します。これconvex_hullは、ポリゴンのエッジに対応する元のポイントのセットへのインデックスのペアで構成される配列です。厄介なことに、これらは順序付けられていないため、これらのポイントを含むポリゴンを再構築する必要があります（たとえば、次のように）。

import numpy as np
import matplotlib.nxutils
import scipy.spatial

def find_convex_hull(points):
  triangulation = scipy.spatial.Delaunay(points)
  unordered = list(triangulation.convex_hull)
  ordered = list(unordered.pop(0))
  while len(unordered) > 0:
    next = (i for i, seg in enumerate(unordered) if ordered[-1] in seg).next()
    ordered += [point for point in unordered.pop(next) if point != ordered[-1]]
  return points[ordered]

@ user1443118で提案されているように、のpoints_inside_poly関数をmatplotlib.nxutils使用して、凸包に対応する結果のポリゴンに点が存在するかどうかをテストできます。これにより、交差度を計算するための次の関数が得られます。

def inclusion(points_a, points_b):
  ch_a = find_convex_hull(points_a)
  return (1.0 * matplotlib.nxutils.points_inside_poly(points_b, ch_a)).mean()

したがって、以下に示すように、いくつかのポイントのセット（元の例のようなプロパティを使用）が与えられます。

A = np.random.randn(100, 2)
B = np.array([2,0]) + 0.5 * np.random.randn(100, 2)
C = 0.5 * np.random.randn(100, 2)
D = np.array([5,0]) + 0.5 * np.random.randn(100, 2)

ここに画像の説明を入力してください

包含度は次のように計算できます。

>>> inclusion(A, B)
0.44

>>> inclusion(A, C)
1.0

>>> inclusion(A, D)
0.0

points_in_polyただし、最後に、関数が必ずしもポリゴン境界上のポイントを内側にあるとは限らないことに注意してください（基になる関数がこのように動作する理由については、ここを参照してください）。このため、元の例のセットCは、点（1,5）がAの凸包上にあり、カウントされないため、部分的にのみ含まれます。

于 2012-07-25T08:44:08.693 に答える