Учитывая набор поверхностей в трехмерном пространстве, я пытаюсь присвоить каждой поверхности зону, относящуюся к наименьшей трехмерной области, которую включает набор, или не использовать зону, если это неприменимо. Я также хочу определить, является ли поверхность интерфейсом между двумя зонами. Так, например, если бы у нас было 11 поверхностей, представляющих два куба, поставленных друг на друга, поверхности в верхнем кубе были бы в одной зоне, а поверхности в нижнем были бы в другой зоне (с поверхностью интерфейса, в обеих зонах).
В качестве примера я хочу взять набор поверхностей, таких как это, и превратить его в это. Каждый цвет здесь представляет зону, а серый не связан с зоной (как на откидной створке внизу).
Я провел некоторые поиски, пытаясь выяснить, придумал ли кто-нибудь уже алгоритм для этого, но я ничего не нашел (большинство, похоже, идентифицируют области, а не связывают поверхности с областью, которую они заключают). Таким образом, я пытаюсь придумать свой собственный алгоритм, и мне интересно, есть ли какие-либо другие альтернативы или будет ли работать мой метод.
Я предполагаю, что все поверхности связаны.
Моя идея заключается в следующем:
- Выберите случайную поверхность, каждая сторона которой касается ровно одной другой поверхности, и добавьте ее в зону 1.
- Добавьте каждую соединенную поверхность в зону 1 при условии, что каждая ее сторона касается ровно одной другой поверхности.
- Для тех соединенных поверхностей, которые соприкасаются более чем с одной поверхностью хотя бы одной из своих сторон, добавьте их в список «возможно».
- Для каждой новой поверхности в зоне 1 повторите шаги 2-3.
- После того, как поверхность была дважды добавлена в список «возможно», добавьте ее в зону 1 и удалите из списка «возможно». Отметьте эту поверхность как интерфейс зоны.
- Добавьте интерфейс зоны в зону 2.
- Выберите одну случайную поверхность из списка «возможно» и назначьте ее зоне 2 и очистите список «возможно».
- Повторяйте шаги 2–7 (конечно, обновляя номер зоны), пока не останется неназначенных поверхностей.
Кажется, это работает для простых сценариев (например, два куба, поставленных друг на друга), но я не уверен, есть ли какие-то сложные условия, на которые мне нужно обратить внимание, или если он развалится, когда будет больше двух зон. которые разделяют сторону.
Буду признателен за любое улучшение моего грубого алгоритма/альтернативных идей для реализации. Спасибо!
РЕДАКТИРОВАТЬ: вот еще несколько деталей в ответ на некоторые комментарии. Зона по моему определению — это просто группа поверхностей, которые полностью ограничивают трехмерную область без пробелов. Итак, если бы у меня было два куба, А и В, которые не соприкасаются, у меня было бы две зоны: одна, состоящая из всех поверхностей куба А, а другая из всех поверхностей куба В. Если бы у меня был отсутствующий куб с одной стороны, не будет никакой зоны, связанной с этими поверхностями.
Моя конечная цель — сделать автоматизированный процесс группировки поверхностей в инструменте моделирования, который я создаю. Специфика засекречена, но по существу я имею дело с моделями, в которых определенные свойства являются общими только между поверхностями в той же «зоне», как описано выше. Я хочу сделать автоматизированный процесс создания этих зон, чтобы пользователь мог применить эти свойства ко всем поверхностям в зоне сразу, а не делать это вручную.
По сути, проблема сводится к поиску наименьших трехмерных областей, полностью окруженных произвольным набором поверхностей, и отслеживанию того, какие поверхности принадлежат каким областям. Я надеюсь, что это сделает мой вопрос более ясным.
