Вычислительная геометрия (стр. 1 )

Введение

Вычислительная геометрия — это раздел математики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в компьютерной графике, проектировании, черчении и др. Исходными данными в такого рода задаче могут быть множество точек, набор отрезков, многоугольник (заданный, например, списком своих вершин в порядке обхода против часовой стрелки) и т. п. Результатом может быть либо ответ на какой-то вопрос (пересекаются ли эти два отрезка?), либо какой-то геометрический объект (например, наименьший выпуклый многоугольник, содержащий данные точки).

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

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

Основные разделы вычислительной геометрии:

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

Основная задача вычислительной геометрии

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

Работа с точками и отрезками на плоскости.

Наиболее простыми геометрическими объектами на плоскости являются точки и отрезки. Для начала напомним некоторые определения.

Основные определения

На плоскости задана декартова прямоугольная система координат, причем базис имеет правую ориентацию, т. е. ось Oy «получается» поворотом оси Ox против часовой стрелки.

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

Отрезок с концами в точках p1 и p2 — это множество точек, представимых в виде

Направление поворота

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

Векторным произведением двух векторов и

назовем число (!), равное .

Если сопоставить данное нами определение векторного произведения с тем, которое дается в курсах аналитической геометрии (наше произведение оказывается z-координатой «стандартного»), то ответ на поставленный вопрос очевиден: если , то A надо поворачивать против часовой стрелки, если , то A надо поворачивать по часовой стрелке, если , то векторы либо сонаправлены, либо направлены в противоположные стороны.

 

Алгоритмы решения задач.

Проверка пересечения отрезков

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

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

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

Теперь проверим для каждого из отрезков, пересекает ли он прямую, на которой лежит другой. Отрезок пересекает прямую, если его концы лежат по разные стороны от прямой или один из концов лежит на прямой. Последнее легко проверить, используя векторное произведение — векторы p1p3 и p1p4 должны иметь различную ориентацию относительно вектора p1p2.

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

Итог

Отрезки p1p2 и p3p4 пересекаются тогда и только тогда, когда одновременно выполнены три условия:

Пересекаются ограничивающие их прямоугольники.

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

Есть ли пересекающиеся отрезки?

Постановка задачи

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

Метод решения задачи

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

Введем отношение порядка на отрезках. Будем говорить, что два отрезка сравнимы относительно x, если вертикальная прямая с абсциссой x пересекает оба отрезка. При этом s1выше s2, если точка пересечения s1 с вертикальной прямой выше точки пересечения s2 с этой же прямой.

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

Движение прямой

Будем хранить следующую информацию:

Состояние дел у прямой — упорядоченное множество отрезков, пересекаемых прямой в данный момент времени. Расписание — список критических точек — состояние дел у прямой может измениться только в них.

При этом структура данных, реализующая состояние дел у прямой, должна поддерживать следующие операции:

INSERT(s) — добавить отрезок s DELETE(s) — удалить отрезок s ABOVE(s) — указать отрезок, располагающийся непосредственно выше s BELOW(s) — указать отрезок, располагающийся непосредственно ниже s

С использованием сбалансированного дерева поиска (например, AVL-дерева или красно-черного дерева) все эти операции можно реализовать за O(logn).

Итог: общий алгоритм

1 сортируем концы отрезков в порядке возрастания абсцисс

  (точки с равными абсциссами идут в порядке возрастания

  ординат); проверяем, нет ли совпадающих точек среди