Вращающиеся суппорты - Rotating calipers

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

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

Метод назван так потому, что идея аналогична вращению подпружиненного штангенциркуль вокруг снаружи выпуклый многоугольник.[1] Каждый раз, когда одно лезвие суппорта прилегает к краю многоугольника, оно образует антиподальная пара острием или краем, касающимся противоположного лезвия. Полный "поворот" штангенциркуля вокруг многоугольника обнаруживает все пары противоположных точек; множество всех пар, рассматриваемых как граф, образует бить. Метод поворота суппортов можно интерпретировать как проективный дуальный из алгоритм линии развертки в котором развертка проходит по склонам линий, а не по Икс- или у-координаты точек.

История

An антиподальная пара вершины и их поддерживающие параллельные линии.

Метод вращающихся штангенциркулей впервые был использован в диссертации Майкл Шамос в 1978 г.[2] Шамос использует этот метод для создания всех противоположный пары точек на выпуклый многоугольник и вычислить диаметр выпуклого многоугольника в время. Годфрид Туссен придумал фразу «вращающиеся штангенциркули», а также продемонстрировал, что этот метод применим для решения многих других задач вычислительной геометрии.[3]

Вращающиеся суппорты, нахождение моста между двумя выпуклыми многоугольниками

Алгоритм Шамоса

Шамос дал следующий алгоритм в своей диссертации (стр. 77–82) для метода вращающихся штангенциркулей, который генерирует все противоположные пары вершин на выпуклом многоугольнике:[2]

/ * p [] имеет стандартную форму, т. е. против часовой стрелки,      различные вершины, без коллинеарных вершин.   ANGLE (m, n) - это процедура, которая возвращает угол по часовой стрелке      выметается лучом при вращении из положения, параллельного      на направленный отрезок Pm, Pm + 1 в положение, параллельное Pn, Pn + 1   Мы предполагаем, что все индексы приведены к mod N (так что N + 1 = 1).*/GetAllAntiPodalPairs(п[1..п])    // Находим первую антиподальную пару, располагая вершину напротив P1    я = 1    j = 2    в то время как угол(я, j) < Пи        j++    Уступать я, j    / * Теперь обходим многоугольник с учетом         возможно параллельные края. Линия L проходит через         Pi, Pi + 1 и M проходит через Pj, Pj + 1    */    // Цикл по j, пока не будет просканирован весь P    текущий = я        в то время как j != п        если угол(текущий, я + 1) <= угол(текущий, j + 1)            j++            текущий = j        еще            я++            текущий = я        Уступать я, j        // Теперь займемся параллельными краями        если угол(текущий, я + 1) = угол(текущий, j + 1)            Уступать я + 1, j            Уступать я, j + 1            Уступать я + 1, j + 1            если текущий = я                j++            еще                я++

Другая версия этого алгоритма появилась в тексте Препараты и Шамоса в 1985 году, в которой не вычислялись углы:[4]

