Расчет центроида сферического многоугольника

11

Я хотел бы общий способ расчета центроидов для полигонов на сфере.

Пока что лучшая онлайн-справка:

Инструменты для графики и фигур Джефф Дженнесс.

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

Я знаю, что существует несколько способов определения центроида сферического многоугольника, но я ищу что-то аналогичное следующим определениям для точек и полилиний:

  • Точки : среднее арифметическое декартовых векторов, представляющих точки.
  • Полилинии : средневзвешенное значение декартовых векторов, представляющих средние точки каждого отрезка, взвешенное по (сферической) длине каждого отрезка.

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

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

Связанный: Как найти центр геометрии объекта?

Джейсон Дэвис
источник

Ответы:

9

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

Один из способов сделать это очевидным - рассмотреть довольно экстремальный треугольник, такой как почти половина полушария. Например, начиная с (lon, lat) = (-179, 0), бегите вдоль экватора к (0, 0), затем до северного полюса в (0, 90), а затем возвращайтесь к началу в (- 179,0). Это треугольник 90-179-90, включающий большую часть северной половины западного полушария. Проблема заключается в том, что его конечные точки (показанные на рисунке белыми точками) лежат практически в плоскости: одна находится на полюсе, а две другие находятся почти на противоположных сторонах от нее. Таким образом, их среднее значение, спроецированное обратно на сферу (красная точка), почти на полюсе - но это примерно так далеко от любого разумного центра, который можно получить:

Большой сферический треугольник

В качестве другого примера, давайте триангулируем полигон, представляющий верхнюю полусферу относительно ее центра, Северного полюса. Мы всегда будем делить Западное полушарие на две равные половины, каждая из которых представляет собой треугольник 90-90-90 (таким образом избегая любых проблем с огромными, охватывающими полушарие треугольниками). Восточное полушарие, однако, будет разделено на n равных полулун. Вершины луны k ( k = 1, 2, ..., n ) имеют координаты (lon, lat)

((k-1) * 180/n, 0),  (k * 180/n, 0),  (k * 180/n, 90).

Луны для k = 8

На этом рисунке показана установка для k = 8. Красные точки - это «треугольники» отдельных треугольников, рассчитанные в соответствии с документом «Инструменты для графики и фигур», стр. 65-67.

Делая вычисления, я нахожу, что при k = 2, взвешенный по площади центр действительно находится на Северном полюсе (как указывалось бы из соображений симметрии), но с увеличением n результат быстро смещается в западное полушарие и, в предел, приближается к широте 89,556 градусов по долготе -90 градусов. Это примерно в 50 километрах к югу от самого Северного полюса.

Следует признать, что погрешность +/- 50 км для многоугольника, охватывающего 20 000 км, невелика; общее количество произвольных вариаций из-за разных триангуляций в этом случае составляет всего 0,5%. Очевидно, что относительные ошибки могут быть сделаны сколь угодно большими путем включения отрицательных треугольников (просто сложите и вычтите некоторые действительно большие треугольники относительно маленького треугольника). Независимо от этого, любой, кто собирается делать сферические вычисления, очевидно, пытается избежать ошибок проецирования, поэтому он ищет высокую точность. Этот метод триангуляции не может быть рекомендован.

Whuber
источник
Вы продемонстрировали, что ошибки могут накапливаться при больших n, но не ясно, что подход обязательно ошибочен. Какое значение n вы использовали для достижения предельного значения?
Джейсон Дэвис
Также большое спасибо за то, что сделали расчеты и посмотрели на это всесторонне. Я просто хочу немного больше разъяснений, прежде чем смогу решить проблему. :)
Джейсон Дэвис
Джейсон, я добавил предварительный пример, чтобы дать тебе некоторую интуицию. Сам предел быстро приближается; несколько десятков лун получат несколько значащих цифр. Но новый пример должен уложить любые давние сомнения в том, что эта взвешенная триангуляция делает что-то разумное - за исключением маленьких треугольников, где вам гораздо лучше выполнять вычисления в проецируемых координатах в первую очередь. Единственная причина для сферических вычислений - это когда область анализа действительно глобальна, потому что тогда все прогнозы вносят много искажений.
whuber
1
Фантастика, спасибо. Так что, если я правильно понимаю, простое усреднение декартовых векторов не приведет к разумному центроиду для сферического треугольника (особенно больших, как ваш первый пример). Я исследую лучшие методы, например, нахождение пересечения медиан большого круга.
Джейсон Дэвис
Кстати, я все еще надеюсь, что центроид тяжести со сферической областью, подобный вышеупомянутому, будет работать. Представьте, что каждому многоугольнику дают трехмерный объем, добавляя вершину в начале сферы. Затем приостановите сферу невидимой струной, связанной с ее источником, и найдите устойчивое равновесие. Центроид является самой нижней точкой (это проекция центра масс на сферическую поверхность). Это должно работать в стороне от нескольких неоднозначных случаев, например, от полосы, идущей вокруг экватора, где я могу просто выбрать разумную точку. Рад обсудить новый вопрос, если вы считаете, что оно того стоит.
Джейсон Дэвис
3

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

