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



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

Кривая замкнута, как я понимаю?

Это стеб?

И что значит, определить внешнюю границу? Продемонстрируйте рисунком, чтоли.



Почему Вы так думаете?

Сейчас нарисую.

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

PS. Не заметил, что заданы точки кривой... Навскидку - наметки как разбить алгоритм на два алгоритма: 1) подойти от точки заведомо лежащей вне кривой до упора в кривую 2) обойти вдоль кривой (по часовой стрелке, например), отмечая точки кривой, соприкасающиеся с точкой обхода. К каждому пункту придумать алгоритм - уже легче...

Скорее всего, более общая постановка задачи: определить, находится ли точка внутри (или снаружи) замкнутого контура.
Решения (_стандартной_топологической_задачи_) разбираются, по-моему, во 2-м томе Кнута.
До определения способа задания контура (массив, связанный список,...; метод интерполяции; пересечения областей;...) говорить просто не о чем.

Рисуем касательную в конкретной точке. Дальше половина направлений будет в одну сторону - половина в другую.
Ставим точку сначала с одной стороны, потом с другой. И проверяем, есть ли путь до точки которая находится внутри (или снаружи).

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


Ещё сложность в том, что кривая задана отрезками и точки между отрезками неравномерны!
Тоесть, изменение направление - много точек, движение по прямой - то точек мало!
ТОесть они редки!

Для обведения по кругу просто кривой уже четыре олгаритма придумал!

И метод по касательно может не помочь, так как например в этом напралении модет не быть точек, а линия есть!

Всем спасибо за советы.
Готов ещё выслушать предложения.
А кто может посоветовать какую-нибудь книгу???

Ужасно информативно... Коль привели эти каракули, то, хотя бы цветом что-то выделили, пояснения бы дали... А так - что привели рисунок, что - нет... Потратьте немного времени на полную и грамотную постановку задачи! Тогда и решение быстрее сможите найти, или подскажет, посоветует кто-нибудь что-то дельное.

А кто-нибудь знаком с файлом фомата .plt для OziExplorer?
Вот в этом файле даны точки кривой от начала до конца.
Из него я и считываю.

Перерисовал заного!

Здесь ещё наиболее сностный вариант!

НАчало и конец могут совпадать!
Если надо могу ещё более подробно описать.

На границе не указал точки, но их должно быть мало. Тоесть наиного меньше чем на основной кривой. Но точность тоже должна быть.

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

По трем соседним точкам восстанавливается треугольник. Координаты всех его вершин известны. Определяется его площадь. Если она не равна 0, то точки не лежат на прямой - и можно определить, какие точки сетки попадают в него, а какие - нет. В матрицу точек сетки записываем признак попадания-непопадания.
Берем следующий треугольник, модифицируем матрицу. Остановка процесса по исчерпанию количества точек кривой. Значения признаков в матрице, "окруженные" признаками противоположного значения, инвертируются.

Впрочем, наверное, это сложно для вас. Бросьте это безнадёжное дело.

Не надо оскарблять. Я тоже могу.
Во-вторых это может не пракатить! Три соседнии точки которые вы говорите могут быть в начале и конце массива координат.
В - третьих я говорю. Точки может не быть, а прямая линия там проходить будет и ваш алгоритм просто её не заметит. Уже так нагревался.
Обратите внимание на рисуночек.
Это не просто графика. Это работа с координатами GPS.

Я уже сделал четыре программы на векторном анализе. НЕ знаю на сколько это сложно для вас?
Но при определённых условия анализ не проходит.



И ваш метод при большом треке, например Москва - Владивосток, просто не прокатит.
Памяти не хватит!

Это не "оскарбление", а чистая констатация факта - вы не можете даже условия задачи сформулировать нормально. И, судя по аргументации, эту задачу не сможете решить ближайшие несколько лет . Хотя, удачи вам, конечно.

Я же Вашими способностями умственными не интересуюсь.
Мне нужен совет,а не Ваши шуточки.
А решения же четыре есть, за неделю!

И ещё прочитай внимательнее , что я написал.
Там указана вся специфичность задачи.

Речь не идет ни о чьих способностях, ни умственных. ни о каких других. От Вас хотят допытаться нормальной формулировки Вашей задачи.

Спросите меня пожалуйста, что конкретно Вам не понятно, я постараюсь это место подробнеее описать.

Дан файл .plt.
Из наго я считываю координаты по порядку движения по кривой.
При движении по прямой, точки идут очен редко и это очень плохо.
Из-за этого случаются сбои.
При изменении направления точки идут часто и тут всё хорошо!
Мне интереснее, как отфильтровать внутрении точки кривой.
Что мне ещё указать во втором приведённом рисунке?

