Бесконечный начальный ограничительный треугольник в итерационных триангуляторах Делоне - PullRequest
Новая
       84

Бесконечный начальный ограничительный треугольник в итерационных триангуляторах Делоне

4 голосов
/ 04 сентября 2010

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

Но согласно «Числовым рецептам: искусство научных вычислений»:

"... если расстояние является лишь конечным (до граничных точек), построенная триангуляция может быть не совсем Делоне. Например, ее внешняя граница в необычных случаях может быть слегка вогнутой с небольшими отрицательными углами порядка диаметра набора «реальной» точки, деленного на расстояние до «фиктивных» (граничных) точек.

Итак, какие есть варианты для увеличения декартовых координат с точками на бесконечности, без необходимости преобразовывать все входные данные в другую систему координат, такую ​​как однородные координаты? Как эти точки соответствуют обычным геометрическим предикатам CCW и Incircle?

Окружность (a, b, c) Бесконечность -> Ложь. при условии, что a, b, c конечны.

Но как быть, когда один из a, b, c является точкой на бесконечности? Становится ли круг полуплоскостью, а затем проверка становится проверкой CCW? Что если 2 или более точек на окружности бесконечны? круг расширяется в полную плоскость, заставляя тест всегда давать истину? Как насчет CCW? Как вы классифицируете точку относительно линии, которая имеет одну или несколько точек на бесконечности?

Ответы [ 2 ]

0 голосов
/ 14 июля 2015

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

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

Затем вставьте каждую точку p, одну за другойкак обычно (алгоритм Бойера-Ватсона), путем (1) вычисления тетраэдра T, который содержит точку p (локализация) и (2) нахождения зоны конфликта, следующим образом:

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

(2) Для определения зоны конфликта требуется небольшая модификация:

  • Точка p находится в конфликте с конечным тетраэдром T, если он находится в своей ограниченной области (как обычно)

  • Для бесконечного тетраэдра T = (p1, p2, p3, p4) один из p1, p2, p3, p4 является бесконечной вершиной (например, p2, тогда T = (p1, бесконечный, p3,p4)).Чтобы проверить, находится ли p в конфликте с T, замените бесконечную вершину на p и вычислите подписанный объем тетраэдра: в нашем примере sign_volume (p1, p, p3, p4), если он положительный, то T находится в конфликтес р.Если оно отрицательно, то T не конфликтует с p.Если р точно на опорной плоскости трех конечных вершин Т, то Т, находится в конфликте с р, если Т «находится в конфликте с р, где Т» представляет собой тетраэдр рядом с Т по конечномугрань T (эквивалентно, вместо запроса T ', можно проверить, находится ли p в описанном круге конечного фасета T).

См. реализации в:

0 голосов
/ 15 декабря 2011

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

Некоторое время назад я написал генератор Делоне на Java, и он доступен здесь: http://open.trickl.com/trickl-graph/index.html

См. http://open.trickl.com/trickl-graph/apidocs/index.html и, в частности: 

    // Check if fourth point is within the circumcircle defined by the first three
   private boolean isWithinCircumcircle(PlanarGraph<V, E> graph, V first,
           V second,
           V third,
           V fourth) {
      // Treat the boundary as if infinitely far away
      Coordinate p = vertexToCoordinate.get(fourth);
      if (PlanarGraphs.isVertexBoundary(graph, first)) {
         return isLeftOf(third, second, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, second)) {
         return isLeftOf(first, third, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, third)) {
         return isLeftOf(second, first, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, fourth)) {
         return false;
      }

      Coordinate a = vertexToCoordinate.get(first);
      Coordinate b = vertexToCoordinate.get(second);
      Coordinate c = vertexToCoordinate.get(third);

      boolean within = (a.x * a.x + a.y * a.y) * getDblOrientedTriangleArea(b, c, p)
              - (b.x * b.x + b.y * b.y) * getDblOrientedTriangleArea(a, c, p)
              + (c.x * c.x + c.y * c.y) * getDblOrientedTriangleArea(a, b, p)
              - (p.x * p.x + p.y * p.y) * getDblOrientedTriangleArea(a, b, c) > 0;

      return within;
   }

Здесь граничные точки явно проверяются при проверке состояния окружности, поэтому их можно эффективно рассматривать как «бесконечно». Это гораздо проще, чем выяснить все геометрические значения, чем вы описываете.

...