Нахождение центра геометрии объекта?

37

Дан набор 2D или 3D точек:

Как найти центр геометрии объекта?

Согласно следующему рисунку, центр геометрии отличается от центра масс, если он рассчитан в простейшем виде, т. Е. Однородной плотности массы. Проблема возникает, действительно, в расчете тех. Как правило, один из подходов состоит в том, чтобы усреднять координаты X и координаты Y по отдельности, т.е. находить среднее положение для заданных точек (здесь в 2D). Это может быть использовано в качестве центроида для набора точек, представляющих объект. Как показано, из-за лишней вершины вдоль нижнего края для простого прямоугольника результирующий центроид равен (0,5,0,4), а правильный ответ - (0,5,0,5) .
Обратите внимание, что приведенный пример слишком прост. Однако проблема представляет интерес для сложных фигур в 2D и объектов в 3D, для которых доступны только координаты вершин.
Кстати, эффективный вычислительный способ представляет интерес.

Просто чтобы упомянуть, что я проверил некоторые веб-ссылки, такие как Википедия, однако моя текущая проблема заключается в том, что есть группа 2D и 3D точек, которые хотят найти точку в качестве представителя для них. Таким образом, центроид стал представлять интерес. Точки приведены без какой-либо топологической информации. Вы можете рассматривать их как облако точек. Демонстрация, приведенная здесь, позволяет прояснить, что общеизвестное усреднение координат (см., Например, это вопросы и ответы по переполнению стека ) может быть неправильным, как показано в примере.

введите описание изображения здесь

Вот несколько реализаций для сравнения:

  • аа = принятый ответ ниже
  • chull = выпуклая оболочка точек, т. е. золотой многоугольник
  • цент = Centroid предложен в Википедии и обсуждается в аа как полигон центроида
  • centl = центроид ломаной линии , как описано в аа

Визуально centlвыглядит лучше представленной для данной геометрии по сравнению с cent. Два других здесь выглядят многообещающими, но обычно они слишком предвзяты, если дисперсия точек была неоднородной, как это обычно бывает.
А также учтите, что хотя выпуклая оболочка делает задачу достаточно простой, однако она может генерировать слишком длинные и слишком короткие ребра без какого-либо симметричного позиционирования в пространстве, то есть осознание необходимо, если вы делаете простое усреднение (т.е. без взвешивания) для обоих случаев : целые точки (зеленый) или вершины многоугольника с выпуклой оболочкой (синий).

введите описание изображения здесь

Одно приложение может быть найдено в Нахождение минимальной площади прямоугольника для заданных точек? ,

разработчик
источник
Будет ли это работать? Нахождение центроида многоугольника? (StackOverflow)
blah238
3
Я не уверен, что ваш вопрос. Центр геометрии или (обычно центроид) может отличаться от барицентра (центра масс). Это хорошо известный факт. Также существуют различные способы вычисления центра геометрии. См: en.wikipedia.org/wiki/Triangle_center , en.wikipedia.org/wiki/Encyclopedia_of_Triangle_Centers & faculty.evansville.edu/ck6/encyclopedia/ETC.html .
Девдатта Тенгше
1
Об обновлении: когда нет топологии, облако точек - это просто облако точек. Ваша фигура многоугольного квадрата не применяется (и ваш «центр тяжести» (0.5,0.4), по-видимому, не возникает из какой-либо стандартной формулы, кстати: симметрия настоятельно аргументирует, что любая центральная точка квадрата совпадает с (0.5 0,5), независимо от того, как оно определено). Некоторые идеи по поиску репрезентативных или центральных местоположений для облаков точек в двух и более измерениях см. В stats.stackexchange.com/questions/1927 .
whuber
1
@ Разработчик, я вижу вашу точку зрения, ваша пятая точка в нижней части «прямоугольника» (на самом деле многоугольника) делает простое усреднение координат вершин, что дает другой барицентр, чем у многоугольника, как объясняет ответ Вубера.
blah238
1
Ага! Я полностью пропустил эту пятую вершину, хотя искал что-то подобное. Чтобы помочь будущим читателям, я внес небольшое изменение в вопрос, чтобы указать на это. Это действительно добраться до сути дела, тоже: вставка или удаление вершин вдоль ребер изменятся , как поли {линия, угольник} представлены , но это не должно изменить вычисление его врожденных геометрических свойств. Вот почему барицентр вершин может иметь почти произвольное отношение к барицентрам многоугольника или его границе.
whuber

Ответы:

44

Каждый полигон имеет как минимум четыре отдельных "центра":

  • Барицентр его вершин.

  • Барицентр его краев.

  • Его барицентр как многоугольник.

  • ГИС-специфический «центр», полезный для маркировки (обычно рассчитывается с использованием недокументированных проприетарных методов).

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

«Барицентр» в целом - это «центр масс». Три типа различаются в зависимости от того, где предположительно расположена масса: она либо полностью находится на вершинах, либо равномерно распределена по краям, либо равномерно распределена по всему многоугольнику.

