[VladimirYU 0]

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

Мне нужен совет!

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

[Zigrund 0]

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

 

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

 

Дан файл .plt.

Из наго я считываю координаты по порядку движения по кривой.

При движении по прямой, точки идут очен редко и это очень плохо.

Из-за этого случаются сбои.

При изменении направления точки идут часто и тут всё хорошо!

Мне интереснее, как отфильтровать внутрении точки кривой.

Что мне ещё указать во втором приведённом рисунке?

[Палыч 10]

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

 

Дано:

1. На плоскости отрезками прямой задана ломаная линия.

2. Начало каждого следующего отрезка совпадает с концом предыдущего

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

4. Отрезки, составляющие ломаную линию, могут пересекать друг друга

5. Ломаная линия, возможно, делит плоскость на несколько областей; области ограниченные ломаной кривой - внутренние, не ограниченная - внешняя (она одна)

 

Найти:

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

 

Решение:

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

2 Находим все замкнутые участки ломаной (это будут границы внутренних областей)

3. Попарно проверяются внутренние области, ограниченные этими замкнутыми участками ломаной на предмет вхождения одной области в другую; если область входит в другую, то ломаная - граница области исключается (удаляется)

4 Оставшиеся ломаные – решение

 

[Zigrund 0]

Решение:

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

2 Находим все замкнутые участки ломаной (это будут границы внутренних областей)

3. Попарно проверяются внутренние области, ограниченные этими замкнутыми участками ломаной на предмет вхождения одной области в другую; если область входит в другую, то ломаная - граница области исключается (удаляется)

4 Оставшиеся ломаные – решение

 

Спасибо большое.

Ваш алгоритм мне кажется из приведённых наиболее приевлимым.

Я делал так.

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

10 ядерный минимум.

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

 

Большое спасибо.

Кто ещё что посоветует?

 

 

А кто посоветует книжечку???

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

[Палыч 10]

Спасибо большое.

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

 

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

[Ledmaster 0]

Там указана вся специфичность задачи.

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

[Zigrund 0]

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

 

Надо треку внутри находиться это области.

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

 

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

 

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

Мне кажется с последними моими рисунками очень даже коррелирует.

 

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

А не знаете какие-нибудь книжки???

[Artem_Petrik 0]

По моему, то, что у вас точки соединены линиями всех только запутывает.

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

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

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

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

Решение довольно громоздкое, и если результат работы алгоритма будет давать удовлетворяющие вас результаты, то можно будет думать, как его упростить.

 

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

[Палыч 10]

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

Мне кажется с последними моими рисунками очень даже коррелирует.

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

Что же такое Ваш термин "граница" - мне так до сих пор и непонятно.

 

На мой взгляд задачу следовало бы сформулировать так...

Мы, конечно, можем придумывать формулировки задачи, но достоверно её знает только автор вопроса, который до сих пор не удосужился её сформулировать. У меня закрались мысли, что автор решает какую-то задачу (возможно, довольно простую), сложным путём, и один из шагов её решения - задача, которую мы "решаем" но не имеем её формумировки.

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

[Goodefine 0]

...При движении по прямой, точки идут очен редко и это очень плохо.

Из-за этого случаются сбои...

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

[zzzzzzzz 0]

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

Памяти не хватит!

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

[Zigrund 0]

По моему, то, что у вас точки соединены линиями всех только запутывает.

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

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

Нет, точки поступают последовательно.

Например:

- начало движения - это одна точка.

- следующая точка, следующее положения.

- от точки до следующей точки строится трек.

- при движении по прямой точки ставятся редко о получаются такие пересечения, как на рисунке.

- рисуночек схемотичный.

Спасибо за совет.

 

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

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

 

Мне надо как бы очертить зону где находится этот трек.

Для этого я думаю, что надо сначало найти границу.

Вы дали наиболее правильную трактовку задачи.

Но я ещё раз попробую написать:

Есть файл.

В нём координаты точек, по мери их поступления.

Первая точка соединяется со второй и т.д.

И т.д.

Могут возникать пересечения.

Первый рисунок не удачен, но последующии наиболее точно показывает смысл задачи!

 

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

В ряде случаев это делать не надо.

А если дополнять, то дополнять придётся по всему треку!

Конечно это облегчит задачу.

 

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

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

Оставить только внешнии отрезки.

 

Ещё раз попобую задачу объяснить:

- точка

- следующая

- между ними трек

- и т.д.

- таким образом апроксимируется кривая , которая может изгибаться, как хочет, как например на моём первом рисунке.

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

- Впринципе зона может быть точно по границе кривой линии (внешней)!

 

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

[blackfin 23]

Нет, точки поступают последовательно.

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

- Впринципе зона может быть точно по границе кривой линии (внешней)!

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

 

1. Соединяете ваши точки в порядке их следования отрезками, получая таким образом непрерывную кривую.

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

3. Если начало кривой находится внутри границы зоны, в качестве начальной точки можно выбрать любую точку на границе зоны, например точку для которой координата X (или Y) минимальна (или максимальна).

При любом выборе начальной точки направление обхода кривой должно быть "против часовой стрелки".

4. Обход завершается при попадании в точку из которой обход был начат.

Изменено 22 марта, 2009 пользователем blackfin

[Zigrund 0]

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

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

 

Нисего не помогает. :(((((((((((((((((((((((

У меня горе просто!

Есть очень кривыии линии.

Со всяки провальчиками, пычками.

ОТфильтруешь одно, третье вылазит.

Треть, четвёртое.

У меня уже прога листов на 10 получилась.

На одном работает, треий подключил, всё съехало.

 

 

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

[blackfin 23]

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

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