admin / 12.04.2018

Triangulation Point Two — Quest — Wotlk Database Viewer (ADV)

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


Рис. 12. Триангуляция Делоне

 

      Говорят, что пара соседних треугольников триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этих двух треугольников.
      Говорят, что треугольник удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этого треугольника и трёх его соседей (если они существуют).
      Триангуляция Делоне определяется как граф, двойственный диаграмме Вороного — одной из базовых структур вычислительной геометрии.
      Для заданной точки Рi Î {P1, … Рn } на плоскости многоугольником ячейкой) Вороного называется геометрическое место точек на плоскости, которые находятся к Рi ближе, чем к любой другой задан­ной точке Pi, ji.
      Совокупность многоугольников Вороного образует разбиение плоскости, представляющее векторную сеть.
      Диаграммой Вороного заданного множества точек {Р1, … Pn) на­зывается совокупность всех многоугольников Вороного этих точек (рис. 13, а).
      Диаграммы Вороного также иногда называют разбиением Тиссена и ячейками Дирихле.
      Одним из главных свойств диаграммы Вороного является её двойственность триангуляции Делоне (рис. 14). А именно, соеди­нив отрезками тс исходные точки, чьи многоугольники Вороного соприкасаются хотя бы углами, мы получим триангуляцию Делоне (рис. 13, б).

 


Рис. 13. Диаграммы Вороного: а – пример диаграммы; б – двойственная диаграмме триангуляция Делоне


Рис. 14. Граф, двойственный диаграмме Вороного


Рис. 15. Перестроение треугольников, не удовлетворяющих условию Делоне

      Многие алгоритмы построения триангуляции Делоне исполь­зуют следующую теорему: триангуляцию Делоне можно получить из любой другой триангуляции по той же системе точек, последова­тельно перестраивая нары соседних треугольников ΔАВС и ΔBCD, не удовлетворяющих условию Делоне, в пары треугольников ΔABD и ΔACD (рис. 15). Такая операция перестроения также часто называ­ется флипом.
      Исходя из данной теоремы, как вы считаете, можно ли построить триангуляцию Делоне по некоторой триангуляции путем последова­тельного улучшения её до выполнения условия Делоне?
      При проверке условия Делоне для пары соседних треугольников можно использовать непосредственно определение условия Делоне, а также другие способы, основанные на следующих теоремах.
      — триангуляция Делоне обладает максимальной суммой мини­мальных углов всех своих треугольников среди всех возможных три­ангуляции;
    — триангуляция Делоне обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возмож­ных триангуляции.
      В данных теоремах фигурирует некая суммарная характеристика всей триангуляции (сумма минимальных углов или сумма радиусов), оптимизируя которую в нарах смежных треугольников, можно полу­чить триангуляцию Делоне.
      На практике обычно используют несколько способов проверки ус­ловия Делоне для заданной пары треугольников:

  1. Проверка через уравнение описанной окружности.
  2. Проверка с заранее вычисленной описанной окружностью.
  3. Проверка суммы противолежащих углов.

      Рассмотрим подробнее каждый из них.
      1. Проверка через уравнение описанной окружности. Уравнение окружности, проходящей через точки (х11), (х22), (х33) можно записать в виде:

     Как вы считаете, можно ли заменить данную формулу следующей: (x2+y2) · a – x · b + y · c –d = 0, где

     Тогда условие Делоне для любого заданного треугольника Δ((х11), (х22), (х33)) будет выполняться тогда и только тогда, когда для любого узла (х00) триангуляции верно ((x02+y02) × ax0 × b + y0× cd) × sgn a≥ 0, т.е. когда (х00) не попадает внутрь окружности, описанной вокруг треугольника Δ((х11), (х22), (х33)).

     Для упрощения вычислений можно заметить, что если тройка точек (х11), (х22), (х33) является правой (т.е. обход их в треугольнике выполняется по часовой стрелке), то всегда sgn a = –1, и наоборот, если тройка эта левая, то sgn а = 1.
     2. Проверка с заранее вычисленной описанной окружностью.
     Вычисляем для каждого построенного треугольника центр и радиус описанной вокруг него окружности, после чего проверка условия Делоне будет сводиться к вычислению расстояния до центра этой окружности и сравнению результата с радиусом. Таким образом, центр (х00) и радиус г окружности, описанной вокруг треугольника Δ((х11), (х22), (х33)), можно найти как:

