Топология у Покрытия

[XdenisX]

Добрый день.
Мой вопрос может показаться странным, но так , или иначе, его придется задать.
У меня существует проблема с растрово-векторным преобразованием. Программу я пишу на С++,
вернее, сказать , уже дописал, но возникла неприятность, после преобразования, контура полученных объектов имеют зубчатую форму. Мое начальство сказало, что все хорошо и Шейп-файл правильный, но хорошо бы иметь более сглаженную форму у контуров. После сглаживания, естественно, возникают неопределенности(Пересечения или дыры.)
Для того , чтобы, этого не происходило, мне необходимо использовать другую структуру хранения данных, типа Покрытия ESRI.
Извините за затянушуюся преамбулу.

Может быть, кто нибудь сталкивался уже с подобной проблемой? Т.е, как эту злосчастную топологическую структуру (покрытие) построить.
Заранее благодарен за любые советы.
С уважением, JAS

[Boris]

так вам надо узнать как покрытие построить или как построить покрытие с возможностью его последующего редактирования?

[gamm]

Т.е, как эту злосчастную топологическую структуру (покрытие) построить.

строить вам, к счастью, ничего не нужно, поскольку топология уже индуцирована растром, ее нужно только сохранить.

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

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

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

[XdenisX]

Спасибо Вам за ответ. Думал, что вряд ли, кто-то откликнется.
Теперь я могу более подробно описать то,что у меня сейчас имеется.
1. общий массив координат точек с признаками узел/ не узел.
2. Массив сформированных полигонов , кольца полигонов представляют из себя списки указателей на дуги.
3. Массив дуг , дуги представлены как списки указателей на точки, при этом каждая дуга имеет начальный и конечный узлы.

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

Я понимаю, что возникновение пересечений и дырок возникает из-за того, что сглаживание осуществляется независимо для каждого полигона. При этом общая граница смежных полигонов проходится дважды, а направление общей дуги (ребра) у смежных полигонов противоположное (180 градусов).
Правильно ли, я, Вас понял, что мне необходимо добавить для каждого объекта(дуги) дополнительные свойства : полигон слева и полигон справа, может быть для ребра в полигоне задать дополнительное свойство Inverse(True/False), означающее, что координаты точек ребра необходимо считывать в определенном(StartNode->EndNode, либо, EndNode->StartNode) направлении? .
К сожалению, у меня сейчас отсутствует объект суперполигон .
С уважением, JAS

[gamm]

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

Непонятно, что у вас за дуги, поскольку полигоны автоматически получаются при сборке. Сначала есть только дуги - проходите дугу, и делаете маску (ребер), куда ставите отметки, чтобы не проходить дуги 2 раза; дугу ведете пока точки (пересечения лини сетки) соединяют пиксели одного цвета. Все дуги записываете куда-то, и потом (когда все дуги готовы) находите инцидентные узлы (например, просто отсортировав по координатам начал/концов) - это дает вторую структуру (узлов, и списки дуг в них; дуги сортируете против часовой). Потом обходите дуги, как я сказал - получаете полигоны. Осталось найти, кто в кого вложен, для этого достаточно иметь poin_in_poly() и охватывающие прямоугольники полигонов, чтобы быстро отсекать не пересекающиеся пары - получите частичный порядок, из которого построите топологию объектов. И сглаживать надо именно дуги, и поскольку они в одном экземпляре, то никаких дырок не будет (если не переборщить).

В общем, возни много - используйте GRASS

[XdenisX]

Спасибо за ответ. Одно уточнение , у меня не изображение, а данные модельных расчетов в узлах регулярной сетки, а в прочем, сути это не меняет. В настоящее время топология полигонов построена. Более того, если Вам будет это интересно, перед тем как использовать функцию PointInPoly(), я предварительно проверяю, что Центроиды полигонов действительно находятся внутри полигонов, т.к бывают случаи, когда центроид(центр масс) находится вне полигона, тогда его приходится принудительно перемещать внутрь полигона и только после этого формировать сложные полигоны с островами(Принцип - Вассал моего вассала, не мой вассал). Как , Вы и предлагали, я, вначале экстентом отсекаю все полигоны , которые явно не имеют общих границ, а , затем с использованием PointInPoly() определяю вложенность полигонов.
Это выполнено. Каждый полигон имеет еще и свои атрибутивные характеристики . Вы правы, сглаживать надо именно дуги. У меня осталась одна задача - выполнить сглаживание. Извините, что, я Вас напрягаю, но среди коллег по работе посоветоваться не с кем. C GRASS заморачиваться не хочется, т.к, задача практически выполнена. Осталась одна проблема - сгладить дуги и практически все. Я, думаю, что , для этой задачи, даже не придется для дуги вводить дополнительные свойства(левый полигон / правый полигон - необходимы для Булевой алгебры ), а вот для полигона, видимо, ориентацию дуги вводить придется. Общий массив структур типа "Дуга" у меня существует, осталось правильно установить флаг ориентации для каждой дуги конкретного полигона и после этого запускать процедуру сглаживания.
Спасибо за помощь. Слава Богу, я, понял, что иду в правильном направлении. Осталось немного - начать и кончить.
С наступающим Вас Новым годом, желаю удачи,
JAS
PS
Начальство на крутые GIS тратить деньги не любит, поэтому, приходится "репу морщить"

