Доброго всем времени суток!
Из темы по Delphi меня отправили сюда.

Задача такая: найти точки, лежащие на определенном расстоянии до ломанной.

Как реализовано мною на данный момент:
1. Рассматриваем ломанную как набор отрезков;
2. Производим поиск точек, которые лежат в пределах концов отрезка (скалярным произведением векторов);
3. Если точка лежит в пределах отрезка, то вычисляем расстояние от нее до отрезка. Для этого находим высоту треугольника, который образовывают точки и концы отрезка.
4. Если высота оказывает меньше или равной заданному расстоянию, то добавляем точку в массив для дальнейшей работы.

В чем минус такого подхода - мне необходимо работать с миллионами точек (минимум несколько десятков тысяч, но чаще счет идет на миллионы). Ломанных тоже не мало - сотни или же тысячи, каждая состоит из нескольких десятков отрезков. Соответственно расчет занимает очень много времени - так как для каждого отрезка каждой ломанной производится нереально огромное количество вычислений.

Вопрос такой - есть ли возможность упростить поиск точек? Если какой-то способ вычислять расстояние до ломанной не разбивая ее на отрезки, а рассматривая целиком?

форма ломаной - ближе к прямой или улитки всякие могут быть?

какое примерно соотношение между длиной орезка ломаной и расстоянием для поиска (1:100, 1:10, 1:1, 10:1, 100:1, ...)?

какой процент точек обычно попадает в нужную область (1, 10, 99)?

с ответами на эти вопросы можно будет посоветовать что-то...

2) Раздвигаем отрезок в обе стороны на макс. расстояние, когда точка ещё "возле отрезка". Получаем прямоугольник. Эффективный поиск точек, лежащих внутри прямоугольника, заданного координатами вершин, вроде уже обсуждался...
3) Строим окружности вокруг концов отрезка радиусом, равным макс. расстоянию, когда точка ещё "возле отрезка". Эффективный поиск точек, лежащих внутри окружности с известным центром и радиусом, вроде уже обсуждался...


Для начала - кластеризовать пространство, особенно если элементы ломаных и расстояние "нахождения рядом"по сравнению с пространством малы, а точки расположены более-менее равномерно.

Форма ломанной ближе к прямой. По сути это аппроксимация провода... поэтому это наверно даже ближе к параболе.
Соотношение между длиной отрезка и расстоянием до точки может быть разным, но чаще всего это 1:1 или 1:2
Процент попадания опять же разнится (все зависит от плотности точек), в один отрезок укладывается менее 1% точек.

Что, если попробовать как-то так:

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

сначала написал кучу всего для случая с одной ломаной, потом заметил, что ломаных много 

тогда уже можно строить более-менее сложные структуры

т.к. ломаных меньше, то лучше на них, даже на их отрезках

1. дерево:
разбиваем пространство на две половины по какой-нибудь оси так, чтобы слева и справа было приблизительно одинаковое количество отрезков
с половинами поступаем так же, пока не дойдём до достаточно маленьких наборов отрезков
ищем так же - смотрим, расстояние от каждой половины до точки, если больше нужного - отбрасываем всю половину, иначе анализируем её части
http://en.wikipedia.org/wiki/K-d_tree

2. сетка:
просто делим пространство на клетки, как в тетради в клеточку
в каждой клетке записываем номера отрезков, касающихся её
для поиска смотрим, какие клетки находятся вблизи точки и проверяем их отрезки

Добавлено через 1 минуту и 17 секунд
вспомнил, что уже описывал это: http://forum.vingrad.ru/index.php?showtopi...t&p=2528263

Мда, все не так просто как хотелось бы.

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