Изменения

<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> принаджлежит нижней огибающей, то все остальные прямые лежат сверху. Короче даПусть полуплоскости заданы уравнениями прямых и ориентацией, одно и то же..с какой стороны от прямой лежит полуплоскость.

Если в конвекс-халле мы идем слева направо по увеличению иксаСначала рассмотрим все полуплоскости, которые "смотрят", то тут то же самое будетесть ориентированны, вниз. Аналогично можно рассмотреть все полуплоскости, если мы пойдем справа налево по увеличению угла наклонакоторые ориентированны вверх.

Полностью считать пересечние можно по отдельности {{Лемма|statement=[[Файл:halfSpaces.png|400px|thumb|right|Нужна ли полуплоскость <tex> l'' </tex>?]]Предикат проверки (верхняя + нижняя огибающаясм. рисунок)того, а можно что прямая <tex> l'' : A''x + B''y + C'' = 0 </tex> лежит над пересечением прямых <tex> l : Ax + By + C = 0 </tex> и сразу все<tex> l' : A'x + B'y + C' = 0 </tex> равен знаку определителя <tex>\begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix}</tex>. |proof=Для проверки предиката нужно определить знак выражения <tex> A''x_0 + B''y_0 + C'' </tex>, где <tex> (x_0, как полный конвексy_0) </tex> {{---}} точка пересечения прямых <tex> l' </tex> и <tex> l </tex>. Эта точка находится из уравнения <tex> \begin{pmatrix} A & B\\ A' & B' \end{pmatrix}\begin{pmatrix} x_0\\ y_0 \end{pmatrix} =\begin{pmatrix} -C\\ -C' \end{pmatrix}</tex>. Решением будет <tex>\begin{pmatrix} x_0\\ y_0 \end{pmatrix} =\frac{\begin{pmatrix} B' & -B\\ -A' & A \end{pmatrix}\begin{pmatrix} -C\\ -халлC' \end{pmatrix}}{ \begin{vmatrix} A & B\\ A' & B'\end{vmatrix}}</tex>. Подставим это решение в <tex> A''x_0 + B''y_0 + C'' </tex> и домножим на определитель.

Тут бы и закончить конспект, но стоит уточнить, что у пересечения полуплоскостей есть одна небольшая особенность {{<tex>A'' \left<(B'; -B);(-C; -}} оно может быть пусто, тогда как выпуклая оболочка вполне себе всегда определена, и это надо учитывать. И еще. когда мы рассматриваем верхнююC')\right> + B'' \left<(нижнюю-A'; A) огибающую, мы рассматриваем все прямые кроме вертикальных. Еще прямые близкие к вертикальным, но имеющие разный наклон ;(-C; -C')\right> + C'' \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} =</ и \) are mapped to very different points. Отсюда выходит то, почему конвекс-халл состоит из двух таких разных и одинаковых частей.tex>

Convex Hulls and Half<tex>= A'' \begin{vmatrix} B' & B \\ -C' & -C \end{vmatrix} -Space IntersectionB'' \begin{vmatrix} A' & A \\ -C' & -C \end{vmatrix} - C'' \begin{vmatrix} A' & A \\ B' & B \end{vmatrix} In 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 UH(P), which consists of the convex hull edges that have P below their supporting line—see the 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. (We assume for simplicity that no two points have the same x= \begin{vmatrix} A'' & A' & A \\ B'' & B' & B \\ -coordinate)C'' & -C' & -C \end{vmatrix} =</tex><tex>= \begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \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 allother 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 Таким образом, если представить прямую <tex> Ax + By + C = 0 </tex> как точку с однородными координатами <tex> (A(P ∗ , B, C)</tex>, this means that p ∗ contributes an edge to the unique bottom cell of the arrangement. This cell is the intersection of the halfто этот предикат {{-planes bounded by a line in P ∗ and lying below that line. The boundary of the bottom cell is an x-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 x-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 x-coordinate of p}} всего лишь поворот, it follows that the leftа проверка предиката {{-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}} проверка очередной точки в [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обходе Грэхема]] для нахождения выпуклой оболочки.

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Алгоритм:q. In the dual plane, this means that all lines r ∗ , with r ∈ P \ {p, q}* Отсортировать все полуплоскости по углу наклона;* Запустить обход Грэхема для полуплоскостей, 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 half-planes—half-planes bounded from above by a non-vertical line—can be computed by computing an upper convex hull, and that the intersection of upper half-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 half-planes? Of course, we can split the set H into a set H + of upper half-planes and a set H − of lower half-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 convex;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смотрящих вверх;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От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, а ограниченная {{---}} когда обе цепочки не пусты и пересекаются. == Связь пересечения полуплоскостей с выпуклой оболочкой == {{Лемма |id=1|statement= Пересечение полуплоскостей может быть получено построением выпуклой оболочки в [[двойственное пространство|двойственном прострастве]] для множества точек, являющихся дуальным преобразованием исходных полуплоскостей|proof= [[Файл:DualSpaceCH.png ‎ |400px|thumb|right| Множество точек в двойственном пространстве]][[Файл:DualSpaceCH400.png |400px|thumb|right| Множество прямых в исходном пространстве]] '''Важно:''' Покажем конструктивный алгоритм для множестве полуплоскостей, не содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, позволяющие снять данное ограничение. '''Важно:''' В картинке перепутаны <tex>P</tex> и <tex>P^\star</tex>. TODO  Рассмотрим планарный случай и предположим, что вертикальные и параллельные прямые отсутствуют (в конце приведем два способа решения данной проблемы). However Пусть у нас есть множество ориентированных прямых, to apply this duality to a given set of half-planesкаждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <tex> P(p_x, we need a point in the intersection of the halfp_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>, где <tex>p</tex> - точка в исходном пространстве, there cannot be any general duality that turns the intersection of a set of half<tex>l</tex> -planes into a convex hullпрямая в исходном пространстве, <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>. Посмотрим на планарный граф множества(рис.2) прямых.” Из факта выше, мы можем понять, что <tex>p</tex> внесла ребро в самый нижний фейс(This problem is nicely solved if one works in oriented projective spaceименно тот, который задаёт часть пересечения полуплоскостей). Обозначим цепочку данного фейса, 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Количество точек в массиве одинаковое, an algorithm to compute the intersection of halfпри это каждая точка из <tex>\mathcal{UH}</tex> внесла вклад в <tex>\mathcal{LE}</tex>) Напоследок, cоседние точки <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