Попробую протелепатить... Вот (возможно, неверная и неполная) постановка задачи и примерное решение.

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

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

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

Спасибо большое.
Ваш алгоритм мне кажется из приведённых наиболее приевлимым.
Я делал так.
Я сам строил вектор под определённым углом, и определял его персечение с отрезками, но оказалось, что для этого софта нужен был супер компутер!
10 ядерный минимум.
Следующую версию программы я буду опираться на Ваш совет.

Большое спасибо.
Кто ещё что посоветует?


А кто посоветует книжечку???
Даже с графикой связанную, с примерно такой же задачей.

Я постановку задачи написал для затравки, чтобы Вы поправили и дополнили её. Неужели, попадание = 100% ? Ну а решение было приведено мной выше, я его, фактически, повторил

PS. Кстати, постановка задачи в моей редакции с приведенными рисунками как-то плохо коррелирует...

С треками все понятно, но Вы на всех рисунках обводите область трека с некоторым запасом, это что?

Надо треку внутри находиться это области.
Но тут не сложно, если границу внешнюю знаем, то к ней просто добавить - это не сложно.



А что именно плохо коррелирует??? Поясните. Что Вам не нравится.
Мне кажется с последними моими рисунками очень даже коррелирует.

А какие у Вас есть ещё предложения? Посоветуйте пожалуйста.
А не знаете какие-нибудь книжки???

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

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

Ну, например: 1) Я считал что граница - часть самой ломанной. Вы её рисуете на некотором (иногда, давольно значительном) расстоянии от ломаной. 2) В моей редакции задачи - если ломанная состоит из одного отрезка, то внутренних областей нет (и соответственно границы). В Вашем рисунке - есть.
Что же такое Ваш термин "граница" - мне так до сих пор и непонятно.

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

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

Это интересно. Вы собрались решать задачу аналитическими уравнениями? Точно не численным матрично-сеточным способом? Тогда приготовьтесь решать систему уравнений, количество которых будет равно количеству точек кривой. Причем, если там отрезки, то уравнения с кучей модулей будут. Хех... И конечное уравнение будет длиной Москва-Владивосток.

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


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

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


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


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

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

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

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

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

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

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


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

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

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

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

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

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

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




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




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



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



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



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


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

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

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

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

Для тех, кто слаб в математике… Пусть на плоскости тремя точками заданы два отрезка АВ и ВС. Точка А не совпадает с точкой В; точка В не совпадает с точкой С. Точки заданы координатами x и y: точка А, например, имеет координаты xa и ya. Определить угол fi образованный отрезком ВС и продолжением отрезка АВ (см. рисунок).
Нажмите для просмотра прикрепленного файла
Для определения угла fi в диапазоне от минус pi до плюс pi необходимо получить синус и косинус угла.
Косинус угла можно получить, если вспомнить скалярное произведение векторов
AB * BC * Cos fi = ABx * BCx + ABy * BCy
где AB и ВС – длина соответствующего вектора (отрезка); т.е. AB = Sqrt ( (xb-xa)^2 + (yb-ya)^2)
ABx и BCx– проекции вектора (отрезка) на ось Х; т.е. ABx = xb – xa
ABy и BСy – проекции вектора (отрезка) на ось Y

Синус угла получаем из произведения векторов
AB * BC * Sin fi = ABx * BCy - ABy * BCx
Обозначения – см. выше.

По найденным синусу и косинусу определяем угол. Обычно, в языках высокого уровня для этого используют функцию atan2(Sin fi,Cos fi).

Задачу решил подностью.
Всё с помощью тогоже битмапа.
Теперь есть и внутреении и наружнеи зоны.
И даже фильтрация излишних точек.
Получилось следующее:



А мой тоже рядышком.




Спасибо за консультацию. С этими азами знаком. Но всё равно спасибо.





На счёт задачи формулировки задачи я с Вами полностью согласен.
У меня не очень просто большой опыт спрашивания.
Спасибо за советы.
Буду пробовать.
Идея конечно ясна.
Ещё раз спасибо!

Опять "тень на плетень" навели, - область внутри петли у вас не выбрана оказалась. Незачет.
"Битмап", как вы изволили выразится, это матрично-сеточное решение.
Хотя, жить вам...

Где что не выбрано???
На последнем моём прикрёплённом файлике внутреннии зоны рисуются.
И впринципе в моём алгоритме можно задать сначала, какой должна быть площадь внутренних зон, чтобы её выбирать.
Получилось просто всё очень удобно.
Ещё подключил алгоритмик, чтобы убрать лишнюю избыточность точек.
На некоторых кривых по 1000 точек достаточно всего 100 моих.

Ещё раз всем большое спасибо за советы.

Могу подробно описать, как делал.