ГЕОЭКОЛОГИЯ. ИНЖЕНЕРНАЯ ГЕОЛОГИЯ. ГИДРОГЕОЛОГИЯ. ГЕОКРИОЛОГИЯ, 2007, № 2, с. 173-179
МЕТОДОЛОГИЯ И МЕТОДИКА ИССЛЕДОВАНИЙ
УДК 528.94.942
ОЧЕРТАНИЯ ТОЧЕЧНЫХ МНОЖЕСТВ. ПРИЛОЖЕНИЯ ДЛЯ ГЕОЭКОЛОГИЧЕСКОГО И ИНЖЕНЕРНО-ГЕОЛОГИЧЕСКОГО КАРТОГРАФИРОВАНИЯ
© 2007 г. О. К. Миронов
Институт геоэкологии им. Е.М. Сергеева РАН Поступила в редакцию 28.09.2005 г. После исправления 06.06.2006 г.
Вводится понятие очертания точечного множества. Рассматриваются приложения нового понятия для задач анализа картографической информации: оценки качества первичной информации, формализации интуитивных представлений о форме, которую образует множество точечных объектов на карте, предварительной обработки информации при составлении карт. Предлагаемые методы могут быть реализованы в геоинформационных технологиях.
ВВЕДЕНИЕ
Понятие очертания точечного множества вводится для формализации часто встречающейся в естественных науках ситуации, когда требуется охарактеризовать конфигурацию некоторого множества точек.
В науках о Земле, в частности в геоэкологии и инженерной геологии, точечные множества возникают как наборы точек на карте или в 3-мерном пространстве.
Изучение конфигураций природных точечных объектов (эпицентры землетрясений, местонахождения природных катастроф, рудопроявления и т.п.) проводится обычно в контексте разведочного анализа данных, т.е. исследователь старается найти закономерности в фактическом материале и сформулировать гипотезы о характере расположения точек и генезисе соответствующих природных процессов. Типичная задача - описать в понятных и объективных терминах конфигурацию точечного множества с целью дальнейшего количественного ее анализа.
Изучение конфигурации антропогенных объектов (населенные пункты, изыскательские скважины, точки геохимического опробования, пункты мониторинга окружающей среды и т.п.), как правило, проводится, чтобы оценить, насколько хорошо имеющийся набор объектов обеспечивает решение некоторой задачи. Типичный пример -определить, достаточно ли исходных данных для проведения исследований с заданной степенью достоверности получаемых результатов.
Для некоторых видов изысканий существуют нормативы, определяющие необходимую плотность исходных данных для получения результатов с заданной долей уверенности в их правильности. Инструкции по составлению карт устанавли-
вают минимальное допустимое количество точек опробования на единицу площади в зависимости от масштаба карты.
Описание геометрической структуры точечного множества обычно проводится на качественном уровне либо в терминах плотности точек. На качественном уровне говорят, например, о "приуроченности" точечных объектов к какому-либо другому объекту, линейных подструктурах и т.п. Для обоснования этих рассуждений обычно ссылаются на "наглядность" картинки, не приводя количественных оценок. При исследовании плотности точек неявно используются гипотезы о (вероятностной) процедуре порождения этих точек, функции распределения точек в пространстве. В терминах плотности точек получаются описания "в среднем", без учета конкретных геометрических структур. В вычислительных процедурах геостатистики для получения оценочной количественной информации требуется наличие определенного числа исходных точек в круге или шаре фиксированного радиуса с центром в заданной точке. Во всех этих случаях неявно предполагается приблизительно равномерное распределение исходных точек в области с определенной изменчивостью изучаемой величины. Конфигурация множества исходных точек в явном виде не учитывается.
На рис. 1 показаны 2 варианта расположения 3 исходных точек в круге с центром в оцениваемой точке. Очевидно, что в случае б оценка, вообще говоря, будет более достоверной, чем в случае а, хотя по плотности точек оба варианта эквивалентны. Вводимое ниже понятие очертания точечного множества позволяет различать эти конфигурации.
Лх 1 *х
"V2
\**3 а \*х3 • Х-----
Рис. 1. К оценке достаточности исходных данных: а, б - см. текст.
Для формализации постановки указанных выше задач, их решения и последующего анализа в настоящей работе определяется понятие очертания множества точек. Новое понятие является обобщением введенного в работе Г. Эдельсбрун-нера [4] понятия "a-shape" точечного множества. С точки зрения автора, русское слово "очертание" наилучшим образом соответствует новому понятию и является более точным в данном контексте переводом слова "shape", чем слово "форма". Предлагается использовать понятие очертания для экспертной оценки исходной информации.
На интуитивном уровне очертание множества точек - это то, что видит наблюдатель, рассматривающий эти точки с некоторого расстояния. В отличие от наиболее популярных в вычислительной геометрии триангуляции Делоне и многоугольников Вороного [3] очертание точечного множества зависит не только от самого этого множества, но и от параметра а, который соответствует этому расстоянию и может изменяться от 0 до бесконечности. При взгляде из бесконечности (а = га) наблюдатель видит только выпуклую оболочку исходного множества, при рассмотрении c очень близкого расстояния (а = 0) очертание рассыпается на не связанные друг с другом точки. Интересные объекты могут получаться при промежуточных значениях параметра а.
На рис. 2 показаны очертания множества точек, случайным образом расположенных внутри контура буквы "А", при различных значениях параметра а.
ТЕОРИЯ
Очертание определяется для множества точек в п-мерном пространстве. Далее будет рассматриваться плоский случай (п = 2).
Триангуляцией множества точек М называется набор треугольников такой, что
1) вершины любого треугольника принадлежат множеству М;
2) каждая точка множества М является вершиной хотя бы одного треугольника;
3) любые два различных треугольника либо не имеют общих точек, либо имеют общую вершину, либо имеют целую общую сторону;
4) объединение всех треугольников совпадает с выпуклой оболочкой множества М.
Триангуляция Делоне является в некотором смысле "самой правильной" и выделяется "условием Делоне": для любого треугольника триангуляции описанная вокруг него окружность не содержит внутри себя точек множества М [3].
Технологические средства для построения триангуляции Делоне входят в большинство геоинформационных пакетов программ.
Для 3-мерного пространства определение триангуляции Делоне аналогично с заменой треугольников на тетраэдры, а окружности - на сферу.
В п-мерном случае используются п-мерные симплексы и сферы.
Треугольники, входящие в состав триангуляции, и отрезки, являющиеся их сторонами, называются симплексами триангуляции. В 3-мерном случае симплексами называются тетраэдры триангуляции, их грани и ребра.
Триангуляция должна иметь разумное обоснование с точки зрения исследователя. Иногда целесообразно использовать триангуляции Делоне с ограничениями [3]. Ограничения задаются в виде
Рис. 2. Очертание буквы "А". ГЕОЭКОЛОГИЯ. ИНЖЕНЕРНАЯ ГЕОЛОГИЯ. ГИДРОГЕОЛОГИЯ. ГЕОКРИОЛОГИЯ < 2 2007
набора отрезков, которые обязательно должны включаться в триангуляцию. Для треугольников, стороны которых не содержат ограничений, условие Делоне должно выполняться. Ограничения обычно определяются какой-либо природной сущностью, например задают изображение геологического разлома или водораздела. Если дополнительные соображения отсутствуют, то следует использовать триангуляцию Делоне.
Для определения очертания множества точек М возьмем некоторую его триангуляцию. Назовем функцию F, определенную на множестве S симплексов этой триангуляции "формообразующей", если она удовлетворяет следующему условию: если симплекс ^ содержится в границе симплекса ^ то F(s) < F(t).
Примеры формообразующих функций.
1. Геометрическая функция [4]: F1(s) - радиус описанной вокруг симплекса s окружности (если s - отрезок длины 2г, то F1(s) = г).
2. Изменчивость числовых данных. Допустим, что для каждой точки V из М задана числовая характеристика g(v). Положим
F2(s) = тах^(у)| V - вершина s) -
- тт^(у)| V - вершина s).
3. Изменчивость порядковых данных. Допустим, что для каждой точки V из М задана порядковая (ранговая) характеристика h(v) - ранг согласно некоторому упорядочению. Положим
F3(s) = тах(Щ»^ - вершина s) -
- тт(ШУ)^ - вершина s).
4. Изменчивость качественных данных. Допустим, что точки из М разбиты на непересекающиеся классы. Положим
F4(s) = 0, если все вершины s принадлежат к одному классу;
F4(s) = 1, если среди вершин s есть принадлежащие к разным классам.
5. Комбинация функций. F5 - сумма возрастающих функций от определенных выше функций вида F1, F2, F3, F4 (например, их линейная комбинация с положительными коэффициентами). Возможно использование нескольких функций вида F2, F3, F4, определенных для разных показателей опробований в точках. Применение нелинейных возрастающих функций от исходных функций позволяет ввести нелинейные штрафы за наблюдаемые расхождения в исходных данных.
Нетрудно видеть, что варианты 2-4 определения формообразующей функции строятся по следующему алгоритму.
Пусть F(s) - некоторая функция, определенная на одномерных симплексах (отрезках) триангуляции. Распространим ее на все симплексы t по формуле:
F(t) = тах^^)^ - ребро 0 - тт^^)^ - ребро 0.
Например, для функции F2 можно положить F(s) = ^(а) - g(b)|, где а, Ь - концы отрезка s.
Было бы интересно найти другие примеры формообразующих функций, не сводящиеся к этому способу.
Для заданной формообразующей функции F и параметра а назовем Fa-очертанием множества М объединение множества М и симплексов s, для которых F(s) < а. По определению "формообразующей" функции треугольники, входящие в очертание, будут замкнуты: если треугольник входит в очертание, то его стороны - тоже.
В приложениях вид функции F и величину параметра а для определения очертания задает эксперт в соответствии с требованиями решаемой задачи: допустимыми расстояниями между исходными точками и изменчивостью исходных данных.
Очертание множества М при фиксированном значении параметра состоит из объектов 3 размерностей, которые содержательно интерпретируются следующим образом.
1. Изолированные точки
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.