Вычисление области пересечения полуплоскостей
Прямая линия делит плоскость на две полуплоскости, по одной с каждой стороны прямой линии. Полуплоскости являются самыми простейшими из выпуклых планарных областей, но путем выполнения операций пересечения и объединения соответствующим образом выбранных полуплоскостей из них может быть сформирован любой полигон. В этом разделе мы ограничимся задачей формирования области пересечения для коллекции полуплоскостей.
Пусть Н будет коллекцией полуплоскостей и через I(H) обозначим область их пересечения. Если она непуста, то область I(H) называется выпуклым политопом. Область I(H) безусловно является выпуклой, поскольку пересечение выпуклых областей всегда выпуклое. На рис. 1 изображены два выпуклых политопа, образованных пересечением полуплоскостей. На рисунке а это выпуклый полигон, тогда как на рисунке 6 получился неограниченный выпуклый политоп. Полуплоскость в Н является лишней, если ее удаление не изменит I(H). На рисунке ниже лишняя только полуплоскость, определяемая прямой линией е.
 |
Один из способов формирования пересечения n полуплоскостей заключается в их поочередной обработке. Самая непосредственная реализация такого подхода будет выполняться за время 0(n2). Но здесь с успехом можно применить способ "разделяй и властвуй", поскольку набор пересечений ассоциативен - область пересечения п полуплоскостей может быть получена вычислением пересечения пар полуплоскостей в любом порядке. Следовательно, при любом делении набора Н на два непустых поднабора Н1 и Н2 будем иметь I(H) = I(H1) П I(H2). Для вычисления I(H) с использованием способа "разделяй и властвуй" мы будем разбивать коллекцию полуплоскостей Н на два непустых поднабора H1 и Н2 примерно одинакового размера, затем рекурсивно вычислять I(H1) и I(H2), после чего комбинировать их для получения I(Н1) П I(Н2). В конечном случае (n = 1) будем просто возвращать чистую полуплоскость из Н.
Возвратимся к реализации. Нам необходим способ представления границ выпуклых политопов, получаемых в процессе выполнения алгоритма, а также окончательного политопа I(H). К сожалению, для этого мы не можем использовать объекты класса Polygon, поскольку границы неограниченных выпуклых политопов не замкнуты. Но вместо определения нового класса мы будем отсекать I(H) по границам выпуклого ограничивающего прямоугольника В. Тем самым будет обеспечено, что каждый политоп, выполняемый по мере выполнения алгоритма, будет ограничен и определен как пересечение некоторого выпуклого политопа и ограничивающего прямоугольника В.
В программе halfplanelntersect мы будем представлять полуплоскость в виде объектов класса Edge и считать, что полуплоскость лежит справа. от ребра. Программе задается массив Н из n ребер и выпуклый ограничивающий прямоугольник box. Программа возвращает выпуклый полигон, равный пересечению прямоугольника box и п полуплоскостей в наборе Н. Реализация использует классы из раздела структуры геометрических данных.
Polygon *halfplanelntersect (Edge H[], int n, Polygon &box)
{
Polygon *c;
if (n == 1)
clipPolygonToEdge (box, H[0), c);
else {
int m = n / 2;
Polygon *a = halfplaneIntersect (H, m, box);
Polygon *b = halfplaneIntersect (H+m, n-m, box);
с = convexPolygonIntersect(*a, *b) ;
delete a;
delete b;
}
return c;
}
В программе используются две функции: Функция clipPolygonToEdge применяется для выделения части ограничивающего прямоугольника, лежащего справа от ребра (для каждой полуплоскости).
bool clipPolygonToEdge(Polygon &s, Edge &e, Polygon* &result)
{
Polygon *p = new Polygon;
Point crossingPt;
for (int i = 0; i < s.size(); s.advance(CLOCKWISE), i++} {
Point org = s.point();
Point dest = s.cw()->point();
int orgIsInside = (org.classify(e) != LEFT);
int destIsInside = (dest.classify(e) != LEFT);
if (orgIsInside != destIsInside) {
double t;
e.intersect(s.edge(), t);
crossingPt = e.point(t);
}
if (orgIsInside && destIsInside)
p->insert(dest);
else if (orgIsInside && !destIsInside) {
if (org != crossingPt)
p->insert(crossingPt);
}
else if (!orgIsInside && !destIsInside)
; // nothing is done
else {
p->insert(crossingPt);
if (dest != crossingPt)
p->insert(dest);
}
}
result = p;
return (p->size() > 0);
}
Функция convexPolygonIntersect формирует область пересечения для двух выпуклых полигонов.
Ограничивающий прямоугольник, который будет передаваться в программу halfplanelntersect, должен быть достаточно большим, чтобы не потерять нужную информацию. В идеале полуплоскости, образованные ребрами ограничивающего прямоугольника, являются лишними, так что решение, возвращаемое программой, равно I(H). Если это невозможно, т. е. когда пересечение I(H) безгранично, ограничивающий прямоугольник должен охватывать все вершины, принадлежащие I(H) и в этом случае будет отброшена только неинтересная часть I(H). Ответственность за установку подходящих границ ограничивающего прямоугольника возлагается на прикладную программу, которая вызывает функцию halfplaneIntersect.
Анализ
При размере входного массива, равном n, время работы Т(n) программы halfplanelntersect определяется рекуррентным выражением T(n) = 2T(n/2) + an, n>1.
Здесь элемент an соответствует времени, которое затрачивается функцией convexPolygonlntersect для формирования области пересечения двух выпуклых полигонов. Отсюда следует, что программа halfplanelntersect выполняется за время О(n log n).
Этот алгоритм оптимален.
8 8 8
| |
*
Обратная связь