Содержание к диссертации
Введение
Глава 1. Методы восстановления поверхности объекта по набору изображений 11
1.1 Историческое развитие методов моделирования объектов 11
1.2 Методы реконструкции моделей объектов 13
1.3 Пассивные методы 16
1.4 Активные методы 17
1.5 Анализ результатов 19
Глава 2. Основы стереореконструкции ., 20
2.1 Модель камеры 20
2.2 Калибровка камеры 22
2.2.1 Параметры камеры 22
2.2.2 Методы калибровки камеры 23
2.3 Работа с некалиброванными изображениями 25
2.3.1 Определение внутренних параметров камеры 25
2.3.2 Определение внешних параметров камеры 26
2.4 Анализ пары снимков 26
2.4.1 Взаимное ориентирование снимков 27
2.4.2 Определение элементов взаимного ориентирования 32
2.4.2.1 Приведение уравнения к линейному виду 32
2.4.2.2 Использование упрощённого случая съёмки 32
2.4.3 Трансформация снимка, вызванная его переводом в другое положение 35
2.4.4 Определение координат точек объекта 38
2.5 Определение точек соответствия 39
2.5.1 Эпиполярная прямая 40
2.5.2 Методы поиска соответствий 42
2.5.3 Повышение эффективности методов согласования 48
2.5.3.1 Двухэтапный алгоритм 48
2.5.3.2 Иерархический алгоритм 49
2.5.3.3 Использование дополнительных изображений 52
2.5.3.4 Использование условия упорядочивания и динамического программирования 53
2.6 Анализ результатов 54
Глава 3 Выделение объекта па изображении 56
3.1 Постановка задачи 56
3.2 Сегментация 56
3.3 Построение контура 62
3,3.1 Выделение прямых линий на изображении 63
3.4 Анализ результатов 69
Глава 4 Восстановление формы поверхности объекта 71
4.1 Постановка задачи 71
4.2 Обзор методов 72
4.3 Триангуляция Делоне для конечного набора точек 75
4.3.1 Структура хранения элементов триангуляционного разбиения 75
4.3.2 Алгоритм построения триангуляции Делоне для конечного набора точек 76
4.3.2.1 Выбор первого ребра 78
4.3.2.2 Формирование области поиска следующей точки 78
4.3.2.3 Принцип выбора следующей точки для построения нового треугольника 80
4.3.2.4 Клеточный пошаговый алгоритм 83
4.3.2.5 Новый метод выбора следующей точки для построения треугольника 84
4.3.2.6 Построение нового треугольника 90
4.3.3 Сравнение эффективности модифицированного алгоритма прямого построения с традиционными методами 91
4.4 Создание триангуляционного разбиения с учетом особенностей формы объекта 97
4.4.1 Подразбиение готовой триангуляции в соответствии с контурными линиями 99
4.4.1.1 Поиск треугольника из триангуляционного разбиения, касающегося или включающего в себя один из концов контурного отрезка 100
4.4.1.2 Последовательный переход по ветке соседних рёбер к треугольникам, пересекающим контурный отрезок 102
4.4.2 Перестройка триангуляционного разбиения в соответствии с контурными линиями 105
4.4.3 Сужение выпуклой триангуляции до границ объекта 111
4.5 Иерархическое восстановление поверхности объекта 115
4.6 Анализ результатов 118
Глава 5 Вычисление метрических характеристик объекта 120
5.1 Получение координат точки на поверхности объекта по координатам точки на его проекции 120
5.2 Определение расстояния между точками по поверхности объекта 123
5.3 Вычисление площади поверхности выделенного фрагмента 125
5.3.1 Триангуляционное разбиение внутренности фрагмента 125
5.3.2 Определение площади поверхности, используя текущее триангуляционное разбиение 127
5.3.2.1 Определение граничных треугольников, опоясывающих границу выделенного фрагмента и резание этих треугольников по границе 129
5.3.2.2 Формирование фигуры внутри треугольника 131
5.3.2.3 Вычисление площади многоугольной фигуры 133
5.3.2.4 Алгоритм определения площади части фрагмента отсекаемой треугольником 137
5.3.2.5 Новый алгоритм определения площади части фрагмента, попавшего во внутренность треугольника 141
5.3.2.6 Определение треугольников, целиком лежащих на объекте и вычисление их площади 146
5.4 Анализ результатов 149
Глава 6 Построение диалоговой системы. Программная реализация 150
6.1 Требования к диалоговой системе 150
6.2 Технические характеристики системы 152
6.3 Этапы работы комплекса 152
6.4 Улучшение поверхности объекта 157
6.5 Проведение бесконтактных измерений на поверхности объекта 158
6.7 Анализ результатов 160
Выводы по диссертации 162
Библиографический список 164
Приложение. Акты внедрения 177
- Историческое развитие методов моделирования объектов
- Модель камеры
- Выделение прямых линий на изображении
- Триангуляция Делоне для конечного набора точек
- Получение координат точки на поверхности объекта по координатам точки на его проекции
Введение к работе
Актуальность темы: Определение качественных геометрических характеристик объектов необходимо в различных областях науки и техники: в геодезии и астрономии, военно-инженерном деле и артиллерии, архитектуре и строительстве, географии и океанологии, судебной медицине и криминалистике, атомных испытаниях и космических исследованиях и т.д.
Долгое время все операции связанные с геометрическими измерениями, выполнялись вручную и поэтому являлись не производительными. Качество и объём работ зависели от субъективных факторов. Появление фотографии положило начало фотограмметрии - науке об определении формы, размера, и пространственного положения различных объектов посредством измерения их фотографических изображений [6]. Данный подход имеет ряд преимуществ, а именно: высокую точность измерений, большую производительность труда и возможность измерения параметров объекта бесконтактным методом [36]. Обработка снимков производится на различных приборах: стереопроекторах, стереоавтографах стереокомпараторах, мои о компараторах и т.д. [35]. Несмотря на высокую стоимость приборов, применение фотограмметрических методов имеет значительные экономические преимущества.
На данный момент имеется достаточно большой выбор средств получения изображений с высоким разрешением. Появившаяся в последнее время доступная по цепе массовая цифровая съемочная аппаратура, быстро совершенствуясь, теснит традиционную фотоаппаратуру, поскольку точность измерений по снимкам, полученным цифровыми камерами, оказалась достаточной для решения многих фотограмметрических задач.
Бурное развитие вычислительной техники, которая становится всё более производительной и доступной по цене, а также применение изображений, получаемых цифровыми съемочными системами, позволяют резко удешевить и автоматизировать процесс измерения. Для этого все этапы работы со снимками на дорогостоящих приборах заменяются обработкой изображений на обычном персональном компьютере [60]. На сегодняшний день существует несколько программных продуктов, использующих данный подход (ImageModeler [96], ВИДИС [10], Photomodeler [94] и т.д.). Основные недостатки существующих программных комплексов: значительная доля участия человека, как оператора фотограмметрических преобразований; использование дополнительных устройств, которые находятся в прямом взаимодействии с объектами сцены, оказывают на сцену воздействие и сами являются ее участниками; сложность работы с комплексом, что создаёт проблемы в обучении операторов.
Поэтому актуальной задачей является комплексная автоматизация системы восстановления модели поверхности объекта по его изображениям, т. е. сведение к минимуму участия человека как оператора, без использования дополнительного оборудования.
Для вычисления метрических характеристик объекта необходимо с высокой степенью точности восстановить модель его поверхности. Методы реконструкции поверхностей играют большую роль в процессе современного промышленного проектирования и производства. Они широко применяются в машиностроении, медицине, археологии, в области мультимедиа и т.д. В настоящее время актуальной является проблема точной реконструкции сложных поверхностей с минимальной трудоёмкостью.
Цель работы; Решение задачи правильного восстановления геометрии объекта. Разработка методов и алгоритмов по автоматизации процесса бесконтактного измерения поверхности объекта и создание на их основе стереофото-грамметрической системы с соответствующим программным обеспечением. Разработка алгоритмов вычисления метрических характеристик объекта.
Методы исследования: В работе использовались теоретические и методологические основы фотограмметрии, методы аналитической геометрии и векторной алгебры, основные положения вычислительной и проективной геометрии, методы программирования, применены подходы, базирующиеся на методах теории графов, а также использовались методы современной компьютерной обработки изображений и геометрического моделирования с визуализацией результатов моделирования.
Научная новизна состоит: в новом методе иерархического восстановления моделей сложных поверхностей; в алгоритме реконструкции поверхности, представляющем собой модификацию классического метода прямого построения триангуляции Делоне. Применены подходы, оптимизирующие его трудоёмкость; в методах и алгоритмах триангуляции в заданном контуре и перестройки триангуляционного разбиения с учетом особенностей формы объекта, представляющие собой модификацию методов построения триангуляции Делоне с ограничениями; в методах и алгоритмах для проведения измерений на заданной поверхности; в создании диалоговой системы, выполняющей точное определение геометрических характеристик объекта по набору изображений.
Теоретическая и практическая ценность: В диссертации, выполненной в рамках фундаментальной НИР "Разработка теоретических основ алгоритмов и программ геометрии и графики для параллельных технологий проектирования" (ГР № 01970004538, Нижегородский государственный архитектурно-строительный университет), предложены методы, позволяющие автоматизировать процесс восстановления поверхности объекта по его изображениям. На основе этих подходов создан программный комплекс, проводящий бесконтактные измерения на поверхности объекта с ярко выраженными контурами. Предложенная в диссертационной работе методика реконструкции сложной поверхности объекта также может быть использована в различных областях, исполь-
9 зующих цифровую модель поверхности (компьютерной графике, медицине, горном деле и т.д.).
Апробация работы:
Результаты диссертационной работы докладывались: на 10-й Нижегородской сессии молодых учёных. Технические науки (март 2005 г.); на заседании кафедры "Начертательная геометрия и компьютерная графика" (июнь 2005 г.); на научно-методической конференции профессорско-преподавательского состава, аспирантов и специалистов (г. Н. Новгород, ВГАВТ, декабрь 2005 г.); на 11-й Нижегородской сессии молодых учёных. Технические науки (февраль 2006 г.); на поволжской региональной научно-методической конференции "Компьютерная графика и мультимедийные технологии в задачах конструирования и проектирования" (Саратов, СГТУ, апрель 2006 г.).
Публикации: По теме диссертационной работы опубликовано 13 печатных работ [107-119].
Структура и объем работы: Работа состоит из введения, шести глав, выводов, списка литературы включающего 119 наименований и приложения. Работа содержит 176 страниц машинописного текста, 38 рисунков, 1 таблицу.
Во введении обоснована актуальность темы, сформулированы цели и задачи исследований, отмечена научная новизна и практическая значимость работы.
В главе 1 содержится краткий обзор литературы по теме восстановления поверхности объекта, используя его изображения, формулируются достоинства и недостатки изложенных в этом обзоре методов. Описано историческое развитие методов моделирования объектов. Обобщаются традиционные подходы к решению этой проблемы.
В главе 2 вводятся необходимые определения и обозначения. На основе фотограмметрических методов создаётся модель "изображение - объект", позволяющая получить пространственные координаты точек объекта по паре изображений.
В главе 3 рассмотрены методы предварительной обработки изображения и выделения характерных элементов на нём. Предложены методы и алгоритмы позволяющие облегчить процедуру выделения объекта на изображении.
В главе 4 приведён краткий обзор методов восстановления поверхности по набору точек и предложены подходы, позволяющие точно реконструировать форму поверхности.
В главе 5 предложены методы и алгоритмы для проведения измерений на заданной поверхности.
В главе 6 изложены основные принципы построения диалоговой системы, позволяющей осуществлять бесконтактный обмер объектов. Диалоговая система представляет собой комплекс программ, являющийся программной реализацией методов и алгоритмов, изложенных в предыдущих главах.
В заключении перечисляются основные результаты диссертационной работы и формулируются необходимые выводы.
Историческое развитие методов моделирования объектов
Попытки восстановления моделей объектов предпринимались довольно давно. Одним из первых и самых распространенных средств информационного восстановления моделей в течение длительного исторического периода являлось проекционное изображение на плоскости, полученное различными способами при произвольном аппарате проецирования. Однако изображение модели должно быть понятным и близким к реальной модели, что обуславливает необходимость разработки новых форм предметного изображения объекта - макетирования и моделирования [24]. Главным недостатком такого представления долгое время являлось использование большое количество ручного труда. В настоящее время появилась возможность существенно сократить долю ручного труда, применением автоматизированных систем на основе ЭВМ. Очень интересным подходом может быть реконструкция моделей реальных объектов на основе серии обычных изображений физических объектов и сред, сделанных с различных точек наблюдения [19]. Сопоставляя эти изображения, в ряде случаев можно реконструировать поверхность изображаемых объектов. Основы теории определения положения объектов в пространстве по их перспективным изображениям были положены еще в средние века. В XVIII веке перспективные рисунки стали использоваться в топографических целях. Появление фотографии положило начало фотограмметрии - науке об определении форм, размеров и пространственного положения различных объектов посредством измерения их фотографических изображений [6]. В начале XX века был изобретен стереокомпаратор - прибор для измерения пространственного положения объектов по паре перекрывающихся фотографических изображений [60]. Интерес к методам восстановления моделей объекта по его плоским изображениям возобновился в середине XX столетия в связи с исследованиями в области искусственного интеллекта, а практическая потребность в робототехнических устройствах, способных ориентироваться в трехмерном пространстве, постоянно поддерживает этот интерес в последние десятилетия [9].
На данный момент имеется достаточно большой выбор средств получения изображений с высоким разрешением, необходимым для точного восстановления трёхмерной модели поверхности объекта. К ним относятся фотографические камеры, позволяющие получить высококачественное изображение объекта, пригодное для дальнейшей оцифровки сканером, видеокамеры на базе ПЗС матриц и цифровые фотограмметрические камеры. Появившаяся в последнее время доступная по цене массовая цифровая съемочная аппаратура, быстро совершенствуясь, теснит традиционную фотоаппаратуру [5, 8].
Основные преимущества цифровых камер [12]:
- общедоступность;
- оперативное получение цветных изображений без фотолабораторных работ;
- низкая стоимость;
- малая масса;
- простота в управлении.
Как показано в работах [14, 61, 65], достижимая точность измерений, по снимкам, полученным цифровыми камерами, оказалась достаточной для решения многих фотограмметрических задач.
Широкое внедрение вычислительной техники, сопровождаемое быстрым снижением ее стоимости и увеличением мощности и быстродействия, а также применение изображений, получаемых цифровыми съемочными системами, по 13 зволяет заменить все этапы работы со снимками на громоздких и дорогостоящих приборах, обработкой изображений на обычном персональном компьютере [26]. В работе [55] указывается отличительная черта такого подхода. Это более глубокая и сложная обработка снимков и менее жёсткие фотограмметрические требования к геометрии съёмки и снимков. К сожалению, сегодня совсем немного систем, позволяющих использовать такой подход в полной мере и достаточно эффективно, хотя работы в этом направлении интенсивно ведутся.
Модель камеры
Модель центральной перспективы (точечной перспективы) впервые была предложена Брунеллеччи в начале XV века. Она удобна с математической точки зрения. Несмотря на свою простоту, модель центральной перспективы часто является приемлемым приближённым описанием процесса формирования изображения. В результате перспективной проекции возникает перевёрнутое изображение. Иногда вместо такого изображения удобно рассматривать мнимое изображение, которое расположено в плоскости, лежащей перед отверстием, концентрирующем лучи света, на таком же расстоянии, как и реальная плоскость изображения [56]. Мнимое изображение по всем параметрам точно соответствует реальному изображению. Отличие состоит только в том, что оно не перевёрнуто. В дальнейшем будет использоваться модель мнимого изображения.
В случае рассмотрения модели современной камеры, оснащённой линзами, в предыдущую модель, на место отверстия, концентрирующего лучи света, добавляется реальная линза (толстая линза) (рис. 2.1).
Уравнения, описывающие поведение толстой линзы, легко выводятся из уравнения параксиального преломления [56]. Они выглядят так же, как и уравнения для тонких линз: дальнейшем необходимо считать, что камера сфокусирована на бесконечности fz —»оО), так что расстояние от отверстия (центра линзы) до плоскости изображения (z) равно фокусному расстоянию (/). Также построенная модель камеры будет пренебрегать геометрическими искажениями (аберрациями), присущими реальным линзам.
Пусть (S,X,Y,Z) - система координат, связанная с камерой, начало координат S которой совпадает с оптическим центром камеры, а векторы Хи Y образуют базис векторной плоскости, параллельной плоскости мнимого изображения Р, которая находится на расстоянии / от отверстия в отрицательном направлении вектора Z (рис. 2.2), Прямая проходящая через отверстие и перпендикулярная к Р, называется оптической осью, а точка О, в которой она Пересе 22 кается с Р, называется главной точкой снимка. Эту точку можно использовать в качестве начала системы координат, связанной с плоскостью изображения, и она играет важную роль в процедурах калибровки камер.
На практике реальная система координат и система координат камеры связаны рядом физических параметров, таких как фокусное расстояние линзы, размеры пикселей, положение главной точки, положение и ориентация камеры.
Выделение прямых линий на изображении
Для более быстрого и эффективного выделения прямых линий на изображении Д. Канни в своей работе [69] предложил разделить этот процесс на несколько стадий:
- выделение краевых точек на изображении.
К изображению применяется фильтр Собела, описанный ранее. В результате формируется массив краевых точек, в каждом элементе которого, помимо информации о положении точки (х,у), хранится угол градиента, вычисленный по формуле (3.1). Все краевые точки отмечены как "неиспользованные".подавление не максимумов.
Данная операция используется с целью уменьшения толщины контура изображения (упрощение контура). Подавление не максимумов представляет собой удаление пикселей, модуль градиента которых не является локально максимальным. То есть, значение модуля градиента в данном пикселе меньше значения модуля одного из его соседей, примыкающих к одной из его сторон.
- пороговая обработка с концепцией гистерезиса. Выделение краевых точек путём использования обычной пороговой проверки может привести к разрывам контура. Для устранения таких случаев используется концепция гистерезиса. То есть для проверки используются два порога: верхний и нижний. Если значение модуля градиента меньше нижнего порога, то данная точка удаляется из рассмотрения. Точка является краевой, если значение модуля градиента в этой точке больше верхнего порога. Если же значение находится между двумя порогами, такие точки будут называться "кандидатами". "Кандидаты" становятся краевыми точками в том случае, если они связаны с остальными краями. В своей работе Канни рекомендует отношение верхнего порога к нижнему порогу на уровне 3:1 или 2:1.
- формирование прямых линий, используя информацию о краевых точках и точках - "кандидатах".
Для реализации последней стадии работы метода автором были разработаны три алгоритма формирования прямых линий.
В процессе работы алгоритмов используется понятие "сканирующего окна", представляющего собой прямоугольник заданного размера, центр которого расположен в рассматриваемой точке. Размеры окна могут регулироваться пользователем. По умолчанию ширина и высота окна составляют 8 пикселей.
Окрестностью точки будет считаться набор точек попавших внутрь "сканирующего окна", центр которого расположен в этой точке.
Каждой точке приписывается атрибут, представляющий собой показатель попадания данной точки в состав одного из сформированных отрезков. Атрибуту присваивается значение "использованная", если рассматриваемая точка задействована при формировании одного из отрезков. В противном случае атрибут имеет значение "неиспользованная".
Точка, которая рассматривается в данный момент работы алгоритма, будет называться текущей.
Триангуляция Делоне для конечного набора точек
Удачный выбор структуры хранения для представления триангуляции может оказать значительно влияние на трудоёмкость алгоритмов, использующих данную структуру, а также на скорость обработки при их реализации. Существует несколько основных способов представления. Это вершишю-рёберная, треугольная и рёберная структуры [49]. Для большинства методов, применяющих триангуляционную модель, необходимо быстро определять номера рёбер смежных треугольников. К числу таких методов относятся также методы, осуществляющие обмер на поверхности объекта. Исходя из этого, оптимальным выбором структуры является зависимость "ребро —» треугольники".
То есть, для данного ребра определяется список соседних с ним треугольников: Структура Ребро
Узелр! - указатель на первую концевую вершину ребра Узел р2 - указатель на вторую концевую вершину ребра
Ребро si -указатель на соседнее ребро, примыкающее кузлурї, справа от вектора р2р] Ребро s2 -указатель на соседнее ребро, примыкающее кузлур2, справа от вектора p2pl Ребро s3 -указатель на соседнее ребро, примыкающее кузлурї, слева от вектора p2pl Ребро s4-указатель на соседнее ребро, примыкающее кузлур2, слева от вектора p2pl
В данной структуре треугольники в явном виде не хранятся и представляют собой набор рёбер, составляющих эти треугольники. Первый треугольник заключён между текущим ребром и рёбрами si и s2, а второй - между рёбрами s3, s4 и текущим ребром. Таким образом, в структуре "Ребро" хранятся два соседних к текущему ребру треугольника.
Также вводятся дополнительные правила формирования структуры "Ребро". Рёбра si, s2 должны находиться справа от вектораp2pl, a s3, s4 - слева. Причём, рёбра si, s3 должны иметь в своей структуре точку pi, равную точке pi текущего ребра, а рёбра s2, s4 должны иметь в своей структуре точку р2, равную точкер2 текущего ребра. Такое формирование структуры позволяет быстро передвигаться по соседним треугольникам в указанном направлении.
Опорные точки, характеризующие узловые точки триангуляционного разбиения, представлены следующим образом: Структура Узел Х- координата по оси ОХ Y- координата по оси 0Y Z- координата по оси 0Z.
Во внутреннем представлении координаты Хи Y хранятся в виде целых чисел. Как описано в работе [50], это позволяет в явном виде контролировать возникающие при вычислениях ошибки округлений и избегать нарушений структуры триангуляции.
Получение координат точки на поверхности объекта по координатам точки на его проекции
В качестве проекции объекта используется одно из его изображений (фотоснимок). Это справедливо, поскольку согласно теории идеальной оптической системы, разработанной Гауссом в 1841 г., сохраняется гомоцентричность пучков, т.е. исходящий из одной точки пучок лучей после прохождения оптической системы даёт изображение одной точки и каждой точке в пространстве объектов соответствует точка в пространстве изображений. Поверхность объекта определяется его триангуляционным разбиением. Поскольку изображения поверхности объекта получены без перекрытий, набор треугольников на поверхности объекта проектируется в набор треугольников на его изображении. Таким образом, сформировано триангуляционное разбиение, покрывающее изображение объекта.
Автором разработан быстрый метод, позволяющий по заданным координатам проекции точки (х,у), определить координаты этой точки на поверхности объекта. Идея метода:
Пользователь отмечает точку на изображении объекта. Путём перехода по ветке соседних треугольников покрывающих изображение объекта определяется треугольник, в который попала эта точка. Соответствующий ему треугольник на поверхности объекта, включает в себя искомую точку. С другой стороны, согласно теории идеальной оптической системы точка объекта, её изображение (проекция) и центр проецирования (точка фотографирования) лежат на одной прямой. Зная координаты точки на изображении и точки проецирования можно сформировать эту прямую. В результате пересечение данной прямой с плоскостью найденного треугольника даёт координаты искомой точки на поверхности объекта.
Формально пошаговый алгоритм выглядит следующим образом:
Шаг 1: Производится проверка, попала ли точка (х,у) в рамку окаймляющую объект. В случае если точка выходит за границы рамки, выдаётся соответствующее сообщение и происходит аварийное завершение функции с кодом ошибки.
Шаг 2: Определение номера квадрата, в который попала точка (предварительно вся область разбивается на сектора (квадраты) для оптимизации работы алгоритма).
Шаг 3: Выбор произвольного ребра из этого квадрата.
Шаг 4: Переход по ветке соседних треугольников путём кратчайшего расстояния по направлению к данной точке. Если соседних треугольников в данном направлении не обнаружено, то происходит аварийное завершение функции с кодом ошибки (точка не лежит в области покрытой триангуляцией).
Шаг 5: Если во время перехода по ветке соседних треугольников, один из соседних треугольников совпадает с треугольником предыдущего шага, то треугольник, в котором лежит искомая точка, найден, иначе переход на шаг 4. Шаг 6: По треугольнику, в который попала точка в плоскости изображения, определяется соответствующий ему треугольник на поверхности объекта. Шаг 7: Формируется уравнение плоскости, проходящей через три вершины треугольника, определённого на шаге 6. Шаг 8: Формируется уравнение прямой линии, проходящей через начало координат (центр проецирования) и данную точку (x,y,J), где/- фокусное расстояние. Шаг 9: Определяется точка пересечения сформированной плоскости (шаг 7) и прямой линии (шаг 8). Использование упорядочивания рёбер триангуляционного разбиения по квадратам позволило сделать время поиска треугольника, включающего отмеченную точку, практически не зависящим от величины триангуляционного разбиения. Структура триангуляционного разбиения представляет собой планар-ный прямолинейный граф, где вершинами графа являются точки объекта (вершины треугольников), а рёбрами являются прямолинейные отрезки, соединяющие эти точки (стороны треугольников). Использование такой структуры позволило резко снизить перебор треугольников на попадание внутрь их данной точки.
