Алгоритм построения не выпуклых полигонов

[Григорий Степанов]

Во время разработки утилит для автоматизации оцифровки топографических карт столкнулся со следующей задачей:

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

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

Вопрос: Как построить гладкий НЕ ВЫПУКЛЫЙ полигон?

[Григорий Степанов]

Извиняюсь, только после написания поста обратил внимание на раздел "Геоконкурс:Пожары". Видимо следует писать не сюда, но буквально заворожила тема "Алгоритмы"...

[gamm]

Во время разработки утилит для автоматизации оцифровки топографических карт столкнулся со следующей задачей:

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

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

Вопрос: Как построить гладкий НЕ ВЫПУКЛЫЙ полигон?

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

навскидку пара идей:

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

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

[gamm]

Извиняюсь, только после написания поста обратил внимание на раздел "Геоконкурс:Пожары". Видимо следует писать не сюда, но буквально заворожила тема "Алгоритмы"...

кстати, и сюда можно писать - идейка вполне годится для генерализаци пикселей, признанных пожарищем, с построением границ пожара

[Григорий Степанов]

Вариант с обработкой результатов триангуляции Делоне похоже вполне жизнеспособен. Спасибо за идею!

[gamm]

Вариант с обработкой результатов триангуляции Делоне похоже вполне жизнеспособен. Спасибо за идею!

обращайтесь

всегда рад помочь старым знакомым.