Найти контур 2D неорганизованного pointcloud

Question

У меня есть набор двумерных точек, неорганизованный, и я хочу найти «контур» этого набора (а не выпуклый корпус). Я не могу использовать альфа-формы, потому что у меня есть цель скорости (менее 10 мс на среднем компьютере). Мой первый подход состоял в том, чтобы вычислить сетку и найти квадраты контуров (квадраты, которые имеют пустой квадрат, как сосед). Поэтому я считаю, что эффективно сократил количество очков (от 22000 до 3000). Но мне еще нужно уточнить этот новый набор.

Мой вопрос: как я могу найти реальные очертания точек среди моих зеленых точек?

Answer 1

После уик-энда, полного отражений, я нашел удобное решение.

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

Мы должны решить, какие квадраты считаются «контуром». Наши критерии: по крайней мере один пустой сосед и по крайней мере 3 непустых соседних.

Нам не хватает информации о подключении. Таким образом, мы выбираем квадрат «Контур», который как 2 «Контур» соседи или меньше. Затем мы выбираем одного из соседей. Из этого можно начать разложение. Мы просто обходим вокруг текущей площади, чтобы найти следующий квадрат «Контур», зная предыдущие квадраты «Контур». Наши контурные критерии не позволяют нам зайти в тупик.

Теперь мы имеем векторы связанных квадратов, и обычно, если наша форма не имеет отверстия, только один вектор связанных квадратов!

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

красные точки являются контур зеленого один. Используемая техника - это плоский барицентр.

Для набора из 28000 пунктов эта методика занимает 8 мс. Альфа-формы CGAL будут занимать в среднем 125 мс за 28000 очков.

PS: Я надеюсь, что я ясно, английский не мой Родной: s

Answer 2

Вы действительно должны использовать альфа-формы. Возможно, использовать только зеленые точки в качестве входов альфа-альфа-алгоритма.