最小の最近傍距離と最大の密度を持つ3D空間で確率的に与えられた点をサンプリングします

5
Shaun Han 2021-01-11 05:31.

私が持っているn3次元空間の点を。すべての最近傍距離がr。より大きい点のサブセットを確率的にサンプリングしたいと思います。サブセットのサイズmは不明ですが、サンプリングされたポイントをできるだけ密にしたいと思います。

同様の質問がありますが、それらはすべて、特定のポイントからサンプリングするのではなく、ポイントを生成することに関するものです。
最小の最近傍距離で3D空間にランダムな点を生成します

それぞれの間の距離が最小の3次元ランダムポイントを生成しますか?

300個のランダムな3Dポイントがあるとしましょう。

import numpy as np
n = 300
points = np.random.uniform(0, 10, size=(n, 3))

最大化しながらm最小の最近傍距離でポイントのサブセットを取得するための最速の方法は何ですか?r = 1m

3 answers

2
David Eisenstat 2021-01-14 15:00.

おそらく効率的な二基準近似スキームがありますが、整数計画法が平均して非常に速いのになぜわざわざするのでしょうか。

import numpy as np

n = 300
points = np.random.uniform(0, 10, size=(n, 3))

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver("SCIP")
variables = [solver.BoolVar("x[{}]".format(i)) for i in range(n)]
solver.Maximize(sum(variables))
for j, q in enumerate(points):
    for i, p in enumerate(points[:j]):
        if np.linalg.norm(p - q) <= 1:
            solver.Add(variables[i] + variables[j] <= 1)
solver.EnableOutput()
solver.Solve()
print(len([i for (i, variable) in enumerate(variables) if variable.SolutionValue()]))
1
Daniel F 2021-01-18 23:16.

これはサブセットの最適な大きさではありませんがKDTree、距離の計算を最適化するために使用して、それほど長くはかからずに近くにある必要があります。

from scipy.spatial import KDTree
import numpy as np

def space_sample(n = 300, low = 0, high = 10, dist = 1):
    points = np.random.uniform(low, high, size=(n, 3))
    k = KDTree(points)
    pairs = np.array(list(k.query_pairs(dist)))
    
    def reduce_pairs(pairs, remove = []):  #iteratively remove the most connected node
        p = pairs[~np.isin(pairs, remove).any(1)]
        if p.size >0:
            count = np.bincount(p.flatten(), minlength = n)
            r = remove + [count.argmax()]
            return reduce_pairs(p, r)
        else:
            return remove
    
    return np.array([p for i, p in enumerate(points) if not(i in reduce_pairs(pairs))])

subset = space_sample()

最も接続されているノードを繰り返し削除することは最適ではありませんが(300ポイントのうち約200ポイントを維持します)、最適に近い最速のアルゴリズムである可能性があります(ランダムに削除するだけで高速になる唯一の方法です)。あなたはおそらく@njit reduce_pairsその部分をより速くすることができます(後で時間があれば試してみます)。

0
Shaun Han 2021-01-19 14:07.

@David Eisenstatの回答を30の与えられたポイントでテストします:

from ortools.linear_solver import pywraplp
import numpy as np

def subset_David_Eisenstat(points, r):
    solver = pywraplp.Solver.CreateSolver("SCIP")
    variables = [solver.BoolVar("x[{}]".format(i)) for i in range(len(points))]
    solver.Maximize(sum(variables))
    for j, q in enumerate(points):
        for i, p in enumerate(points[:j]):
            if np.linalg.norm(p - q) <= r:
                solver.Add(variables[i] + variables[j] <= 1)
    solver.EnableOutput()
    solver.Solve()
    indices = [i for (i, variable) in enumerate(variables) if variable.SolutionValue()]
    return points[indices]

points = np.array(
[[ 7.32837882, 12.12765786, 15.01412241],
 [ 8.25164031, 11.14830379, 15.01412241],
 [ 8.21790113, 13.05647987, 13.05647987],
 [ 7.30031002, 13.08276009, 14.05452502],
 [ 9.18056467, 12.0800735 , 13.05183844],
 [ 9.17929647, 11.11270337, 14.03027534],
 [ 7.64737905, 11.48906945, 15.34274827],
 [ 7.01315886, 12.77870699, 14.70301668],
 [ 8.88132414, 10.81243313, 14.68685022],
 [ 7.60617372, 13.39792166, 13.39792166],
 [ 8.85967682, 12.72946394, 12.72946394],
 [ 9.50060705, 11.43361294, 13.37866092],
 [ 8.21790113, 12.08471494, 14.02824481],
 [ 7.32837882, 12.12765786, 16.98587759],
 [ 8.25164031, 11.14830379, 16.98587759],
 [ 7.30031002, 13.08276009, 17.94547498],
 [ 8.21790113, 13.05647987, 18.94352013],
 [ 9.17929647, 11.11270337, 17.96972466],
 [ 9.18056467, 12.0800735 , 18.94816156],
 [ 7.64737905, 11.48906945, 16.65725173],
 [ 7.01315886, 12.77870699, 17.29698332],
 [ 8.88132414, 10.81243313, 17.31314978],
 [ 7.60617372, 13.39792166, 18.60207834],
 [ 8.85967682, 12.72946394, 19.27053606],
 [ 9.50060705, 11.43361294, 18.62133908],
 [ 8.21790113, 12.08471494, 17.97175519],
 [ 7.32837882, 15.01412241, 12.12765786],
 [ 8.25164031, 15.01412241, 11.14830379],
 [ 7.30031002, 14.05452502, 13.08276009],
 [ 9.18056467, 13.05183844, 12.0800735 ],])

