Квазитриангуляция

Поделись знанием:
Перейти к: навигация, поиск

Квазитриангуляция — структура разбиения плоскости, обладающая свойствами триангуляции Делоне, но вершинами которой служат не точки, а произвольно наклонённые отрезки[1]. Строго говоря, это разбиение не является триангуляцией в геометрическом смысле, то есть разбиением плоскости на треугольные грани, но является триангуляцией в топологическом смысле.





Структура

Принцип построения структуры основан на (мысленной) замене каждого отрезка топологии на множество тесно (в пределе — бесконечно близко) расположенных точек и построения для всех этих точек триангуляции Делоне. Важно различать два типа граней: грани, инцидентные трём отрезкам, и грани, инцидентные только двум различным отрезкам. Грани второго типа группируются в кластеры — цепочки смежных граней, соединяющих одну и ту же пару отрезков. Если удалить все внутренние рёбра такой цепочки, то все грани цепочки объединяются в одно квазиребро (см. рис.). В общем случае, такое квазиребро имеет четырёхугольную форму, причём с двух противоположных сторон оно ограничено частями соединяемых отрезков, а с двух других — парой оставшихся не удалёнными рёбер. Для квазиребра эта пара не удалённых рёбер играет роль пары противоположно ориентированных квазидуг некоего квазиграфа. В топологическом смысле этот квазиграф является триангуляцией, то есть он планарен и все его грани — а это как раз грани первого типа — треугольные. Роль вершин квазиграфа играют отрезки.

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

Свойства

1. Любая вершина квазитриангуляции всегда соединена ребром с ближайшей к ней вершиной.

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

3. Если грань инцидентна внутренней точке отрезка топологии, то этот отрезок направлен по касательной к окружности, описанной вокруг этой грани.

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

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

См. также

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

Напишите отзыв о статье "Квазитриангуляция"

Примечания

Литература

  • Лузин С. Ю., Лячек Ю. Т., Петросян Г. С., Полубасов О. Б. Модели и алгоритмы автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. — СПб.: БХВ-Петербург, 2010. — С. 224. — ISBN 978-5-9775-0576-5.

Отрывок, характеризующий Квазитриангуляция

– А много вы нужды увидали, барин? А? – сказал вдруг маленький человек. И такое выражение ласки и простоты было в певучем голосе человека, что Пьер хотел отвечать, но у него задрожала челюсть, и он почувствовал слезы. Маленький человек в ту же секунду, не давая Пьеру времени выказать свое смущение, заговорил тем же приятным голосом.
– Э, соколик, не тужи, – сказал он с той нежно певучей лаской, с которой говорят старые русские бабы. – Не тужи, дружок: час терпеть, а век жить! Вот так то, милый мой. А живем тут, слава богу, обиды нет. Тоже люди и худые и добрые есть, – сказал он и, еще говоря, гибким движением перегнулся на колени, встал и, прокашливаясь, пошел куда то.
– Ишь, шельма, пришла! – услыхал Пьер в конце балагана тот же ласковый голос. – Пришла шельма, помнит! Ну, ну, буде. – И солдат, отталкивая от себя собачонку, прыгавшую к нему, вернулся к своему месту и сел. В руках у него было что то завернуто в тряпке.
– Вот, покушайте, барин, – сказал он, опять возвращаясь к прежнему почтительному тону и развертывая и подавая Пьеру несколько печеных картошек. – В обеде похлебка была. А картошки важнеющие!
Пьер не ел целый день, и запах картофеля показался ему необыкновенно приятным. Он поблагодарил солдата и стал есть.
– Что ж, так то? – улыбаясь, сказал солдат и взял одну из картошек. – А ты вот как. – Он достал опять складной ножик, разрезал на своей ладони картошку на равные две половины, посыпал соли из тряпки и поднес Пьеру.
– Картошки важнеющие, – повторил он. – Ты покушай вот так то.
Пьеру казалось, что он никогда не ел кушанья вкуснее этого.
– Нет, мне все ничего, – сказал Пьер, – но за что они расстреляли этих несчастных!.. Последний лет двадцати.
– Тц, тц… – сказал маленький человек. – Греха то, греха то… – быстро прибавил он, и, как будто слова его всегда были готовы во рту его и нечаянно вылетали из него, он продолжал: – Что ж это, барин, вы так в Москве то остались?
– Я не думал, что они так скоро придут. Я нечаянно остался, – сказал Пьер.
– Да как же они взяли тебя, соколик, из дома твоего?
– Нет, я пошел на пожар, и тут они схватили меня, судили за поджигателя.
– Где суд, там и неправда, – вставил маленький человек.
– А ты давно здесь? – спросил Пьер, дожевывая последнюю картошку.
– Я то? В то воскресенье меня взяли из гошпиталя в Москве.
– Ты кто же, солдат?
– Солдаты Апшеронского полка. От лихорадки умирал. Нам и не сказали ничего. Наших человек двадцать лежало. И не думали, не гадали.
– Что ж, тебе скучно здесь? – спросил Пьер.
– Как не скучно, соколик. Меня Платоном звать; Каратаевы прозвище, – прибавил он, видимо, с тем, чтобы облегчить Пьеру обращение к нему. – Соколиком на службе прозвали. Как не скучать, соколик! Москва, она городам мать. Как не скучать на это смотреть. Да червь капусту гложе, а сам прежде того пропадае: так то старички говаривали, – прибавил он быстро.
– Как, как это ты сказал? – спросил Пьер.
– Я то? – спросил Каратаев. – Я говорю: не нашим умом, а божьим судом, – сказал он, думая, что повторяет сказанное. И тотчас же продолжал: – Как же у вас, барин, и вотчины есть? И дом есть? Стало быть, полная чаша! И хозяйка есть? А старики родители живы? – спрашивал он, и хотя Пьер не видел в темноте, но чувствовал, что у солдата морщились губы сдержанною улыбкой ласки в то время, как он спрашивал это. Он, видимо, был огорчен тем, что у Пьера не было родителей, в особенности матери.