Изменения

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div><includeonly>[[КатегорияФайл: В разработкеsamplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограниченно или пусто]]</includeonly>

[[Файл== Предикат трех прямых ==Задача:dualесть конечное множество полуплоскостей, найти фигуру их пересечения или сообщить что оно пусто.png|400px|thumb|right|типа это одно и то же]]

Короче говоряДля начала заметим, верхний(нижний) конвекс-халл для множества точекчто если пересечение не пусто, то же самое, что и нижняя(верхняя) огибающая(англоно выпукло. lower(upperДоказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскость выпукла) envelope) для множества прямых.

Если рассмотреть что ребро <tex> PQ </tex> принадлежит верхнему конвекс-халлу это означает, что все остальные точки лежат снизу. А если ребро <tex> PQ </tex> принаджлежит нижней огибающей, то все остальные прямые лежат сверху. Короче даПусть полуплоскости заданы уравнениями прямых и ориентацией, одно и то же..с какой стороны от прямой лежит полуплоскость.

Convex Hulls and Half<tex>A'' \left<(B'; -Space IntersectionIn Chapter 8 we have met the concept of duality. The strenth of duality lies in that it allows us to look at a problem from a new perspective, which can lead to more insight in what is really going on. Recall that we denote the line that is the dual of a point p by p ∗ , and the point that is the dual of a line by ∗ . The duality transform is incidence and order preserving: p ∈ if and only if ∗ ∈ p ∗ , and p lies above if and only if ∗ lies above p ∗ . Let’s have a closer look at what convex hulls correspond to in dual space. We will do this for the planar case. Let P be a set of points in the plane. For technical reasons we focus on its upper convex hull, denoted UHB);(P-C; -C'), which consists of the convex hull edges that have P below their supporting line—see the \right> + B'' \left side of Figure 11.4. The upper convex hull is a polygonal chain that connects the leftmost point in P to the rightmost one. <(-A'; A);(We assume for simplicity that no two points have the same x-coordinateC; -C')\right> + C'' \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} =</tex>

When does a point p ∈ P appear as a vertex of the upper convex hull? That is the case if and only if there is a non-vertical line through p such that all<tex>other points of P lie below . In the dual plane this statement translates to the following condition: there is a point ∗ on the line p ∗ ∈ P ∗ such that ∗ lies below all other lines of P ∗ . If we look at the arrangement = A(P ∗ ), this means that p ∗ contributes an edge to the unique bottom cell of the arrangement. This cell is the intersection of the half'' \begin{vmatrix} B' & B \\ -planes bounded by a line in P ∗ and lying below that line. The boundary of the bottom cell is an xC' & -monotone chain. We can define this chain as the minimum of the linear functions whose graphs are the lines in P ∗ . For this reason, the boundary of the bottom cell in an arrangement is often called the lower envelope of the set of lines. We denote the lower envelope of P ∗ by LE(P ∗ )—see the right hand side of Figure 11.4. The points in P that appear on UH(P) do so in order of increasing xC \end{vmatrix} -coordinate. The lines of P ∗ appear on the boundary of the bottom cell in order of decreasing slope. Since the slope of the line p ∗ is equal to the xB'' \begin{vmatrix} A' & A \\ -coordinate of p, it follows that the leftC' & -to-right list of points on UH(P) corresponds exactly to the right-to-left list of edges of LE(P ∗ ). So the upper convex hull of a set of points is essentially the same as the lower envelope of a set of lines.C \end{vmatrix} + C'' \begin{vmatrix} A & A' \\ B & B' \end{vmatrix} =</tex>