[KolesovDmitry]

C GRASS заморачиваться не хочется, т.к, задача практически выполнена. Осталась одна проблема - сгладить дуги и практически все.

Ох, зря... Здается мне вы сэкономите много времени, если все-таки решите вашу задачу через GRASS. Делается это двумя командами.

Пусть, к примеру, нужно векторизовать растр admin, представленный на рисунке step1.

Команда

Код: Выделить всё

r.to.vect in=admin out=tmp_admin feature=area

произведет преобразование растра в вектрор, результат представлен на рисунке step2.

Команда

Код: Выделить всё

 v.clean in=tmp_admin out=tmp_admin1 tool=prune thresh=200 --o

производит очистку вектора с сохранением топологии в соответсвии с заданным порогом (здесь 200). Результат представлен на рисунке step3.

[XdenisX]

Пожалуй, Вы правы. Только мне не приходилось использовать GRASS.
Единственно знаю, что это открытый GIS, я больше пользовался продуктами ESRI(ArcInfo и ArcView).
К сожалению, в настоящее время у нас лицензия ArcGis без Модуля GRID, поэтому мне и пришлось писать программу
на C++. Результат работы своего алгоритма привожу во вложении( полученный шейп визуализировал в ArcMap). А GRASS , видно, мощная вещь. Еще один вопрос - а GRASS имеет встроенный язык разработки?
С уважением, JAS

[Voltron]

А GRASS , видно, мощная вещь. Еще один вопрос - а GRASS имеет встроенный язык разработки?
С уважением, JAS

Очень мощная. Насчет языка разработки — можно писать скрипты на Python. Вводная статья

[gamm]

Очень мощная. Насчет языка разработки — можно писать скрипты на Python

все еще веселее - исходники открыты, можете встраивать собственные куски на С++, нужно только привыкнуть к методам обращения к данным, они достаточно "заковыристые".

кстати по поводу вашей задачи. Я так понимаю, что это изолинии, кто мешает локально интерполировать внутри сетки (хоть квадратичной формой или билинейкой, хоть сплайном - посмотрите MBA), и строить линии по интерполяции? будет вам глаже некуда, топология не порушится, и совпадет со старой линией в пересечениях с узлами сетки. Достаточно будет даже билинейнки, посмотрите в любой программе, как изолинии строятся.

[KolesovDmitry]

А GRASS , видно, мощная вещь. Еще один вопрос - а GRASS имеет встроенный язык разработки?
С уважением, JAS

Очень мощная. Насчет языка разработки — можно писать скрипты на Python. Вводная статья

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

А сама GRASS написана на C.

[XdenisX]

Прошу прощения , а что означает MBA?

[XdenisX]

А задача сводилась к следующему : построить замкнутые контура однородных зон по данным представленным в регулярной сетке и результат представить в виде шейпа. Причем контуры зон должны быть слаженными(исключительно для придания красоты). Если у GRASS есть такие возможности, придется изучать GRASS, а может быть существует возможность дергать функции библиотеки GRASS из среди VisualStudiо?

[Александр Мурый]

В GRASS есть ещё отдельный модуль для генерализации -- v.generalize. Там реализовано, кроме прочего, 6 алгоритмов сглаживания векторов. Вот пример сглаживания полигонов методом "snakes". Только вот с топологией сложно, т.к. в отличие от <v.clean> этот модуль делает с ней что хочет.

И ещё: у модуля r.to.vect есть полезный флаг "-s" для (небольшого) сглаживания полигонов при векторизации.

[XdenisX]

Для amuriy,
Спасибо, приведенный вами пример, по сути и является тем, что мне нужно. Тем более, для полигонов указаны центроиды, придется все таки начать плотно изучать GRASS.