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

[Prinz]

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



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

[Prinz]

Сегодня попробовал написать алгоритм по совету.
НА простых треках работает всё, но есть треки, где касичкой идёт всё,там всё намертво повисает.

Нисего не помогает. ((((((((((((((((((((((
У меня горе просто!
Есть очень кривыии линии.
Со всяки провальчиками, пычками.
ОТфильтруешь одно, третье вылазит.
Треть, четвёртое.
У меня уже прога листов на 10 получилась.
На одном работает, треий подключил, всё съехало.


А кто-нибудь с такой задачей сталкивался?

[blackfin]

Сегодня попробовал написать алгоритм по совету.

А что за совет? А то советов, вроде, много было..

[Prinz]

А что за совет? А то советов, вроде, много было..

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

То, что не решается аналитически, можно решить графически: отрисуйте треки в битмап ( достаточно бит на точку, много еста не займет), тогда задача сведется к банальной заливке области. Если начальную точку выбрать гарантированно во внешней области, как раз гарантированно зальется все, что вне.

З.Ы. чтобы не было "протеканий" во внутрь, треки нужно рисовать толстыми линиями. Как раз получится отступ, который Вы рисовали, в половину толщины линии.

Решил задачу аналогично вашему совету.
Сожалею, что поздно прочитал Ваш совет, а то неделю думал, голову ломал.
Работает просто всё шикарно.
Теперь буду выделять внутреннии области.
Если необходимо могу моим последователям выложить код программки на билдере.
Буду аналогично внутреенни зоны вычленять.
Всем большое спасибо за советы.

То, что не решается аналитически, можно решить графически: отрисуйте треки в битмап ( достаточно бит на точку, много еста не займет), тогда задача сведется к банальной заливке области. Если начальную точку выбрать гарантированно во внешней области, как раз гарантированно зальется все, что вне.

З.Ы. чтобы не было "протеканий" во внутрь, треки нужно рисовать толстыми линиями. Как раз получится отступ, который Вы рисовали, в половину толщины линии.

Решил задачу аналогично вашему совету.
Сожалею, что поздно прочитал Ваш совет, а то неделю думал, голову ломал.
Работает просто всё шикарно.
Теперь буду выделять внутреннии области.
Если необходимо могу моим последователям выложить код программки на билдере.
Буду аналогично внутреенни зоны вычленять.
Всем большое спасибо за советы.

Курите теорию R-функций. (Функции Рвачева).

Заинтересовало очень Ваше придложение с математической точки зрения.
Слышал о них, но дела с ними никогда не имел.
А посоветуйте книжечку пожалуйста.
В моих книжках по Вышке такого нет.

Курите теорию R-функций. (Функции Рвачева).

Заинтересовало очень Ваше придложение с математической точки зрения.
Слышал о них, но дела с ними никогда не имел.
А посоветуйте книжечку пожалуйста.
В моих книжках по Вышке такого нет.

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

Я Вам скриншёт сейчас пришлё.
Вот, как у меня это вышло, и как оно должно быть.
Красная линия - это трек. который надо обвести с определённой точностью.
Граница области, которую я строю - чёрная линия.


Это кусочек трека, обведённого моей прожкой.

Было бы интересно и математическим способом решить эту задачу.

Эскизы прикрепленных изображений

 

[Ledmaster]

Вот, как у меня это вышло, и как оно должно быть.
Красная линия - это трек. который надо обвести с определённой точностью.
Граница области, которую я строю - чёрная линия.

Это кусочек трека, обведённого моей прожкой.

Забавно, как раз в левом верхнем углу этого скриншота находится мой офис!