Let’s do one final check. Two points p and q in P form an upper convex hull edge if and only if all other points in P lie below the line through p and<tex>q. In the dual plane, this means that all lines r ∗ , with r ∈ P = A'' \ begin{p, qvmatrix}, lie above the intersection point ∗ of p ∗ and q ∗ . This is exactly the condition under which p ∗ ∩ q ∗ is a vertex of LE(P ∗ ). What about the lower convex hull of P and the upper envelope of P ∗ ? (We leave the precise definitions to the reader.) By symmetry, these concepts are dual to each other as well. We now know that the intersection of lower halfB' & B \\ -planes—halfC' & -planes bounded from above by a nonC \end{vmatrix} -vertical line—can be computed by computing an upper convex hull, and that the intersection of upper halfB'' \begin{vmatrix} A' & A \\ -C' & -planes can be computed by computing a lower convex hull. But what if we want to compute the intersection of an arbitrary set H of halfC \end{vmatrix} - C'' \begin{vmatrix} A' & A \\ B' & B \end{vmatrix} = \begin{vmatrix} A'' & A' & A \\ B'' & B' & B \\ -planes? Of course, we can split the set H into a set H + of upper halfC'' & -planes and a set H − of lower halfC' & -planes, compute H + by computing the lower convex hull of H + ∗ and H − by computing the upper convex hull of H − ∗ , and then compute H by intersecting H + and H − . But is this really necessary? If lower envelopes correspond to upper convexC \end{vmatrix} =</tex><tex>hulls, and upper envelopes correspond to lower convex hulls, shouldn’t then the intersection of arbitrary half-planes correspond to full convex hulls? In a= \begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix} </tex>sense, this is true. The problem is that our duality transformation cannot handle vertical lines, and lines that are close to vertical but have opposite slope are mapped to very different points. This explains why the dual of the convex hull consists of two parts that lie rather far apart.}}

