Обнаружение произвольных форм

Question

Привет,

У нас есть набор точек, которые представляют пересечение трехмерного тела и горизонтальной плоскости.Мы хотели бы обнаружить двухмерные фигуры, которые представляют поперечные сечения тела.Может быть одна или несколько таких форм.Мы нашли статьи, в которых обсуждается, как работать с изображениями с помощью Hough Transform, но у нас может быть тысячи таких точек, поэтому преобразование в изображение очень расточительно.Есть ли более простой способ сделать это?

Спасибо

Answer 1

При преобразовании 3D-модели в набор точек вы выбросили информацию, необходимую для поиска форм пересечения.Пройдите по графу связности ребер-граней вашей 3D-модели, чтобы найти точки пересечения ребер-плоскостей по порядку.

Предполагая, что у вас есть или можно построить топографию 3d-модели (некоторое количество вершин, ребра между вершинами,грани, ограниченные ребрами):

1. Перебирайте список ребер, пока не найдете тот, который пересекает тестовую плоскость, добавьте его в список
2. Выберите одну из граней, имеющих этот ребро
3. Выполните итерации по другим краям этой грани, чтобы найти следующее пересечение, добавьте его в список
4. Повторите для другой грани, которая разделяет эту грань, пока вы не вернетесь к начальной кромке

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

Есть некоторый Java-код, который делает это здесь ,и довольно изящное тестовое приложение здесь .

Управление:

• 1-5 для изменения тестового объема
• q и w для измененияколичество плоскостей запросов
• a, s и d для изменения скорости сканирования плоскостей запросов
• перетащите левой кнопкой мыши, чтобы повернуть представление
• щелкните правой кнопкой мыши-drag для поворота плоскостей запроса

Answer 2

Алгоритм / код из принятого ответа не работает для сложных особых случаев, когда плоскость пересекает некоторые вершины вогнутой поверхности.В этом случае «ходьба» графа связности граней жадно могла бы закрыть некоторые многоугольники раньше времени.

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

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