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

[Prinz]

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



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

[zzzzzzzz]

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

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

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

[Prinz]

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

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

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



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

[zzzzzzzz]

Не надо оскарблять. Я тоже могу.

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

[Prinz]

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

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

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

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

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

 

[VladimirYU]

Я же Вашими способностями умственными не интересуюсь.
Мне нужен совет!

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

[Prinz]

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

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

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

[Палыч]

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

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

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

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

[Prinz]

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

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

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


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

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