It is possible to define a different duality transformation that allows vertical linesТаким образом, если представить прямую <tex> Ax + By + C = 0 </tex> как точку с однородными координатами <tex> (A, B, C) </tex>, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} проверка очередной точки в [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обходе Грэхема]] для нахождения выпуклой оболочки. Алгоритм:* Отсортировать все полуплоскости по углу наклона;* Запустить обход Грэхема для полуплоскостей, смотрящих вниз (с предикатом-определителем);* Запустить обход Грэхема для полуплоскостей, смотрящих вверх;* Пересечь две цепочки. However От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, to apply this duality to a given set of halfа ограниченная {{-planes--}} когда обе цепочки не пусты и пересекаются. == Связь пересечения полуплоскостей с выпуклой оболочкой == {{Лемма |id=1|statement= Пересечение полуплоскостей может быть получено построением выпуклой оболочки в [[двойственное пространство|двойственном прострастве]] для множества точек, являющихся дуальным преобразованием исходных полуплоскостей|proof= [[Файл:DualSpaceCH.png ‎ |400px|thumb|right| Множество точек в двойственном пространстве]][[Файл:DualSpaceCH400.png |400px|thumb|right| Множество прямых в исходном пространстве]] '''Важно:''' Покажем конструктивный алгоритм для множестве полуплоскостей, не содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, позволяющие снять данное ограничение. '''Важно:''' В картинке перепутаны <tex>P</tex> и <tex>P^\star</tex>. TODO  Рассмотрим планарный случай и предположим, что вертикальные и параллельные прямые отсутствуют (в конце приведем два способа решения данной проблемы). Пусть у нас есть множество ориентированных прямых, we need a point in the intersection of the halfкаждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <tex> P(p_x, p_y) \Rightarrow P^\star (p_x x -planesp_y)</tex>. But that was to be expected Далее воспользуемся основными свойствами дуальной трансформации (см. As long as we do not want to leave the Euclidean planeдоказательтсво в конспекте о [[двойственное пространство|двойственном прострастве]]):#<tex>p</tex> <tex>\in</tex> <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> <tex>\in</tex> <tex>p^\star</tex>, there cannot be any general duality that turns the intersection of a set of halfгде <tex>p</tex> -planes into a convex hullточка в исходном пространстве, <tex>l</tex> - прямая в исходном пространстве, <tex>l^\star</tex>, because the intersection of half<tex>p^\star</tex> -planes can have one special propertyих дуальное отображение.#<tex>p</tex> лежит "над" <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> лежит "над" <tex>p^\star</tex>  '''Важно 2: it can be empty''' * <tex>p^\star</tex> - точка в двойственном пространстве, <tex>p</tex> - линия в исходном,* <tex>l^\star</tex> - прямая в двойственном пространстве, <tex>l</tex> - точка в исходном,* Значок <tex>*</tex> означает, что элемент из двойственного пространства.Рассмотрим множество точек(<tex>P^\star</tex>) в двойственном пространстве и рассмотрим верхнюю часть выпуклой оболочки, построенной на этих точках. Обозначим её за <tex>\mathcal{UH}</tex>(Upper hull). Далее мы будем работать только с прямыми(в исходном пространстве), у которых вектор нормали направлен вниз, т.е они образовывают верхнюю цепочку. What could that possibly correspond to По свойству выпуклой оболочки, любое ребро из цепи <tex>\mathcal{UH}</tex> содержит "ниже" себя все точки множества <tex>P^\star</tex>, а так же эта цепь соединяет самую правую точку с самой левой. Рассмотрим какую-то точку <tex>p^\star \in the dual? The convex hull of a set of points P^\star</tex> и заметим, что она будет принадлежать цепи <tex>\mathcal{UH}</tex> <tex>\Leftrightarrow</tex> <tex>\exists</tex> прямая <tex>l^\star </tex> : <tex>p^\star \in Euclidean space is always well definedl^\star</tex> и все точки из <tex>P^\star</tex> лежат ниже <tex>l^\star</tex> (сейчаc мы жили в двойственном пространстве). В обычном пространстве данный факт эквивалентен следующему: *Дуальное отображение точки <tex>p^\star</tex> в базовое пространство {{---}} прямая <tex>p</tex>, которая по ''первому свойству'' содержит точку <tex>l</tex>(в базовом пространстве прямая <tex>p^\star</tex> перешла в точку <tex>p</tex>).*Так как прямая <tex>l^\star</tex> лежит выше всех точек, то теперь каждая прямая из <tex>P</tex> лежит выше точки <tex>l</tex> (по свойству 2). Итого: there is no such thing as “emptinessу нас есть точка <tex>l</tex> на прямой <tex>p</tex>, лежащая ниже всех остальных прямых из <tex>P</tex>.”  Посмотрим на планарный граф множества(This problem is nicely solved if one works in oriented projective spaceрис.2) прямых. Из факта выше, мы можем понять, что <tex>p</tex> внесла ребро в самый нижний фейс(именно тот, который задаёт часть пересечения полуплоскостей). Обозначим цепочку данного фейса, but this concept is beyond the scope of this bookкак <tex>\mathcal{LE}</tex>.Математически данную цепочку мы можем описать, как минимум из всех линейных функция (заданные прямыми) Only once you know that the intersection is not emptyв <tex>P</tex>. Так же <tex>X</tex> компонента узлов этой цепочки монотонно возрастает. Вернемся к <tex>\mathcal{UH}</tex> и заметим, and a point in the interior is knownчто при обходе цепи, can you define a duality that relates the intersection with a convex hullкоордината <tex>X</tex> точек растет. We leave it at this for nowЕсли же мы будет обходить цепочку из <tex>P</tex>, образующую пересечение полуплоскостей, мы заметим, что наклон прямых уменьшается. The important thing is that—although there are technical complications—convex hulls and intersections of half-planes Учитывая этот факт, и то что наклон линии из <tex>\mathcal{LE}</tex> совпадет с <tex>X</tex> координатой точки (or half-spaces in three dimensionsвспоминаем отображение и применяем производную) are essentially dual concepts, можно сделать вывод, что обход слева направо точек из цепи <tex>\mathcal{UH}</tex>, совпадает с обходом точек из <tex>\mathcal{LE}</tex> справа налево.  (Обе линии монотоны, одна возрастает, другая убывает. HenceКоличество точек в массиве одинаковое, при это каждая точка из <tex>\mathcal{UH}</tex> внесла вклад в <tex>\mathcal{LE}</tex>) Напоследок, an algorithm to compute the intersection of halfcоседние точки <tex>p^\star</tex> и <tex>q^\star</tex> из <tex>P^\star</tex> образуют какое-planes то или принадлежат какому-то ребру <tex>\mathcal{UH}</tex> <tex>\Leftrightarrow</tex> все точки из <tex>P^\star</tex> лежат "ниже" линии, построенной на точках <tex>p^\star</tex> и <tex>q^\star</tex>. В исходном пространстве это означает: все прямые из пространства <tex>P</tex> за исключением прямых <tex>p</tex> и <tex>q</tex> лежат над пересечением <tex>p</tex> и <tex>q</tex>. Это достаточное условие, что пересечение <tex>p</tex> и <tex>q</tex> <tex>\in the plane </tex> <tex>\mathcal{LE}</tex>. Таким образом мы построили верхнее пересечение полуплоскостей. Аналогичным образом строится нижнее, затем мы пересекаем полученные две цепочки.}}Что же делать с вертикальными линиями?# Найдем все вертикальным прямые за <tex>O(or half-spaces in three dimensionsN) can be given by dualizing a convex-hull algorithm</tex>. Возьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Построим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, самую правую и самую левую вертикальную прямую.# Перейдем в однородное двойственное пространство.

* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 15 11 page 253-254