GetAllAntiPodalPairs(п[1..п])    i0 = п    я = 1    j = я + 1    в то время как (Площадь(я, я + 1, j + 1) > Площадь(я, я + 1, j))        j = j + 1        j0 = j    в то время как (j != i0)        я = я + 1        Уступать я, j        в то время как (Площадь(я, я + 1, j + 1) > Площадь(я, я + 1, j)            j = j + 1            если ((я, j) != (j0, i0))                Уступать я, j            еще                 вернуть        если (Площадь(j, я + 1, j + 1) = Площадь(я, я + 1, j))            если ((я, j) != (j0, i0))                Уступать я, j + 1            еще                 Уступать я + 1, j

Приложения

Пирзаде[5] описывает различные применения метода вращающихся штангенциркулей.

Расстояния

  • Диаметр (максимальная ширина) выпуклого многоугольника[6][7]
  • Ширина (минимальная ширина ) выпуклого многоугольника[8]
  • Максимальное расстояние между двумя выпуклыми многоугольниками[9][10]
  • Минимальное расстояние между двумя выпуклыми многоугольниками[11][12]
  • Самая широкая пустая (или разделяющая) полоса между двумя выпуклыми многоугольниками (упрощенный малоразмерный вариант задачи, возникающей в Машина опорных векторов на основе машинного обучения)
  • Расстояние Гренандера между двумя выпуклыми многоугольниками[13]
  • Оптимальное разделение полос (используется в медицинской визуализации и твердотельном моделировании)[14]

Ограничивающие рамки

Триангуляции

Операции с несколькими полигонами

  • Объединение двух выпуклых многоугольников
  • Общие касательные к двум выпуклым многоугольникам
  • Пересечение двух выпуклых многоугольников[16]
  • Критические линии поддержки двух выпуклых многоугольников
  • Векторные суммы (или сумма Минковского) двух выпуклых многоугольников[17]
  • Выпуклая оболочка двух выпуклых многоугольников

Обходы

  • Кратчайшие трансверсали[18][19]
  • Самая тонкая полоска поперечины[20]

Другие

  • Непараметрические решающие правила для классификации с машинным обучением[21]
  • Оптимизация угла апертуры для решения проблем с видимостью в компьютерном зрении[22]
  • Поиск самых длинных клеток в миллионах биологических клеток[23]
  • Сравнение точности стрельбы двух человек на дальности
  • Классифицируйте участки мозга по сканированным изображениям

Смотрите также

использованная литература

  1. ^ «Вращающийся суппорт» на домашней странице Туссена
  2. ^ а б Шамос, Майкл (1978). «Вычислительная геометрия» (PDF). Йельский университет. С. 76–81.
  3. ^ Туссен, Годфрид Т. (1983). «Решение геометрических задач с вращающимися суппортами». Proc. MELECON '83, Афины. CiteSeerX  10.1.1.155.5671. Цитировать журнал требует | журнал = (Помогите)
  4. ^ Шамос, Франко П. Препарата, Майкл Ян (1985). Вычислительная геометрия Введение. Нью-Йорк, Нью-Йорк: Springer New York. ISBN  978-1-4612-7010-2.
  5. ^ Пирзаде, Хормоз (1999). «Расчетная геометрия с вращающимися суппортами». Библиотека Макгилла.
  6. ^ Бинай К. Бхаттачарья и Годфрид Т. Туссен, «Быстрые алгоритмы для вычисления диаметра конечного плоского множества», Визуальный компьютер, Vol. 3, № 6, май 1988 г., стр. 379–388.
  7. ^ Бинай К. Бхаттачарья и Годфрид Т. Туссен, «Противоположный пример алгоритму диаметра для выпуклых многоугольников». IEEE Transactions по анализу шаблонов и машинному анализу, Vol. ПАМИ-4, № 3, май 1982 г., стр. 306–309.
  8. ^ Майкл Э. Хоул и Годфрид Т. Туссен, «Вычисление ширины множества», Транзакции IEEE по анализу шаблонов и машинному анализу, Vol. 10, вып. 5, сентябрь 1988 г., стр. 761–765.
  9. ^ Годфрид Т. Туссен и Джим А. МакАлир, "Простой O (п журнал п) алгоритм нахождения максимального расстояния между двумя конечными плоскими множествами », Письма с распознаванием образов, Vol. 1, 1982, стр. 21–24.
  10. ^ Бинай К. Бхаттачарья и Годфрид Т. Туссен, «Эффективные алгоритмы для вычисления максимального расстояния между двумя конечными плоскими множествами». Журнал алгоритмов, т. 14, 1983, стр. 121–136.
  11. ^ Годфрид Т. Туссен и Бинай К. Бхаттачарья, «Оптимальные алгоритмы для вычисления минимального расстояния между двумя конечными плоскими множествами», Письма с распознаванием образов, т. 2, декабрь 1983 г., стр. 79–82.
  12. ^ «Вращающийся суппорт». 2015-03-30. Архивировано 30 марта 2015 года.. Получено 2017-03-22.CS1 maint: BOT: статус исходного URL-адреса неизвестен (ссылка на сайт)
  13. ^ МАРТИНЕС, УГО М. (1 января 1978 г.). "Обзор:" СИНТЕЗ ОБРАЗЦА ", У. Гренандер, Springer-Verlag, Нью-Йорк, 1976. 509 с." Международный журнал общих систем. 4 (2): 126–127. Дои:10.1080/03081077808960672. ISSN  0308-1079.
  14. ^ Барекет и Вольферс (1998). «Оптимизация полосы, разделяющей два многоугольника». Графические модели и обработка изображений. 60 (3): 214–221. Дои:10.1006 / gmip.1998.0470.
  15. ^ Тайхманн, Марек (1989). «Проблемы оптимизации размещения клина». Цитировать журнал требует | журнал = (Помогите)
  16. ^ Годфрид Т. Туссен, "Простой линейный алгоритм пересечения выпуклых многоугольников", Визуальный компьютер, Vol. 1. 1985. С. 118–123.
  17. ^ Томас Лозано-Перес, "Пространственное планирование: подход к пространству конфигурации", Транзакции IEEE на компьютерах, Vol. 32, № 2, 1983, стр. 108–120.
  18. ^ Бинай К. Бхаттачарья и Годфрид Т. Туссен, «Вычисление кратчайших трансверсалей». Вычисление, т. 46, 1991, стр. 93–119.
  19. ^ Бинай К. Бхаттачарья, Юрек Чизович, Питер Эгид, Иван Стойменович, Годфрид Т. Туссен и Хорье Уррутиа, «Вычисление кратчайших трансверсалей множеств». Международный журнал вычислительной геометрии и приложений, Vol. 2, № 4, декабрь 1992 г., стр. 417–436.
  20. ^ Жан-Марк Робер и Годфрид Т. Туссен, «Линейное приближение простых объектов». Вычислительная геометрия: теория и приложения, Vol. 4, 1994, стр. 27–52.
  21. ^ Рассон и Гранвиль (1996). «Геометрические инструменты в классификации». Вычислительная статистика и анализ данных. 23 (1): 105–123. Дои:10.1016 / S0167-9473 (96) 00024-2.
  22. ^ Bose, P .; Hurtado-Diaz, F .; Omaña-Pulido, E .; Snoeyink, J .; Туссен, Г. Т. (1 августа 2002 г.). «Некоторые проблемы апертурно-угловой оптимизации». Алгоритмика. 33 (4): 411–435. CiteSeerX  10.1.1.16.7118. Дои:10.1007 / s00453-001-0112-9. ISSN  0178-4617.
  23. ^ «Алгоритмы неправильного диаметра для выпуклых многоугольников».