(а) Это свойство внутренней части многоугольника (вместо вершин или ребер). Таким образом, разделение ребра на две части путем вставки дополнительной вершины не должно изменять положение центроида. Обратите внимание, что определение центроида по Дженнессу не соответствует этому критерию, поскольку положение центроида будет зависеть от того, как многоугольник делится на треугольники.

(b) Небольшое изменение формы многоугольника должно немного сместить центр тяжести. Здесь необходимо наложить ограничение на общую протяженность многоугольника (например, до одного полушария). Без этого ограничения легко построить случаи, когда центроид внезапно качается к противоположной стороне земли с небольшим движением вершины. Это условие исключает методы, которые требуют, чтобы центроид лежал внутри многоугольника.

(c) Он должен привести к плоскому определению центроида для небольших полигонов.

Вот два подхода, удовлетворяющие этим критериям:

(1) Вычислить центроид для эллипсоидального многоугольника в трех измерениях и спроецировать обратно на поверхность эллипсоида (вдоль нормали к эллипсоиду). Большое преимущество: центроид можно вычислить, разбив многоугольник на более простые формы.

(2) Центроид - это точка с минимальным среднеквадратическим геодезическим расстоянием до всех точек внутри многоугольника. См. Buss и Fillmore, «Сферические средние и применения к сферическим сплайнам и интерполяции», ACM Transactions on Graphics 20 , 95–126 (2001). Большое преимущество: полученная точка не зависит от того, как поверхность встроена в R 3 .

К сожалению, ни одно из этих определений не является простым для применения на практике. Однако первый способ может быть осуществлен просто для сферы. Лучшей «элементарной» областью для использования является четырехугольник, ограниченный ребром многоугольника, двумя меридианами через конечные точки ребра и экватором. Результат для всего многоугольника влечет за собой суммирование вкладов по ребрам. (Дополнительные шаги необходимо предпринять, если многоугольник окружает полюс.)

Предположим, что конечными точками ребра являются (φ 1 , λ 1 ) и (φ 2 , λ 2 ). Пусть азимуты ребра и конечных точек по α 1 и α 2 . Предполагая, что радиус сферы равен 1, площадь четырехугольника равна

  A = α 2 - α 1
      = 2 tan -1 [tan ½ (λ 2 - λ 1 ) sin ½ (φ 2 + φ 1 ) / cos ½ (φ 2 + φ 1 )]

(Эта формула для площади, по Бесселю, существенно лучше ведет себя численно, чем общепринятая формула Л'Уилье для площади треугольника.)

Компоненты центроида для этого четырехугольника определяются

  2 ⟨ х ⟩ = φ 2 Sin (λ 2 - λ 0 ) - φ 1 Sin (λ 1 - λ 0 )   2 ⟨ у ⟩ = сов α 02 - σ 1 ) - (φ 2 сов (λ 2 - λ 0 ) - φ 1 сов (λ 1 - λ 0 ))   2 ⟨ г ⟩ = (λ 2 - λ 1 ) - SIN α 02 - σ

1 )

где σ 2 - σ 1 - длина ребра, а λ 0 и α 0 - долгота и азимут ребра, где он пересекает экватор, а оси x и y ориентированы так, чтобы пересечение экватора находилось в точке x = 1, y = 0. ( z - ось, проходящая через полюс, конечно.)

cffk
источник
Можете ли вы объяснить, почему положение центроидов Дженнесса будет зависеть от того, как многоугольник делится на треугольники? Я знаю из примера @ whuber, что вычисление центроида Дженнесса неверно для сферических треугольников, но что если вместо этого использовать центроид, основанный на медианах сферического треугольника? Это все еще не удастся?
Джейсон Дэвис
Дженнесс эффективно заменяет сферический многоугольник набором плоских треугольников и вычисляет их центроид. Понятно (?), Результат будет зависеть от разбиения. Выполнение вычисления, которое я обрисовал в общих чертах с использованием центроидов сферических треугольников, хорошо. Вы можете найти формулу для центроида в JE Brock, Тензор инерции для сферического треугольника, J. ​​Applied Mechanics 42, 239 (1975) dx.doi.org/10.1115/1.3423535
cffk
Я еще раз взглянул на бумагу Брока. Его формула для центра масс сферического треугольника включает сумму по краям треугольника. Поэтому его можно обобщенно применить к многоугольнику (без необходимости разбивать его на треугольники).
cffk
Вы не против предоставить ссылку для расчета площади из-за Бесселя? Кажется, я нигде не могу его найти, и мне интересно написать быструю (и точную) сферическую область многоугольника. Благодаря!
Джейсон Дэвис
Я нашел его и понял, что вы перевели его на английский, так что спасибо. :)
Джейсон Дэвис