где a, b, с, dопределены выше в (*).
     Тогда условие Делоне для треугольника Δ((х11), (х22), (х33)) будет выполняться только тогда, когда для любой другой точки (х00) триангуляции выполняется соотношение (х0 – хc)2 + (у0 – уc)2?r2. Как вы считаете, какой знак должен связывать части данного соотношения?
      3. Проверка суммы противолежащих углов.
       Доказано, что условие Делоне для данного треугольника Δ((х11), (х22), (х33)) будет выполняться только тогда, когда для любой другой точки (х00) триангуляции α + β ≤ π (рис. 16).

 

Триангуляция для конечного набора точек S является задачей триангуляции выпуклой оболочки CH(S), охватывающей все точки набора S. Отрезки прямых линий при триангуляции не могут пересекаться — они могут только встречаться в общих точках, принадлежащих набору S. Поскольку отрезки прямых линий замыкают треугольники, мы будем считать их ребрами. На рис. 1 показаны два различных варианта триангуляции для одного и того же набора точек (временно проигнорируем окружности, проведенные на этих рисунках).

Рис. 1: Два различных варианта триангуляции мя одного набора точек

Для данного набора точек S мы можем видеть, что все точки из набора S могут быть подразделены на граничные точки — те точки, которые лежат на границе выпуклой оболочки CH(S), и внутренние точки — лежащие внутри выпуклой оболочки CH(S). Также можно классифицировать и ребра, полученные в результате триангуляции S, как ребра оболочки и внутренние ребра. К ребрам оболочки относятся ребра, расположенные вдоль границы выпуклой оболочки CH(S), а к внутренним ребрам — все остальные ребра, образующие сеть треугольников внутри выпуклой оболочки. Отметим, что каждое ребро оболочки соединяет две соседние граничные точки, тогда как внутренние ребра могут соединять две точки любого типа. В частности, если внутреннее ребро соединяет две граничные точки, то оно является хордой выпуклой оболочки CH(S). Заметим также, что каждое ребро триангуляции является границей двух областей: каждое внутреннее ребро находится между двумя треугольниками, а каждое ребро оболочки — между треугольником и бесконечной плоскостью.

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

Теорема о триангуляции набора точек. Предположим, что набор точек S содержит n>3 точек и не все из них коллинеарны. Кроме того, i точек из них являются внутренними (т. е. лежащими внутри выпуклой оболочки CH(S). Тогда при любом способе триангуляции набора S будет получено точно n + i — 2 треугольников.

Для доказательства теоремы рассмотрим сначала триангуляцию n-i граничных точек. Поскольку все они являются вершинами выпуклого полигона, то при такой триангуляции будет получено (n — i) — 2 треугольников. (В этом нетрудно удостовериться и, более того, можно показать, что любая триангуляция произвольного m-стороннего полигона — выпуклого или невыпуклого — содержит m — 2 треугольника). Теперь проверим, что будет происходить с триангуляцией при добавлении оставшихся i внутренних точек, каждый раз по одной. Мы утверждаем, что добавление каждой такой точки приводит к увеличению числа треугольников на два. При добавлении внутренней точки могут возникнуть две ситуации, показанные на рис. 2. Во-первых, точка может оказаться внутри некоторого треугольника и тогда такой треугольник заменяется тремя новыми треугольниками. Во-вторых, если точка совпадает с одним из ребер триангуляции, то каждый из двух треугольников, примыкающих к этому ребру, заменяется двумя новыми треугольниками. Из этого следует, что после добавления всех г точек, общее число треугольников составит (n — i — 2) + (2i), или просто n + i — 2.

Рис. 2: Две ситуации, возникающие при триангуляции после добавления новой внутренней точки

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

Рис. 3: Триангуляция Делоне для 250 точек, выбранных случайным образом в пределах прямоугольника. Всего образовано 484 треугольника

Для формирования триангуляции Делоне нам потребуется несколько новых определений. Набор точек считается круговым, если существует некоторая окружность, на которой лежат все точки набора. Такая окружность будет описанной для данного набора точек. Описанная окружность для треугольника проходит через все три ее (не коллинеарные) вершины. Говорят, что окружность будет свободной от точек в отношении к заданному набору гочек S, если внутри окружности нет ни одной точки из набора S. Но, однако, точки из набора S могут располагаться на самой свободной от точек окружности.

Триангуляция набора точек S будет триангуляцией Делоне, если описанная окружность для каждого треугольника будет свободна от точек. На схеме триангуляции рис. 1а показаны две окружности, которые явно не содержат внутри себя других точек (можно провести окружности и для других треугольников, чтобы убедиться, что они также свободны от точек набора). Это правило не соблюдается на схеме рис. 16 — внутрь проведеной окружности попала одна точка другого треугольника, следовательно, эта гриангуляция не относится к типу Делоне.

Можно сделать два предположения относительно точек в наборе S, чтобы упростить алгоритм триангуляции. Во-первых, чтобы вообще существовала триангуляция, мы должны полагать, что набор S содержит по крайней мере три точки и они не коллинеарны. Во-вторых, для уникальности триангуляции Делоне необходимо, чтобы никакие четыре точки из набора S не лежали на одной описанной окружности. Легко видеть, что без такого предположения гриангуляция Делоне не будет уникальной, ибо 4 точки на одной описанной окружности позволяют реализовать две различные триангуляции Делоне.

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

Определение границы зависит от следующей схемы классификации ребер триангуляции Делоне относительно текущей триангуляции. Каждое ребро может быть спящим, живым или мертвым:

  • спящие ребра: ребро триангуляции Делоне является спящим, если она еще не было обнаружено алгоритмом;
  • живые ребра: ребро живое, если оно обнаружено, но известна только одна примыкающая к нему область;
  • мертвые ребра: ребро считается мертвым, если оно обнаружено и известны обе примыкающие к нему области.

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

На каждой итерации выбирается любое одно из ребер е границы и оно подвергается обработке, заключающейся в поиске неизвестной области, ко торой принадлежит ребро е. Если эта область окажется треугольником f, определяемым концевыми точками ребра е и некоторой третьей вершинов v, то ребро е становится мертвым, поскольку теперь известны обе примыкающие к нему области. Каждое из двух других ребер треугольника t переводятся в следующее состояние: из спящего в живое или из живого в мертвое.

Триангуляция Делоне Определение, применение, свойства, методы построения. — презентация

Здесь вершина v будет называться сопряженной с ребром е. противном случае, если неизвестная область оказывается бесконечной плоскостью, то ребро е просто умирает. В этом случае ребро е не имеет сопряженной вершины.

На рис. 4 показана работа алгоритма, где действие происходит сверху вниз и слава направо. Граница на каждом этапе выделена толстой линией.

Алгоритм реализован в программе delaunayTriangulate. Программе задается массив s из n точек и она возвращает список треугольников, представляющих триангуляцию Делоне. Реализация использует класс кольцевого списка и классы из раздела структуры геометрических данных. В качестве класса Dictionary можно использовать любой словарь, поддерживающий требуемые операции. Например, можно переопределить #define Dictionary RandomizedSearchTree.

List<Polygon*> * (Point s[], int n) { Point p; List<Polygon*> *triangles = new List<Polygon*>; Dictionary<Edge*> frontier(edgeCmp); Edge *e = hullEdge(s, n); frontier.insert(e); while (!frontier.isEmpty()) { e = frontier.removeMin(); if (mate(*e, s, n, p)) { updateFrontier(frontier, p, e->org); updateFrontier(frontier, e->dest, p); triangles->insert(triangle(e->org, e->dest, p)); } delete e; } return triangles; }

Рис. 4: Наращивание триангуляции Делоне. Ребра, входящие в состав границы, выделены толстой линией

Треугольники, образующие триангуляцию, записываются в список triangles. Граница представлена словарем frontier живых ребер. Каждое ребро направлено, так что неизвестная область для него (подлежащая определению) лежит справа от ребра. Функция сравнения edgeCmp используется для просмотра словаря. В ней сравниваются начальные точки двух ребер, если они оказываются равными, то потом сравниваются их концевые точки:

int edgeCmp (Edge *a, Edge *b) { if (a->org < b->org) return 1; if (a->org > b->org) return 1; if (a->dest < b->dest) return -1; if (a->dest > b->dest) return 1; return 0; }

Как же изменяется граница от одного шага к другому и как функция updateFrontier изменяет словарь ребер границы для отражения этих изменений? При подсоединении к границе нового треугольника t изменяются состояния трех ребер треугольника. Ребро треугольника t, примыкающее к границе, из живого становится мертвым. Функция updateFrontier может игнорировать это ребро, поскольку оно уже должно быть удалено из словаря при обращении к функции removeMin. Каждое из двух оставшихся ребер треугольника t изменяют свое состояние из спящего на живое, если они уже ранее не были записаны в словарь, или из живого в мертвое, если ребро уже находится в словаре. На рис. 5 показаны оба случая. В соответствии с рисунком мы обрабатываем живое ребро af и, после обнаружения, что точка b является сопряженной ему, добавляем треугольник afb к текущей триангуляции. Затем ищем ребро fb в словаре и, поскольку его там еще нет и оно обнаружено впервые, его состояние изменяется от спящего к живому. Для редактирования словаря мы повернем ребро fb так, чтобы примыкающая к нему неизвестная область лежала справа от него и запишем это ребро в словарь. Затем отыщем в словаре ребро ba — поскольку оно есть в нем, то оно уже живое (известная примыкающая к нему область — треугольник abc). Так как неизвестная для него область, треугольник afb, только что была обнаружена, это ребро удаляется из словаря.

Функция updateFrontier редактирует словарь frontier, в котором изменяется состояние ребра из точки а в точку b:

Рис.

5: Подключение треугольника afb к живому ребру аt

void updateFrontier (Dictionary<Edge*> &frontier, Point &a, Point &b) { Edge *e = new Edge (a, b); if (frontier.find (e)) frontier.remove(e); else { e->flip(); frontier.insert(e); } }

Функция hullEdge обнаруживает ребро оболочки среди п точек массива s. В этой функции фактически применяется этап инициализации и первой итерации метода заворачивания подарка:

Edge *hullEdge (Point s[], int n) { int m = 0; for (int i = 1; i < n; i++) if (s[i] < s[m]) m = i; swap(s[0], s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s[0], s[m]); if ( (c == LEFT) || (C == BETWEEN) ) m = i; } return new Edge(s[0], s[m] ); }

