Поиск на множестве тетраэдров

↑

▷ Содержание

⇐ ПредыдущаяСтр 43 из 43

Рис. 12.3.

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

Рис. 12.4.

1. Рассмотрим плоские фигуры, которые получаются при пересечении какой-либо грани некоторого тетраэдра с каким-либо тетраэдром. Это будут выпуклые фигуры от треугольника до шестиугольника. Разобьем их на треугольники.

2. Эти треугольники и треугольные грани всех тетраэдров спроецируем на плоскость XZ, считая, что их проекции не вырождаются в отрезки. Получим на плоскости XZ множество треугольников, которые могут пересекаться (рис. 12.3.). Найдем все точки пересечения сторон этих треугольников. Проведем через эти точки и вершины треугольников прямые, лежащие в плоскости XZ, параллельные оси Х (рис. 12.4.). При этом предполагаем, что стороны спроецированных треугольников не параллельны оси Х.

Рис. 12.5.

Рис. 12.6.

3. Две такие соседние прямые образуют полосу. При этом, отрезки, которые получаются при пересечении ребер треугольника с полосой, не пересекаются строго внутри полосы и строго внутри полосы нет вершин треугольников. Таким образом, для данной полосы мы можем упорядочить последовательность ребер треугольника, пересекающихся с этой полосой (рис. 12.5.). Для трапеции, образуемой соседними отрезками в полосе, можно занести в структуру совокупность треугольников, в которые она входит. Для некоторой трапеции рассмотрим множество прямых, проходящих через точки четырех ее сторон, перпендикулярно плоскости XZ. Эти прямые образуют замкнутую поверхность, ограничивающую некоторый объем в пространстве, который мы назовем «трубой». Можно упорядочить последовательность этих кусков граней для каждой «трубы». Для каждой области, ограниченной «трубой» и смежными кусками граней, заносим в структуру список тех тетраэдров, в которых она содержится.

4. Задача поиска решается в три этапа, причем, на каждом шаге используется дихотомия. Пусть дана точка (x,y,z), будем искать множество тетраэдров, которым она принадлежит. На первом этапе ищется полоса, в которой лежит точка (x,z). На втором – трапеция в этой полосе, в которую попадает точка (x,z). На третьем – область в трехмерной «трубе», ограниченная смежными кусками граней тетраэдров, которой принадлежит точка (x,y,z). Вычислительная сложность поиска равна O(ln(N)), где N-число тетраэдров.

В следующем разделе будет рассмотрено обобщение этой задачи для случая произвольных не самопересекающихся многогранников в E³. Для упрощения понимания в нём будут также подробно описаны некоторые материалы представленные в данном разделе.

12.3 Поиск на множестве произвольных несамопересекающихся многогранников Е³

Рис. 12.7.

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

Рис. 12.8.

Рис. 12.9.

1.      Рассмотрим область D, являющуюся пересечением плоскости T, содержащей грань G некоторого многогранника V с некоторым другим многогранником W. Считаем, что плоскость Т не проходит через вершины W. D может быть, в принципе, многосвязной областью, и его граница будет состоять из некоторой совокупности замкнутых кусочно-линейных контуров. Опишем, как строятся эти контуры. Пусть A={A_i,i=1,l} – совокупность всех ребер многогранника W, которые пересекаются с плоскостью Т и Р={Р_i, i=1,l} – совокупность точек пересечения соответствующих ребер с Т. Возьмем ребро A₁ и выберем одну из двух граней, которым A₁ принадлежит. Далее выбираем из всех ребер этой грани такое, что расстояние от точки пересечения соответствующей этому ребру до Р₁ является наименьшим. Продолжая процесс, мы переходим с очередной грани на смежную, по выбранному ребру, грань и строим последовательность ребер и последовательность соответствующих им точек пересечения с плоскостью Т из Р, которые задают контур, пока не вернемся к исходным ребру А₁ и точке Р₁. Таким образом, мы получаем замкнутый контур. Далее, выбираем любое ребро, не входящее в построенную последовательность ребер, и строим очередной контур по алгоритму, в точности совпадающему с вышеописанным. Продолжаем этот процесс, пока не исчерпаем множество А рёбер, пересекающих плоскость сечения Т. Получаем полностью построенную границу области D, состоящую из замкнутых контуров, представляющих собой некоторые многоугольники (рис. 12.8).

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

4. Проецируем разбитые таким образом грани на плоскость XZ. При этом считаем,

что проекции этих граней не являются отрезками. Получим на плоскости XZ множество фигур, которые могут пересекаться. Найдем все точки пересечения сторон этих фигур. Проведем через эти точки, а также через вершины фигур прямые, лежащие в плоскости XZ, параллельные оси Х (рис. 12.9). При этом предполагаем, что стороны спроецированных фигур не параллельны оси Х (опять же “неудобную” нам ситуацию устраняем некоторым поворотом осей координат).

Рис. 12.10.

Рис. 12.11.

