Urutkan awan poin sehubungan dengan mesh sel heksahedral yang tidak terstruktur

Pertanyaan

Bagaimana Anda mengurutkan awan poin sehubungan dengan mesh sel heksahedral yang tidak terstruktur?

Setiap sel memiliki pusat dan label unik untuk mewakilinya. Ada dua titik awan pada dasarnya (titik awan asli, dan titik awan pusat sel), tetapi informasi geometri sel (kotak pembatas) mungkin berguna, saya tidak yakin.

Hasil

Saya telah melakukan beberapa pertanyaan di sekitar, dan mencari melalui literatur:

jika mesh heksahedral dan tidak terstruktur, masalahnya dikurangi menjadi pencarian rentang ortogonal. Untuk tujuan ini, pohon kd paling sering digunakan. Jika mesh disempurnakan berdasarkan pada struktur data octree, algoritma pencarian rentang dapat dibangun di sekitarnya. Tujuannya adalah untuk menghindari berurusan dengan geometri mesh langsung dan berkonsentrasi pada cloud titik A - hubungan cloud titik B. Cloud titik A: titik kueri, awan titik B: pusat sel mesh.

Catatan penting: Jawaban ini tidak menjawab pertanyaan aktual, tetapi dibiarkan tidak terhapus per permintaan. Dengan malu saya bingung heksahedral dan heksagonal. Pertanyaannya adalah tentang menyortir titik menjadi sel heksahedral sewenang-wenang dalam 3D sementara solusi ini mengurutkan poin menjadi sel heksagonal biasa dalam 2D, atau yang tidak teratur yang sesuai dengan beberapa tesselation Voronoi di dimensi apa pun. Metode ini hanya berlaku jika mesh yang dihasilkan sebagai Voronoi tesselation di tempat pertama (yang tampaknya merupakan pendekatan yang sering digunakan ).

Saya tidak yakin apa yang Anda maksud dengan menyortir di sini, tapi saya berasumsi Anda ingin menyortir titik menjadi tempat sampah heksagonal di pesawat.

Mathematica adalah apa yang saya ketahui, jadi saya akan menunjukkan kepada Anda bagaimana melakukannya di Mathematica, tetapi metode ini dapat diangkut ke sistem lain. Idenya adalah bahwa kisi heksagonal adalah ganda dari yang segitiga: itu dapat dihasilkan sebagai diagram Voronoi dari suatu titik dalam pengaturan segitiga. Suatu titik dari awan adalah milik segi enam yang diberikan jika lebih dekat ke pusat segi enam itu daripada ke pusat segi enam lainnya.

Metode ini akan bekerja untuk jerat dengan bentuk yang berbeda juga, asalkan mereka dapat dihasilkan sebagai diagram Voronoi dari beberapa pengaturan titik. (Misalnya, segi enam tidak perlu teratur.)

Mari kita hasilkan mesh. Ini adalah kisi segitiga:

pts = Join @@ Table[{x, Sqrt[3] y}, {x, 0, 4}, {y, 0, 2}];

points = Join[pts, TranslationTransform[{1/2, Sqrt[3]/2}] /@ pts];

Needs["ComputationalGeometry`"]
PlanarGraphPlot[points, LabelPoints -> False]

Dual adalah hexagonal yang kami tertarik:

DiagramPlot[points, LabelPoints -> False]

Ini membangun fungsi nfyang menemukan indeks pusat segi enam yang paling dekat dengan titik cloud. Ini adalah kunci dari metode ini:

nf = Nearest[N[points] -> Range@Length[points]];

Sekarang mari kita buat cloud 1000 poin acak dan urutkan dengan nf:

cloud = RandomReal[{-1/2, 5}, {1000, 2}];

indices = First /@ nf /@ cloud;

indicesberisi indeks pusat yang paling dekat dengan setiap titik cloud. Ini adalah informasi yang kami butuhkan. Sekarang kita bisa membuat histogram dari mereka ...

Histogram[indices]

... atau warna masing-masing ...

Show[
 DiagramPlot[points, LabelPoints -> False],
 Graphics@MapThread[{ColorData[3][#1], Point[#2]} &, {indices, cloud}],
 PlotRange -> All, AspectRatio -> Automatic
 ]

... atau lakukan visualisasi mewah apa pun yang kita inginkan.

tally = Tally[indices];

ListDensityPlot[Join[points, List /@ Sort[tally][[All, 2]], 2], 
 InterpolationOrder -> 0, 
 Epilog -> (Text[#2, points[[#1]]] & @@@ tally), 
 PlotRange -> {{-.5, 5}, {-.5, 5}}, Mesh -> All, 
 ColorFunction -> (ColorData["BeachColors"][1 - #] &)]

Titik kunci di sini adalah fungsi yang menemukan titik terdekat dengan sesuatu ( Nearest). Mathematica memiliki ini bawaan, tetapi ada kemungkinan sistem Anda tidak. Jika ini masalahnya, lihat pertanyaan ini tentang cara menerapkan fungsi seperti itu secara efisien (atau ikuti saja penerapan waktu linear yang naif jika Anda tidak memiliki banyak poin untuk diproses).