Всем доброго времени суток!

Столкнулся с необходимостью получить контур облака точек. 

Сначала обратился в сторону выпуклых оболочек. Информации по ним много, но лично я использовал вот этот вариант http://e-maxx.ru/algo/convex_hull_graham. В общем то вопросов по этому варианту нет никаких, но я понял, что он мне не подходит.

Дело в том, что мне необходимо зафиксировать "неровности" контура, а выпуклая оболочка как раз их и скрывает.

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


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

Добавь ограничение по длине. Если точка дальше порога, то она не участвует в сортировке.

Да, сначала строишь выпуклую оболочку, затем проверяешь длину ребер, берешь самое длинное (если оно больше порога), начинаешь заворачивать его вовнутрь пока не нарвешься на точку. И т.д.
Еще один способ - построить триангуляцию, удалить внешние треугольники со слишком длинным ребром, затем построить внешний контур.

Если точек не смертелъно много, можно (ИМХО):
Соединит' всe точки со всеми.
Убрат' соединения длиннее, чем заданное ограничение по длине. 
Получится требуемая форма, но у неe могут быт' неприятности вроде таких

После исключения серой линии, появляются 2 варианта решения - красные линии (внутренние соединения не показаны).
Надо ввести критерий выбора из такого рода вариантов. Например, наимен'шая площад' "впуклости" или наименшая суммарная длина или еще что.

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

Я пытаюсь сделать ограничение по длине ребра, как предлагалось выше, но никак не могу понять в какую часть кода эту проверку внедрять - как ни пытался не получается ничего.

[Б]Дементор[/Б], тогда тоже можно соединят' каждую точку с каждой, но, при этом в массив добавлят' тол'ко те, которые мен'ше выбранного ограничения длины. Если точки не очен' плотно расположены, то их бол'шое число не будет критично.

Можно еще так- некий оптимизированный вариант алгоритма:
Нарисоват' описывающий контур.
Убрат' слишком длинные соединения.
Соединит' не все-со-всеми, а тол'ко точки контура, у которых были убраны слишком длинные соединения, со всеми, лежащими в пределах ограничения.
Если замкнутого контура не найдено - растит' деревя от следующих точек, пока нe получится замкнутый контур.
Получится то, о чем а писал выше, но ненужных внутренних соединений будет гораздо мен'ше.

Понятно я написал или мысли выражены путано-туманно?  

http://en.wikipedia.org/wiki/Ramer%E2%80%9...ucker_algorithm

можно построить контур минимальный по площади вокруг облака точек, а потом по алгоритму упростить(если надо)

mrgloom, что-то я не понял. Ramer–Douglas–Peucker algorithm умен'шает испол'зуемое количество точек, а задача, наоборот, добавит'.  Может стоит обяснит' идею для недогадливых?  

Это сообщение отредактировал(а) _Y_ - 31.7.2013, 15:09

Я если не ошибаюсь, но алгоритм Дугласа-Пекера используется для сглаживания... хотя могу и ошибаться, но его применение я встречал только для сглаживания контуров.

сначала строим максимально приближенный к форме контур который прилегает в "облипку" и имеет много точек, а потом его и начинаем упрощать, можно еще потребовать, чтобы оболочка была выпуклой. 


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

Это сообщение отредактировал(а) mrgloom - 31.7.2013, 15:30

Фактически мне и надо построить именно такой контур, чтобы он облеплял облако точек. А упрощать его как раз и можно будет алгоритмом Дугласа-Пекера.

Dementor, eсли вернут'ся к моему рисунку. Каков будет критерий выбора из двух внутренних точек, если любая из них удовлетворяет условию о непревышении длины соединений?

На самом деле для моей задачи без разницы.
Могу пояснить саму суть: предположим есть два облака точек, которые покрывают одну и ту же область. Надо выбрать лишь одно облако, которое покрывает заданную область наиболее хорошо, при этом стоит учитывать, что количество точек в облаке не имеет прямого влияния на качество покрытия, т.к. ясно, что 100 точек из одного облака могут покрыть область лучше 1000 точек из другого. При этом заведомо известно, что форма области, которую покрывают облака стремится либо к прямоугольнику, либо к трапеции. Таким образом, если получившийся контур облака имеет вогнутые внутрь участки, то условие покрытия не выполняется.

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


Это сообщение отредактировал(а) _Y_ - 31.7.2013, 19:25

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

Таким образом я получаю для "рваных" облаков большое количество точек внутри области, при этом для хороших облаков этих точек их очень мало (в основном это начальная точка, конечная точка и немного точек рядом с ними).
Этот вариант далеко не то, к чему я стремился - я то хотел анализировать не количество каких-то там точек, а контура всего облака. Но вариант пока показывает себя рабочим... но я пока не так много случаев проверил, поэтому статистику даже для себя представить не могу.

Но над вашим вариантом решения я буду еще думать - посмотрю что получится.