Функция triangle просто формирует и возвращает полигон для трех точек, передаваемых ей в качестве параметров:

Polygon *triangle (Point &а, Point &b, Point &c) { Polygon *t = new Polygon; t->insert (a); t->insert (b); t->insert (c); return t; }

Наверх

ВАШ ПУТЕВОДИТЕЛЬ В МИРЕWORLD OF WARCRAFT

Триангуляция: точка первая

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

Описание

Есть еще одна причина для изъятия геодезического снаряжения. Это кристалл из дренейской легенды, который очень важен для меня.

Говорят, что кристалл дарует своему носителю сверхъестественную силу!

——Билет 13. Grid-модель рельефа. Алгоритмы построения grid-моделей——

Но существует опасность, что его добудут другие – а именно Пылающий Легион.

<имя>, возьми это снаряжение и используй его, чтобы найти первую точку триангуляции. Мы знаем, что она должна находиться где-то к востоку отсюда поблизости от Манагорна Ультрис.

После этого отметься у моего агента, Дельца Хаззина, на острове Манагорна Ультрис.

Награда

Также, вы получите: 410

Прогресс

Hello, traveler. You come to Hazzin because you are in need of my goods?

Завершение

<Dealer Hazzin lowers his voice to a whisper.>

Ah, I know of your mission.

It is one of great importance to Nexus-Prince Haramad!

Now that we know the location of this first triangulation point, you must move swiftly to find the second!

Дает

По завершению квеста, вы получите:

  • 1250 опыт (75 на максимальном уровне)

Дополнительная информация

Краткая информация
Цепочка
Открывает доступ к заданиям

  • Триангуляция: точка вторая

Дополнительная информация

Сплайновые поверхности

Напомним некоторые понятия.

Регулярной поверхностью называется множество точек М(х, у, z) пространства, координаты х, у, z которых определяются из соотношений

x = x(u,v), y = y(u,v), z = z(u,v), (u,v)ÎD, (11)

гдe x(u,v), y(u,v), z(u,v) — гладкие функции своих аргументов, причем выполнено соотношение

= 2

