Блог

У меня есть N-мерная (обычная) сетка с данными, которая не заполняет ее объем полностью, но должна быть выпуклой. Так, например, в 2D это нормально (1 = существует, 0 = отсутствует):

0011111100
0111111110
1111111111
0011111100
0000011100

Но это не:

0011111100
0111101110
1111111111
0011111000
0000011100

Я хочу найти дополнительные нули во втором примере (выделены жирным шрифтом). И я хочу сделать это более чем в 2 измерениях.

Единственный способ, который я могу придумать сейчас, — это получить все возможные координаты в N-1 измерениях и проверить в N-м измерении, является ли оно выпуклым, что просто означает поиск первой и последней точек данных в этом измерении и проверку, отсутствует ли какая-либо точка между ними. Но мне пришлось бы делать это в каждом измерении и для каждого среза в этом измерении.

Должно быть более простое решение, верно?

Вам нужно будет выяснить и понять алгоритмы, которые помогают получить «многомерную выпуклую оболочку» для данной многомерной сетки. Это немного сложно, и я не могу объяснить полноценное решение в посте, но могу дать приведенные ниже указания.

• ВЫПУКЛАЯ ОБОЛОЧКА В 3 ИЗМЕРЕНИЯХ
• Scipy: выпуклые оболочки в N измерениях.
• CGAL: Библиотека алгоритмов вычислительной геометрии
• Обертка от яблока Ньютона

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

Чтобы легко решить эту проблему, рассмотрим противоположную задачу: «Как можно найти пространство, окружающее фигуру?»

Если вы знаете, как заполнить все пространство, окружающее фигуру, то все пиксели или воксели, которые не являются частью этого пустого пространства, должны быть частью выпуклой оболочки. В следующем примере мы:

1. заполните все окружающее 0 пространство -
2. заменить - на 0 и 0 на 1 (в результате получается выпуклая оболочка)
3. XOR с исходной моделью

 01110        -111-        01110        00000
11010   ->   1101-   ->   11110   ->   00100
11111        11111        11111        00000
  

В конечном результате a 1 теперь представляет собой замкнутое пустое пространство. Обратите внимание, что - это может быть представлено как 2 или 3 , чтобы это сработало, и нам временно понадобилось бы два бита на воксель, а не только один.

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

Реализация второго и третьего шага должна быть тривиальной.

Избегание «тролеанской» логики

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

• flood- заполнить нули во входном массиве с 1 вместо -
• для каждого заполняемого вокселя запишите 1 в отдельный выходной буфер

Затем первый шаг даст нам результат:

 10001
00001
00000
  

Теперь нам просто нужно немного перевернуть этот буфер, чтобы получить выпуклую оболочку.