418
правок
Изменения
м
== Вращающиеся калиперы ==
{|border=0 width="100%"|{{Теорема
|[[Файл:perpendicular.png|250px|thumb|right]]
|}
{| border="0" width="100%"|{{Теорема
|[[Файл:max_parallel.png|170px|thumb|right]]|}
{[[Файл:calipers.png|border="0" width="100%"250px|right]] |Рассмотрим рисунок справа. <tex>L</tex> и <tex>M</tex> {{---}} опорные прямые, проходящие через вершины <tex>A</tex> и <tex>D</tex> соответственно. Значит, <tex>\langle A,D \rangle</tex> {{---}} противолежащая пара точек. Если начать вращать прямые против часовой стрелки вокруг данных точек, они будут оставаться опорными прямыми, пока одна из прямых не станет накладываться на сторону многоугольника. В нашем примере, при вращении <tex>M</tex> к позиции <tex>M'</tex>, <tex>M</tex> коснётся точки <tex>E</tex> раньше, чем <tex>L</tex> коснётся <tex>B</tex>, поэтому <tex>\langle A,E \rangle</tex> становится новой парой противолежащих точек.
|[[Файл:calipers.png|250px|thumb|right]] |}
== Ссылки ==
* ''M.I. Shamos'' Computational geometry, 1978 {{---}} С. 76.
* ''Яглом И.М., Болтянский В.Г.'' Выпуклые фигуры, 1951 {{---}} С. 20, 144.
* [https://github.com/Megabyte777/cg/blob/master/include/cg/operations/diameter.h Реализация - Github.com]
[[Категория: Вычислительная геометрия]]
Нет описания правки
Пусть <tex>P = (p_1, p_2, ... ,p_n)</tex> {{---}} выпуклый многоугольник, в котором порядок обхода вершин направлен против часовой стрелки, и никакие три последовательные точки не лежат на одной прямой. Найти пару чисел <tex>\langle i, j \rangle</tex>, такие, что <tex>d(p_i, p_j)</tex> максимально.
=== Опорные прямые ===
{{Определение
Прямая <tex>L</tex> называется '''опорной прямой''' (англ. ''line of support'') для многоугольника <tex>P</tex>, если его внутренность лежит по одну сторону от <tex>L</tex>, при этом <tex>L</tex> проходит хотя бы через одну из вершин <tex>P</tex>.
}}
|statement=
Пусть <tex>L_1</tex> и <tex>L_2</tex> {{---}} две параллельные опорные прямые фигуры <tex>\Phi</tex>, расстояние между которыми имеет максимальное значение. <tex>A_1</tex> и <tex>A_2</tex> {{---}} граничные точки фигуры <tex>\Phi</tex>, принадлежащие соответственно прямым <tex>L_1</tex> и <tex>L_2</tex>. Тогда отрезок <tex>A_1A_2</tex> перпендикулярен обеим прямым <tex>L_1</tex> и <tex>L_2</tex>.
|proof=
[[Файл:perpendicular.png|250px|right]]
Предположим, что это не так. Тогда расстояние между прямыми <tex>L_1</tex> и <tex>L_2</tex> было бы меньше, чем отрезок <tex>A_1A_2</tex>, и тем более меньше, чем расстояние между двумя опорными прямыми <tex>L'_1</tex> и <tex>L'_2</tex> фигуры <tex>\Phi</tex>, перпендикулярными к отрезку <tex>A_1A_2</tex>, что противоречит условию.
}}
Так как <tex>A_1</tex> и <tex>A_2</tex> {{---}} какие угодно граничные точки фигуры <tex>\Phi</tex>, принадлежащие соответственно прямым <tex>L_1</tex> и <tex>L_2</tex>, то из перпендикулярности отрезка <tex>A_1A_2</tex> к прямым <tex>L_1</tex> и <tex>L_2</tex> следует, что ни одна из прямых <tex>L_1</tex>, <tex>L_2</tex> не может иметь с фигурой <tex>\Phi</tex> целый общий отрезок. Другими словами, каждая из этих прямых содержит единственную граничную точку фигуры <tex>\Phi</tex>.
|statement=
Диаметр выпуклого многоугольника равен максимальному расстоянию между параллельными опорными прямыми.
|proof=
[[Файл:max_parallel.png|170px|right]]
Пусть <tex>\Phi</tex> {{---}} выпуклая фигура, <tex>L_1</tex> и <tex>L_2</tex> {{---}} параллельные опорные прямые, расстояние между которыми имеет наибольшее возможное значение <tex>d</tex>, <tex>A_1</tex> и <tex>A_2</tex> {{---}} общие точки фигуры <tex>\Phi</tex> и прямых <tex>L_1</tex> и <tex>L_2</tex> соответственно. По предыдущей теореме <tex>A_1A_2</tex> перпендикулярен к прямым <tex>L_1</tex>, <tex>L_2</tex>, следовательно, его длина равна <tex>d</tex>. Докажем, что расстояние между любыми двумя точками фигуры <tex>\Phi</tex> не преводходит <tex>d</tex>. Действительно, если <tex>B</tex> и <tex>C</tex> {{---}} какие-либо две точки фигуры <tex>\Phi</tex>, а <tex>m</tex> и <tex>n</tex> {{---}} опорные прямые, перпендикулярные к отрезку <tex>BC</tex>, то отрезок <tex>BC</tex> не превосходит расстояния между прямыми <tex>m</tex> и <tex>n</tex>, которое в свою очередь не превосходит <tex>d</tex>. Следовательно, длина <tex>BC</tex> не может быть больше <tex>d</tex>.
}}
=== Алгоритм ===
Заметим, что параллельные опорные прямые можно провести не через любую пару точек.
Благодаря предыдущей теореме нам нужно рассмотреть только противолежащие точки. Задача в том, чтобы рассмотреть их, не перебирая все пары точек.
Теперь <tex>M'</tex> будет вращаться вокруг <tex>E</tex>, а <tex>L'</tex> продолжит вращаться вокруг <tex>A</tex>, и следующей парой противолежащих точек станет <tex>\langle B,E \rangle</tex>. Продолжая таким образом, мы сгенерируем все пары противолежащих точек, так как параллельные линии пройдут под всеми возможными углами. Определение новой пары противолежащих точек требует только одного сравнения углов, которое можно выполнить с помощью предиката поворота.
=== Асимптотика ===
{{Теорема
Данный алгоритм можно реализовать следующим образом: хранить указатели на противолежащие вершины, и на каждой итерации алгоритма увеличивать либо один из данных указателей, либо сразу оба (когда обе прямые проходят через сторону многоугольника), и заканчивать работу, когда опорные прямые сделают полный круг. Таким образом, каждая из вершин будет посещена каждой из прямых не более двух раз.
}}