D — некоторая область на плоскости параметров u и v. Последнее равенство означает, что в каждой точке регулярной поверхности существует касательная плоскость и положение нормали к этой плоскости при непрерывном перемещении по поверхности текущей точки изменяется непрерывно (рис.

Триангуляция Делоне

20). Уравнения (11) называются параметрическими уравнениями поверхности. Их часто записывают также в векторной форме:

r = r(u,v), (u,v)ÎD,

где

r(u, v) = (x(u, v), y(u,v), z(u,v)).

Будем считать для простоты, что область на плоскости параметров представляет собой стандартный единичный квадрат (рис. 21).

Ограничим наши рассмотрение наборами точек вида

Vij, i = 0, I, …, m; ,j = 0, 1, …, n.

Соединяя соответствующие вершины прямолинейными отрезками, получаем контрольный многогранник (точнее, контрольный, или опорный, граф) заданного массива V (рис. 22).

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

,

где a £ u £ b, g £ v £ d

То обстоятельство, что приведенное выше уравнение можно записать в следующей форме:

,

где i = 0,…,m, j = 0,…,n,

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

⇐ Предыдущая12345Следующая ⇒


Дата добавления: 2015-05-30; просмотров: 134; Опубликованный материал нарушает авторские права? | Защита персональных данных |


Не нашли то, что искали? Воспользуйтесь поиском:

Читайте также:


 

Триангуляция Делоне

 

В триангуляции Делоне в качестве исходных данных используются только точки.

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

 

Все треугольники триангуляции Делоне удовлетворяют условию Делоне: внутрь окружности, описанной вокруг треугольника, не попадает ни одна из точек, участвующих в триангуляции.

 

На приводимом рисунке показаны описанные окружности для нескольких треугольников триангуляции Делоне:

 

Заметим, что одним из свойств триангуляции Делоне является максимизация минимального угла среди всех углов всех построенных треугольников, т.е.

можно говорить о минимизации количества треугольников с острыми углами.

 

Триангуляция Делоне с ограничениями

 

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

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

 

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

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

 

 

На следующем рисунке показано, что для точек 1, 2, 3, 4 условию Делоне удовлетворяет треугольник, составленный из точек 1, 2, 4 (и смежный с ним треугольник из точек 2, 3, 4).

Однако построен треугольник из точек 1, 3, 4 и треугольник из точек 1, 2, 3, потому что ребро из точек 1 и 3 получено из исходной полилинии. Если построить треугольник 1-2-4, то получится ребро 2-4, которое будет пересекать исходное ребро 1-3, что недопустимо:

 

 

 

Недостатки триангуляции Делоне с ограничениями

 

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

 

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

 

 

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

 

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

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

 

 

На следующем рисунке – фрагмент того же участка модели поверхности в 3D окне:

 

 

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

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

 

Таким образом, если в чистом виде использовать триангуляцию Делоне с ограничениями применительно к изолиниям рельефа, то:
1. Модель поверхности будет содержать заведомые ошибки в случае использования ее для подсчета объемов.
2. Визуально модель поверхности будет выглядеть неестественно.

 

 

 

«Рисунок» изолиний – дополнительный источник информации

 

 

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

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

 

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

Кстати, в программе DIGIMINE имеются удобные механизмы для выполнения задачи типа построения тальвегов, вручную. Если в процессе ввода тальвега сначала пристыковаться  к одной изолинии, ввести промежуточные точки, а потом пристыковаться к другой изолинии, то промежуточным точкам вводимой полилинии будут автоматически присвоены «правильные» высотные отметки.

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

 

 

 

 

Проблемы триангуляции — не только с изолиниями

 

Выше были рассмотрены проблемы, возникающие при построении моделей поверхностей с использованием изолиний.

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

 

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

 

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

 

 

Некорректные площадки появляются также при триангуляции откосов уступов:

 

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

 

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

 

 

 

 

 

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

 

В программе DIGIMINE реализовано несколько вариантов триангуляции. Кроме триангуляции Делоне с ограничениями и упомянутой триангуляции с соединением в пределах прямой видимости, имеются еще 2 варианта триангуляции, в которых строятся треугольники, описывающие выпуклые или вогнутые формы рельефа (тальвеги/водоразделы, седловины, вершины/впадины). Более подробно – см. Варианты триангуляции при построении модели поверхности в программе DIGIMINE.

 

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*