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



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

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

Это стеб?

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



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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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