Как лучше всего рассчитать трехмерный (или n-D) центроид? - PullRequest
17 голосов
/ 17 сентября 2008

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

centroid = average(x), average(y), average(z)

, где x, y и z - массивы чисел с плавающей точкой. Кажется, я помню, что есть способ получить более точный центроид, но я не нашел простого алгоритма для этого. У кого-нибудь есть идеи или предложения? Я использую Python для этого, но я могу адаптировать примеры из других языков.

Ответы [ 8 ]

13 голосов
/ 17 сентября 2008

Нет, это единственная формула для центроида набора точек. Смотрите Википедию: http://en.wikipedia.org/wiki/Centroid

11 голосов
/ 18 сентября 2008

Вы смутно упоминаете «способ получить более точный центроид». Возможно, вы говорите о центроиде, на который не влияют выбросы. Например, средний доход домохозяйства в США, вероятно, очень высок, потому что небольшое количество очень богатых людей искажают среднее; они являются "выбросами". По этой причине статистики используют взамен медиана . Один из способов получить медиану - это отсортировать значения, а затем выбрать значение наполовину вниз по списку.

Может быть, вы ищете что-то вроде этого, но для 2D или 3D очков. Проблема в том, что в 2D и выше вы не можете сортировать. Там нет естественного порядка. Тем не менее, есть способы избавиться от выбросов.

Один из способов - найти выпуклую оболочку точек. Выпуклая оболочка имеет все точки «снаружи» множества точек. Если вы сделаете это и выбросите точки, которые находятся на корпусе, вы выбросите выбросы, а оставшиеся точки дадут более «представительный» центроид. Вы можете даже повторить этот процесс несколько раз, и результат будет как очищение лука. На самом деле, это называется «выпуклая оболочка корпуса».

8 голосов
/ 13 июня 2016

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

centroid = average(x), average(y), average(z)

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

В качестве альтернативы вы можете использовать математическую середину (среднее значение экстремумов) в каждом измерении, чтобы избежать этого:

middle = middle(x), middle(y), middle(z)

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

Наконец, вы также можете использовать median (элемент посередине) в каждом измерении:

median = median(x), median(y), median(z)

Теперь это как бы противоположно middle и фактически поможет вам игнорировать выбросы в облаке точек и найти центральную точку на основе распределения ваших точек.

Более надежным способом найти «хорошую» центральную точку может быть игнорирование верхнего и нижнего 10% в каждом измерении, а затем вычисление average или median. Как видите, вы можете определить центральную точку по-разному. Ниже я показываю вам примеры двухмерных облаков точек с учетом этих предложений.

Синяя точка - средний (средний) центроид. Медиана показана зеленым цветом. А середина показана красным. На втором изображении вы увидите именно то, о чем я говорил ранее: зеленая точка находится «ближе» к самой плотной части облака точек, а красная точка находится дальше от нее, принимая во внимание самые крайние границы облако точек.

enter image description here enter image description here

3 голосов
/ 17 сентября 2008

Вы можете использовать увеличение точности суммирования - суммирование Кахана - это было то, что вы имели в виду?

2 голосов
/ 17 сентября 2008

Потенциально более эффективно: если вы рассчитываете это несколько раз, вы можете немного ускорить это, сохраняя две постоянные переменные

N  # number of points
sums = dict(x=0,y=0,z=0)  # sums of the locations for each point

затем изменяя N и суммы, когда точки создаются или уничтожаются. Это меняет положение с O (N) на O (1) для расчетов за счет увеличения объема работы каждый раз, когда точка создается, перемещается или уничтожается.

0 голосов
/ 17 сентября 2008

Да, это правильная формула.

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

0 голосов
/ 17 сентября 2008

«Более точный центроид» Я считаю, что центроид определяется так, как вы его вычислили, поэтому «более точного центроида» не может быть.

0 голосов
/ 17 сентября 2008

Вы получили это. То, что вы рассчитываете, это центроид или средний вектор.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...