stringtranslate.com

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

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

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

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

История

Антиподальная пара вершин и их опорные параллельные прямые .

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

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

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

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

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

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

GetAllAntiPodalPairs ( p [ 1..n ] ) i0 = n i = 1 j = i + 1 while ( Площадь ( i , i + 1 , j + 1 ) > Площадь ( i , i + 1 , j )) j = j + 1 j0 = j while ( i != j0 ) i = i + 1 yield i , j while ( Площадь ( i , i + 1 , j + 1 ) > Площадь ( i , i + 1 , j )) j = j + 1 if (( i , j ) != ( j0 , i0 )) yield i , j else return if ( Площадь ( j , i + 1 , j + 1 ) = Площадь ( i , i + 1 , j )) if (( i , j ) != ( j0 , i0 ) ) yield i , j + 1 else yield i + 1 , j

Приложения

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

Расстояния

Ограничительные рамки

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

Многополигональные операции

Обходы

Другие

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

Ссылки

  1. ^ "Вращающиеся суппорты" на домашней странице Туссэна
  2. ^ ab Шамос, Майкл (1978). «Вычислительная геометрия» (PDF) . Йельский университет. С. 76–81.
  3. ^ Туссен, Годфрид Т. (1983). «Решение геометрических задач с помощью вращающихся штангенциркулей». В Protonotarios, EN; Stassinopoulos, GI; Civalleri, PP (ред.). Труды MELECON '83, Средиземноморская электротехническая конференция, Афины, Греция, 24–26 мая 1983 г. IEEE. стр. A10.02/1–4. CiteSeerX 10.1.1.155.5671 . 
  4. ^ Шамос, Франко П. Препарата, Майкл Ян (1985). Вычислительная геометрия. Введение . Нью-Йорк, штат Нью-Йорк: Springer New York. ISBN 978-1-4612-7010-2.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
  5. ^ Пирзаде, Хормоз (1999). Вычислительная геометрия с вращающимися штангенциркулями (магистерская диссертация). Университет Макгилла.
  6. ↑ Бинай К. Бхаттачарья и Годфрид Т. Туссен, «Быстрые алгоритмы вычисления диаметра конечного плоского множества», The Visual Computer , т. 3, № 6, май 1988 г., стр. 379–388.
  7. ↑ Бинай К. Бхаттачарья и Годфрид Т. Туссен, «Контрпример к алгоритму диаметра для выпуклых многоугольников», Труды IEEE по анализу шаблонов и машинному интеллекту , том PAMI-4, № 3, май 1982 г., стр. 306–309.
  8. ↑ Майкл Э. Хоул и Годфрид Т. Туссен, «Вычисление ширины множества», IEEE Transactions on Pattern Analysis & Machine Intelligence , т. 10, № 5, сентябрь 1988 г., стр. 761–765.
  9. ^ Годфрид Т. Туссен и Джим А. МакАлеар, «Простой алгоритм O( n log n ) для нахождения максимального расстояния между двумя конечными плоскими множествами», Pattern Recognition Letters , том 1, 1982, стр. 21–24.
  10. ^ Бинай К. Бхаттачарья и Годфрид Т. Туссен, «Эффективные алгоритмы вычисления максимального расстояния между двумя конечными плоскими множествами», Журнал алгоритмов , т. 14, 1983, стр. 121–136.
  11. ↑ Годфрид Т. Туссен и Бинай К. Бхаттачарья, «Оптимальные алгоритмы для вычисления минимального расстояния между двумя конечными плоскими множествами», Pattern Recognition Letters , т. 2, декабрь 1983 г., стр. 79–82.
  12. ^ "Вращающиеся суппорты". 2015-03-30. Архивировано из оригинала 2015-03-30 . Получено 2017-03-22 .{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )
  13. ^ MARTINEZ, HUGO M. (1 января 1978 г.). "Обзор: "PATTERN SYNTHESIS", U. Grenander, Springer-Verlag, Нью-Йорк, 1976. 509 стр". International Journal of General Systems . 4 (2): 126–127. doi :10.1080/03081077808960672. ISSN  0308-1079.
  14. ^ Barequet и Wolfers (1998). «Оптимизация полосы, разделяющей два полигона». Графические модели и обработка изображений . 60 (3): 214–221. doi : 10.1006/gmip.1998.0470 .
  15. ^ Тейхманн, Марек (1989). Задачи оптимизации размещения клиньев (магистерская диссертация). Университет Макгилла.
  16. ^ Годфрид Т. Туссен, «Простой линейный алгоритм пересечения выпуклых многоугольников», The Visual Computer , том 1, 1985, стр. 118–123.
  17. ^ Томас Лосано-Перес, «Пространственное планирование: подход с использованием конфигурационного пространства», IEEE Transactions on Computers , том 32, № 2, 1983, стр. 108–120.
  18. ^ Бинай К. Бхаттачарья и Годфрид Т. Туссен, «Вычисление кратчайших трансверсалей», Computing , т. 46, 1991, стр. 93–119.
  19. ^ Бинай К. Бхаттачарья, Юрек Чижович, Питер Эгиед, Иван Стойменович, Годфрид Т. Туссен и Хорхе Уррутиа, «Вычисление кратчайших трансверсалей множеств», Международный журнал вычислительной геометрии и приложений , том 2, № 4, декабрь 1992 г., стр. 417–436.
  20. ↑ Жан-Марк Робер и Годфрид Т. Туссен, «Линейная аппроксимация простых объектов», Computational Geometry: Theory and Applications , Vol. 4, 1994, стр. 27–52.
  21. ^ Rasson и Granville (1996). «Геометрические инструменты в классификации». Computational Statistics & Data Analysis . 23 (1): 105–123. doi :10.1016/S0167-9473(96)00024-2.
  22. ^ Бозе, П.; Уртадо-Диас, Ф.; Оманья-Пулидо, Э.; Сноейинк, Дж.; Туссен, ГТ (2002-08-01). "Некоторые проблемы оптимизации угла апертуры". Algorithmica . 33 (4): 411–435. CiteSeerX 10.1.1.16.7118 . doi :10.1007/s00453-001-0112-9. ISSN  0178-4617. S2CID  27455160. 
  23. ^ «Неверные алгоритмы диаметра для выпуклых многоугольников».