Точки в линии

[geologic]

Щас вот еще раз продумал этот простой вопрос... Опять протестировал многочисленные средства... И в который раз задумался, а можно его все-таки решить, не имея заданного порядка точек? Если линия притом очевидна, конечно. Казалось бы, ищем обзором следующую ближайшую точку, и так далее, но... Что-то все средства на эту тему глючат, и есть подозрение, что не зря.

1. Встречал ли кто-то все-таки удачные решения?

2. Какие могут быть идеи, как решить станрадтными средствами, вроде Spatial Join и т.п.?

Взываю к коллективному разуму

[Анна]

алгоритмически такое возможно, конечно. Хотя это зависит от того, что имеется в виду под заданным порядком точек? ID линий все равно должны быть (т.е. то, что определяет, что эта группа точек относится к линии 1, эта группа точек - линия 2 и т.д.). Иначе в результате получится одна длинная линия.
В таком алгоритме нужно будет (как минимум) задавать такие параметры как угл поиска (bearing) и максимальную дистанцию поиска(tolerance) и выбор начальной точки. С другой стороны и этого скорее всего будет недостаточно, так как гипотетически может встречаться ситуация, когда будет две точки на совершенно одинаковом расстоянии и с равным углом, тогда надо будет (видимо) проверять следующую после этих двух точку, чтобы понять как провести линию... короче, вопросов много...
И опять же, для запуска такого алгоритм нужно будет ооочнь хорошо знать данные, что с точки зрения удобства и user-friendly'ности не есть хорошо. ИМХО

Похожие решения встречала, но скорее для алгоритмов типа кластрезации, диаграмм вороного и т.д. или когда надо обрисовать convex hull группы точек.

по поводу геометрических алгоритмов - очень неплохой список ссылок
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html

[geologic]

Спасибо, мощный ресурс. Буду читать. Похоже, действительно решения разумно привязывать к конкретным случаям.

Идентификатор линии само собой, но если упростить задачу - взять ОДНУ линию и нулевой допуск, т.е. когда появление дубликатов по дистанции для чисел типа float "маловероятно"? Направление ведь не так уж обязательно, хотя его задание убыстряет алгоритм. Интересно подумать, какие еще подводные камни могут встретиться?

Повторюсь, я не сочиняю инструмент, я хочу понять почему имеющиеся скрипты работают криво, а профессиональных не имеется или не слышно.