予想される最小距離が1の場合:

subset1 = subset_David_Eisenstat(points, r=1.)
print(len(subset1))
# Output: 18

最小距離を確認してください。

from scipy.spatial.distance import cdist
dist = cdist(subset1, subset1, metric='euclidean')
# Delete diagonal
res = dist[~np.eye(dist.shape[0],dtype=bool)].reshape(dist.shape[0],-1)
print(np.min(res))
# Output: 1.3285513450926985

予想される最小距離を2に変更します。

subset2 = subset_David_Eisenstat(points, r=2.)
print(len(subset2))
# Output: 10

最小距離を確認してください。

from scipy.spatial.distance import cdist
dist = cdist(subset2, subset2, metric='euclidean')
# Delete diagonal
res = dist[~np.eye(dist.shape[0],dtype=bool)].reshape(dist.shape[0],-1)
print(np.min(res))
# Output: 2.0612041004376223

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

科学者は髪が灰色になる理由の別の可能な説明を見つけます

科学者は髪が灰色になる理由の別の可能な説明を見つけます

このネズミのグリズリした毛皮は、いつか人々が白斑と呼ばれるまれな状態を発症する理由を説明するのに役立つかもしれません。科学者たちは、白斑と呼ばれるまれな汚名を着せられた状態である無着色の皮膚の斑点に悩まされる人もいれば、髪が灰色になる理由を説明できる新たに発見されたメカニズムに遭遇したと考えています。

新しい若いテロリストコレクションの内部のこの外観で、神秘的で残忍な陰謀に飛び込む

新しい若いテロリストコレクションの内部のこの外観で、神秘的で残忍な陰謀に飛び込む

若いテロリストの野生のアンチヒーロー、セラに会いましょう。ほぼ3年前、Black Mask Studiosは、残忍で政治的な色合いのスリラーであるYoungTerroristsと波を起こしました。

Huluが周りを見回し、The Handmaid'sTaleを第3シーズンに更新します

Huluが周りを見回し、The Handmaid'sTaleを第3シーズンに更新します

ハンドメイドの物語のエリザベスモス昨夜、アイオワ上院は、胎児の心拍が検出された後、ほとんどの妊娠中絶を禁止する、いわゆる「心拍」法案を早急に追跡しました。妊娠。また、HuluはThe Handmaid'sTaleを第3シーズンに更新することを決定しました。

ラストコール:どのように風邪と戦うのですか?

ラストコール:どのように風邪と戦うのですか?

これは実際に機能しますか?病気になってから久しぶりですが(ジンクス!)、今朝目が覚めたとき、副鼻腔の奥にひどい痛みを感じ、病気になりそうです。風邪が嫌いです。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

ケイト・ミドルトンはロンドンの水辺で一日を過ごし、さらにジェニファー・ロペス、ジュリアン・ハフなど

ケイト・ミドルトンはロンドンの水辺で一日を過ごし、さらにジェニファー・ロペス、ジュリアン・ハフなど

ケイト・ミドルトンはロンドンの水辺で 1 日を過ごし、ジェニファー・ロペス、ジュリアン・ハフなども。ハリウッドからニューヨークまで、そしてその間のあらゆる場所で、お気に入りのスターの活躍をご覧ください!

ウィスコンシン川でのナイフ攻撃で 17 歳の少年が刺されて死亡、他の 4 人が負傷したままになっている

ウィスコンシン川でのナイフ攻撃で 17 歳の少年が刺されて死亡、他の 4 人が負傷したままになっている

捜査官は、グループと容疑者が攻撃の前にお互いを知っていたかどうかを調べています

実際に変換するコンテンツ戦略を作成することを想像してみてください。それが可能だ。

実際に変換するコンテンツ戦略を作成することを想像してみてください。それが可能だ。

2021 年には、サービスを提供する顧客と顧客に伝えるストーリーについて知っていることをすべて再考することをお勧めします。あとずさりする。

マンモスロスは私の心を愛に開いた

マンモスロスは私の心を愛に開いた

フェリックス ザ キャットの 9 歳の誕生日の日に、大人になってからの最大の損失の 1 つである 2013 年のソフィーを思い出します。私はこのエッセイを書き、2013 年にこのプラットフォームで簡単に共有しました。

あなたがインターネットがあなたに望んでいる人になれないとき

あなたがインターネットがあなたに望んでいる人になれないとき

私は「列車事故」という言葉が嫌いです。人々は自分自身の道徳的羅針盤に安らぎを覚え、そうすることで自分自身が判断を下していることに気づきます。

DFINITY ブロックチェーンの分散型クラウド ビジョン

編集者注: アーカイブ目的で保存されている DFINITY ブログの古い資料を表示しています。

DFINITY ブロックチェーンの分散型クラウド ビジョン

この投稿では、DFINITY チームの分散型クラウドのビジョンと、それが従来のブロックチェーンやアマゾン ウェブ サービスなどの既存のクラウド プロバイダーとどのように関連しているかを探ります。大規模なネットワークによって適用される DFINITY テクノロジのデモンストレーションが 2017 年の秋に行われ、その後、非営利財団を支援するための主要な資金調達が行われ、「オープン クラウド」ネットワークは 2018 年の初夏に開始される予定です。 .

Language