Вопрос по алгоритму определения границы кривой, Возник сложный вопрос и нигде не могу найти ответ! Опции

[Prinz]

Добрый день!
Помоги пожалуйста, или хотя бы посоветуйте!
Мне стоит задача придумать алгоритм, с помощью которого можно определить только внешнюю границу любой кривой линии, любой любой, и только внешнюю. Внутрь заходить не должны.
В наличии только координыты точек исходной кривой!
Я сам придумал с нуля четыре алгаритма, все по своему хороши, но меняется какое-то уовие и они подвисают.
Посоветуйте что-нибудь, хотя бы где почитать.
Буду рад любому ответу!
Заранее спасибо!



Замечание модератора. Заголовок темы следует давать осмысленный, как того требует п.2.1в Правил форума. Отредактировал.
rezident.

[Artem_Petrik]

По моему, то, что у вас точки соединены линиями всех только запутывает.
На мой взгляд задачу следовало бы сформулировать так: Имеется множество точек на плоскости, необходимо
построить замкнутую ломаную таким образом, чтобы ни одна из точек не осталась за границей области, очерченной этой ломаной. Ломаная при этом будет соединять некоторые, но не все, имеющиеся точки. Потом уже, при необходимости от полученной кривой можно бдет сделать отступ, чтоб был запас, как на приведенных рисунках.
Простейший способ решения здесь уже указывался, про треугольники, надо только брать треугольники не только из близлежащих точек, а вообще из всех возможных комбинаций из трех точек.
Т. е. берем три точки, проверяем, находится ли какая-либо точка внутри полученного треугольника, и, если находится - исключаем ее из множества точек, по которым будет проведена граница. Перебираем таким образом все возможные треугольники. В результате у нас останутся только те точки, по которым нужно провести границу. Соединяем их ломаной (каждую точку с двумя ближайшими) и получаем то, что, как я понимаю, требовалось найти.
Решение довольно громоздкое, и если результат работы алгоритма будет давать удовлетворяющие вас результаты, то можно будет думать, как его упростить.

З.Ы. Придумал еще алгоритм . Соединить имеющиеся точки все со всеми, а потом исключить все линии, которые пересекаются. Останется только внешний контур.

[Prinz]

По моему, то, что у вас точки соединены линиями всех только запутывает.
На мой взгляд задачу следовало бы сформулировать так: Имеется множество точек на плоскости, необходимо
построить замкнутую ломаную таким образом, чтобы ни одна из точек не осталась за границей области, очерченной этой ломаной. Ломаная при этом будет соединять некоторые, но не все, имеющиеся точки. Потом уже, при необходимости от полученной кривой можно бдет сделать отступ, чтоб был запас, как на приведенных рисунках.

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

Нужно уменьшить число точек кривой - заменить другой ломаной с меньшим числом отрезков? И при этом, чтобы трек не "уходил" от исходного более чем на Х метров? Элементарная задачаю. По-моему: математика - первый (может быть - второй) семестр института. Наверное, это и есть основная задача. При чём тут границы - мне не понятно.

Тут впринципе если Ваш метод получится реализовать, то на некотороном удалении построить легко.

Мне надо как бы очертить зону где находится этот трек.
Для этого я думаю, что надо сначало найти границу.
Вы дали наиболее правильную трактовку задачи.
Но я ещё раз попробую написать:
Есть файл.
В нём координаты точек, по мери их поступления.
Первая точка соединяется со второй и т.д.
И т.д.
Могут возникать пересечения.
Первый рисунок не удачен, но последующии наиболее точно показывает смысл задачи!

Качественное определение "очень редко" имеет выражение в количественном представлении? Если да, то почему бы в нужных случаях не применить интерполяцию, дополнив прямую нужными точками?..

В ряде случаев это делать не надо.
А если дополнять, то дополнять придётся по всему треку!
Конечно это облегчит задачу.

Чуть выше автор говорил о фильтрации точек.

Я про фильтрацию имел ввиду, отфильтровать внутренни точки, тоесть оставить лишь одну линии - внешнюю!
Оставить только внешнии отрезки.

Ещё раз попобую задачу объяснить:
- точка
- следующая
- между ними трек
- и т.д.
- таким образом апроксимируется кривая , которая может изгибаться, как хочет, как например на моём первом рисунке.
- Нам надо построить нашу кривую, которая будет определять границу зоны, где находится наша петляющая кривая!
- Впринципе зона может быть точно по границе кривой линии (внешней)!

Спасибо ещё раз всем за подсказки.

Причина редактирования: Излишее бездумное цитирование.

[blackfin]

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

По-моему, всё просто:

1. Соединяете ваши точки в порядке их следования отрезками, получая таким образом непрерывную кривую.
2. Двигаясь от начала кривой, при каждом попадании в точку самопересечения кривой выбираете самый правый сегмент кривой и далее двигаетесь вдоль него.
3. Если начало кривой находится внутри границы зоны, в качестве начальной точки можно выбрать любую точку на границе зоны, например точку для которой координата X (или Y) минимальна (или максимальна).
При любом выборе начальной точки направление обхода кривой должно быть "против часовой стрелки".
4. Обход завершается при попадании в точку из которой обход был начат.

Сообщение отредактировал blackfin - Mar 22 2009, 14:21