Существуют простые методы для вычисления всех трех барицентров. Один из подходов основан на том факте, что барицентр несвязанного объединения двух масс является средневзвешенным значением барицентров. Из этого легко получить следующее:

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

  2. Индуктивно барицентр из n (одинаково взвешенных) вершин получается путем усреднения их координат отдельно.

  3. Барицентр отрезка является его серединой. (Это ясно по симметрии.)

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

    Например, рассмотрим форму «L», очерченную точками (0,0), (6,0), (6,12). Есть два сегмента: один длиной 6 со средней точкой в ​​((0 + 0) / 2, (0 + 6) / 2) = (3,0) и другой длиной 12 со средней точкой в ​​((6 + 6) / 2, (0 + 12) / 2) = (6,6). Их средневзвешенные по длине координаты, следовательно, (x, y) с

    x = (6*3 + 12*6) / (6+12) = 5,  y = (6*0 + 12*6) / (6+12) = 4.
    

    Это отличается от барицентра трех вершин, который ((0 + 6 + 6) / 3, (0 + 0 + 12) / 3) = (4,4).

    ( Изменить В качестве другого примера рассмотрим фигуру в вопросе, которая хотя и имеет квадратную форму, представлена ​​в виде пятиугольника, определяемого последовательностью точек (0,0), (1 / 2,0), (1,0), (1,1), (0,1). Пять сторон имеют длины 1/2, 1/2, 1, 1, 1 и средние точки (1 / 4,0), (3 / 4,0), (1 , 1/2), (1 / 2,1) и (0,1 / 2) соответственно, поэтому их средневзвешенное значение равно

    [(1/2)*(1/4, 0) + (1/2)*(3/4, 0) + (1)*(1, 1/2) + (1)*(1/2, 1) + (1)*(0, 1/2)] / (1/2+1/2+1+1+1)
    = (2/4, 2/4) = (0.5, 0.5)
    

    как можно было бы надеяться, даже если барицентр одной вершины (вычисленный как в # 2 выше) равен (0,5, 0,4).)

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

    ( Правка. Рассмотрим, например, многоугольник, изображенный в вопросе. Мы можем триангулировать его треугольниками ((0,0), (1 / 2,0), (0,1)) слева, ((0,1), (1 / 2,0), (1,1)) посередине и ((1,1), (1,0), (1 / 2,0)) справа. Их площади составляют 1/4 , 1/2, 1/4 соответственно и их барицентры - полученные путем усреднения их вершин - (1 / 6,1 / 3), (1 / 2,2 / 3) и (5 / 6,1 / 3), соответственно. Средневзвешенная площадь этих барицентров равна

    [(1/4)*(1/6,1/3) + (1/2)*(1/2,2/3) + (1/4)*(5/6,1/3)] / (1/4 + 1/2 + 1/4)
    = (12/24, 6/12)
    = (0.5, 0.5)
    

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

Очевидно, что каждый из этих методов эффективен : он требует всего одного прохода для представления многоугольника «спагетти», используя (довольно небольшое) постоянное время на каждом шаге. Обратите внимание, что во всех случаях, кроме первого (из чистых вершин), требуется больше информации, чем просто список координат вершин: вам также необходимо знать топологию фигуры. В примере «L» нам нужно было знать, что (0,0) связано, например, с (6,0), а не с (6,12).

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

Другое обобщение признает, что евклидова метрика - квадратный корень из суммы квадратов, согласно Пифагору - может быть изменена на другие метрики Lp для p> = 1: вы берете корень pth от суммы степеней pth. Найти подходящие «барицентры» уже не так просто, потому что красивые аддитивные свойства, использованные выше (барицентры - это средневзвешенные значения барицентров более простых частей фигуры), в общем, больше не действуют. Часто итерационные приближенные численные решения должны быть получены. Они могут даже не быть уникальными.

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

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

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

Whuber
источник
Сообществу: такого хорошего ответа, как этот, от «whuber» можно ожидать только для хорошего вопроса, так как мое знакомство с его предпочтениями, таким образом, вы не возражаете, если бы вы тоже проголосовали, если вам было интересно;)
Разработчик
Я нашел это полезным в некотором смысле, желая дать время другим участникам в качестве мотивации для ответа. Однако я отмечаю это приемлемым конструктивным ответом.
Разработчик
Можете ли вы объяснить, почему области все еще находят, используя клиновые продукты на сфере? Разве сферическая область треугольника не будет более подходящей? Ближайшая ссылка (кроме этого превосходного ответа!), Которую я нашел, - это: jennessent.com/downloads/Graphics_Shapes_Online.pdf - где используются области сферических треугольников.
Джейсон Дэвис
@ Джейсон Я заинтригован: как вы предлагаете использовать области сферических треугольников для вычисления барицентров сферических элементов?
whuber
@whuber Сферический многоугольник разлагается на сферические треугольники, а барицентр каждого треугольника вычисляется путем усреднения декартовых координат его вершин. Я предполагаю, что барицентр многоугольника является средневзвешенным значением этих треугольников, где вес - это сферическая площадь треугольника, а не плоская область, как вы предложили в своем ответе (при условии, что я правильно понимаю произведение клина).
Джейсон Дэвис