Сортировка облака точек по неструктурированной сетке из шестигранных ячеек

Вопрос

Как бы вы отсортировали облако точек относительно неструктурированной сетки шестигранных ячеек?

Каждая ячейка имеет центр и уникальный ярлык для ее представления. В основном есть две точки облаков (исходное облако точек и облако точек центров ячеек), но информация о геометрии ячейки (ограничивающая рамка) может быть полезной, я не уверен.

Полученные результаты

Я немного расспросил и искал литературу:

если сетка является шестигранной и неструктурированной, задача сводится к поиску ортогонального диапазона. Для этого чаще всего используются деревья kd. Если сетка уточняется на основе структуры данных октодерева, алгоритм поиска диапазона может быть построен вокруг нее. Цель состоит в том, чтобы избежать работы с прямой геометрией сетки и сконцентрироваться на облаке точек A - отношении облака точек B. Облако точек A: точки запроса, облако точек B: центры ячеек сетки.

Важное примечание: этот ответ не отвечает на фактический вопрос, но он был оставлен без ответа для каждого запроса. Я смущенно перепутал шестигранные и шестиугольные. Речь идет о сортировке точек в произвольные гексаэдрические ячейки в 3D, в то время как это решение сортирует точки в правильные шестиугольные ячейки в 2D, или нерегулярные, которые соответствуют некоторому тесселяции Вороного в любом измерении. Этот метод применим только в том случае, если сетка была сгенерирована как тесселяция Вороного в первую очередь (что, кажется , иногда используется подход ).

Я не уверен, что вы подразумеваете под сортировкой здесь, но я предполагаю, что вы хотите отсортировать точку в шестиугольные ячейки на плоскости.

Mathematica - это то, что я знаю, поэтому я собираюсь показать вам, как это сделать в Mathematica, но этот метод можно перенести на другие системы. Идея состоит в том, что гексагональная решетка является двойственной треугольной: она может быть сгенерирована как диаграмма Вороного точек в треугольном расположении. Точка из облака принадлежит данному шестиугольнику, если она ближе к центру этого шестиугольника, чем к центру любого другого шестиугольника.

Этот метод будет работать и для сеток различной формы, при условии, что они могут быть сгенерированы как диаграмма Вороного некоторого точечного расположения. (Например, шестиугольники не должны быть регулярными.)

Давайте сгенерируем сетку. Это треугольная решетка:

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]

Его дуал - это шестиугольный, который нас интересует:

DiagramPlot[points, LabelPoints -> False]

Это создает функцию, nfкоторая находит индекс центра шестиугольника, к которому ближе всего находится точка облачности. Это ключ к методу:

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

Теперь давайте сгенерируем облако из 1000 случайных точек и отсортируем их по nf:

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

indices = First /@ nf /@ cloud;

indicesсодержит индексы центров, к которым каждая точка облачности ближе всего. Это информация, которая нам нужна. Теперь мы можем сделать из них гистограмму ...

Histogram[indices]

... или раскрась каждого из них ...

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

... или сделайте какую-нибудь необычную визуализацию, какую захотите.

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 - #] &)]

Ключевым моментом здесь была функция, которая находит ближайшую точку к чему-либо ( Nearest). В Mathematica это встроено, но есть шанс, что ваша система этого не делает. Если это так, пожалуйста, ознакомьтесь с этим вопросом о том, как эффективно реализовать такую ​​функцию (или просто используйте наивную линейную реализацию времени, если у вас нет большого количества точек для обработки).