Найти минимальный набор лучей, пересекающих все вокселы

Question

Ладно, сначала я не был уверен, что это было лучше подходит для MathSO, так что извиняйтесь, если он нуждается в миграции.

У меня есть трехмерная сетка точек (представляющая центры вокселей) с шагом, изменяющимся в каждом измерении, но регулярным. Например, разрешение может составлять 100 на 50-40 для объекта с кубической формой.

Давая мне nVox = 200,000.

Для каждого вокселя - я хотел бы использовать лучи (nVox - 1), заканчивающиеся в центре и исходящие от каждого из других вокселей.

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

В начале, то очевидно, что вам нужно всего лишь вычислить

[nVox * (nVox - 1)]/2 

лучей, а другая половина будет просто в противоположных направлениях. В 2D случае также легко объединить все те, что параллельны одной из осей сетки (и двух диагоналей).

Итак, как мне найти минимальный набор лучей, которые мне нужны, чтобы пройти от всех воксельных центров, ко всем остальным?

Если кто-то может указать мне в правильном направлении, это было бы здорово. Любая помощь будет очень оценена.

Answer 1

Ваша проблема действительно не в трех измерениях каким-либо определенным образом. Вся концептуальная сложность присутствует в двумерном случае.

Вместо того, чтобы индивидуально подключать точки, подумайте о наборе линий, которые проходят через по крайней мере две точки на вашей сетке. Таким образом, вместо того, чтобы сначала думать о точках, подумайте о направлениях. Для 2-D эти направления являются наклонами линий. Эти склоны должны быть рациональными числами, поскольку они пересекают точки на целочисленной решетке. Поскольку у вас есть конечная решетка, числитель и знаменатель наклона могут быть ограничены размером фигуры. Таким образом, ваша основная проблема заключается в перечислении возможных наклонов для рациональных чисел ограниченной «высоты» (математический жаргон).

Существует алгоритм для этого. Это тот, который используется для генерации уменьшенных фракций Farey sequence. Если ваша цифра равна N пикселям, то в общем случае будет наклон с знаменателем N, но не может быть наклон в приведенной форме с знаменателем> N; это не поместилось.

С наклонами от 0 до 1 легче справляться. Вы получаете другие направления двумя операциями: отрицание наклона и взаимозаменяемость осей. Для трех измерений вам нужно два наклона для определения направления.

Для произвольного направления (не обязательно рационального, как указано выше) существует перпендикулярное линейное пространство размерности k-1; для 3-D это плоскость. Проецирование трехмерного параллелепипеда на эту плоскость дает шестиугольник вообще; две вершины выступают во внутреннюю часть, шесть - к вершинам шестиугольника.

Для данного дискретного направления на целочисленной решетке имеется минимальная ограничивающая рамка, так что две противоположные вершины лежат вдоль этого направления. Пока этот ограничивающий прямоугольник помещается внутри вашей исходной сетки, каждая из внутренних точек проекции соответствует линии, которая пересекает вашу сетку не менее чем в двух точках.

Таким образом, перечислите направления, затем для каждого направления укажите, где это направление пересекает вашу сетку, по крайней мере, в двух точках.