4.      Любые две такие соседние прямые образуют полосу. При этом, отрезки, которые получаются при пересечении ребер фигуры с полосой, не пересекаются строго внутри полосы и строго внутри полосы нет вершин фигур, так как мы проводили прямые непосредственно через вершины фигур и точки пересечения сторон этих фигур (рис. 12.10а). Таким образом, в этой полосе находится некоторая совокупность непересекающихся отрезков, с вершинами на прямых, ограничивающих полосы, и для данной полосы мы можем упорядочить последовательность ребер фигуры, пересекающихся с этой полосой (рис. 12.10b). Если взять какую-либо трапецию, то для любой ее внутренней точки, прямая проходящая через нее перпендикулярно плоскости XZ, проходит ровно через ту совокупность граней многогранников, в проекции которых входит эта трапеция. Для некоторой трапеции рассмотрим множество прямых, проходящих через точки четырех ее сторон, перпендикулярно плоскости XZ. Эти прямые образуют замкнутую поверхность, ограничивающую некоторый объем в пространстве, который мы назовем «трубой». При пересечении «трубы» с гранями выделяются трехмерные области (рис. 12.11). Мы можем упорядочить грани и трехмерные области. Причем, все внутренние точки какой-либо такой области входят в одну и ту же совокупность многогранников из М и внутри «трубы» нет вершин многогранников. Заносим список этих многогранников в поисковую структуру. Получаем структуру для геометрического поиска на множестве многогранников М.

5.      Задача поиска решается в три этапа, причем, на каждом шаге используется дихотомия. Пусть дана точка (x,y,z), будем искать множество многогранников, которым она принадлежит. На первом этапе ищется полоса, в которой лежит точка (x,z). Так как множество прямых у нас упорядоченно и их количество - n, мы берём первую и [n/2] (целая часть от деления n на 2) прямые, далее проверяем лежит ли наша точка в полосе между этими двумя прямыми. Выбираем полосу в которой лежит наша точка и аналогично делим её на 2 примерно равных полосы. Алгоритм повторяется пока мы не найдём две соседние прямые между которыми лежит точка, положение которой мы определяем. На втором этапе определяем трапецию в этой полосе, в которую попадает точка (x,z). Проводим в найденной полосе прямую, параллельную оси ОХ и проходящую через искомую точку. Упорядочиваем множество точек пересечения отрезков в нашей полосе с этой прямой и далее как и на первом этапе используем дихотомию. На третьем этапе находим область в трехмерной «трубе», ограниченную смежными кусками граней тетраэдров, которой принадлежит точка (x,y,z).

6.      Суммарное число сторон всех спроецированных контуров, задающих границы областей пересечения многогранников с плоскостями, содержащими грани не превышает k². Соответственно, количество точек пересечения этих сторон между собой не превышает k⁴. Поиск для этого случая осуществляется так же, как и для множества тетраэдров и его вычислительная сложность равна О(ln(k)) + О(ln(k²)) + О(ln(k⁴)), т.е. равна О(ln(k)), (k-суммарное число граней всех многогранников из М).

12.4 Вопросы и упражнения

1. Какие типы запросов можно выделить при решении поисковых задач в вычислительной геометрии?

2. Сформулируйте задачу геометрического поиска для случая точки и множества многогранников.

3. Какова вычислительная сложность описанного в главе алгоритма геометрического поиска на выпуклом многоугольнике для случая уникальных запросов?

4. Какова вычислительная сложность описанного в главе алгоритма геометрического поиска на множестве многогранников?

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

6. Какова вычислительная сложность описанного в главе алгоритма геометрического поиска на произвольном многоугольнике при уникальных запросах?

7. Могут ли многогранники в задаче геометрического поиска описанного в главе быть не связными?

Список литературы

1. Ильин В. А., Позняк Э. Г. Аналитическая геометрия. М.: Наука, 1981.

2. Фокс А, Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. Пер. с англ. М.: Мир, 1982.

3. Фоли Дж., ван Дэм А. Основы интерактивной машинной графики. Кн.1, 2. Пер. с англ. М.: Мир, 1985.

4. Ньюмен У., Спрул Р. Основы интерактивной машинной графики. Пер. с англ. М.: Мир, 1985.

5. Роджерс Д. Алгоритмические основы машинной графики. Пер. с англ. М.: Мир, 1989.

6.  Шикин Е. В., Боресков А. В.Компьютерная графика. Динамика, реалистические изображения. М.: «ДИАЛОГ‑МИФИ», 1995.

7. Вельтмандер П. В. Машинная графика. (Учебное пособие). Новосибирский Государственный технический университет, Новосибирск, 1997.

8. Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. М.: «ДИАЛОГ‑МИФИ». 2001.

9. Эйнджел Э. Интерактивная компьютерная графика. Вводный курс на базе OpenGL. Изд. дом «Вильямс», Москва, Санкт-Петербург, Киев. 2001.

10. Matthew Ward, WPI CS Department .A (Spotty) History and Who's Who of Computer Graphics. http://web.cs.wpi.edu/~matt/courses/cs563/talks/history.html

11. What is Computer Graphics?

12. www.ccr.buffalo.edu/anstey/teaching/419_f02/aug27/two.html

13. Препарата Ф., Шеймос М. «Вычислительная геометрия: Введение» (Пер. с англ.). – Москва: "Мир", 1989. – 478 с.

14. Куликов А.И. Некоторые задачи вычислительной геометрии. Изогеометрическое сглаживание и геометрический поиск. //Труды конференции, GraphiCon2005, Novosibirsk, June 20 – June 24. – P.382-385.

15. Перепарата Ф., Шеймос М., Вычислительная геометрия: Введение. – М: Мир, 1989. – с.404 – 408

16. Медведев Н.Н. Метод Вороного – Делоне в исследовании структуры некристаллических систем. Издательство СО РАН, НИЦ ОИГГМ, Новосибирск, 2000.

Познавательные статьи:



Техника нижней прямой подачи мяча

Комплекс физических упражнений для развития мышц плечевого пояса

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов