У меня есть облако точек, и я хотел бы обнаружить появление определенных шаблонов точек в моем коде.
Допустим, у меня есть 1000 точек в трехмерном пространстве, и я хочу обнаружить все экземпляры 3 точек, которые образуют форму 'L', где каждый сегмент L имеет определенную длину. Облако точек может не иметь точных совпадений, но может быть очень близко (т. Е. В облаке точек длина сегмента 'L' может быть немного больше / короче идеального)
Моя первоначальная идея была примерно такой:
- записать расстояние между всеми точками в форме, которую мы пытаемся обнаружить
- создать пустую «потенциальную фигуру»
- для каждой точки в нашей потенциальной форме, изучите все точки, которые находятся на / около расстояний, найденных в части 1)
- Если мы находим точку, добавляем ее к нашей потенциальной форме и повторяем часть 3), пока у нас не появятся все точки. Затем проверьте углы между точками, чтобы убедиться, что форма действительно правильная. Если не правильно, мы переходим к следующему пункту и начинаем снова
Проблема в том, что у этого подхода ужасное время выполнения. В идеале я хотел бы иметь какую-то структуру данных, чтобы ускорить мои запросы для «Найти все точки, которые находятся между distanceMin и distanceMax от заданной точки. Может кто-нибудь указать мне на некоторые полезные структуры данных, которые могут помочь.
Я думал о том, чтобы поместить все точки в октри, чтобы ускорить время доступа.
Любой другой совет, как улучшить время работы? Эвристика для ускорения вещей?
Примечание: фигуры, которые я пытаюсь найти, являются переменными. Они не всегда будут «L». Я пробовал смотреть на грубые преобразования, но они, кажется, полезны только для обнаружения определенных заранее определенных форм, таких как линии / круги.