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

Question

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

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

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

Answer 1

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

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.Как видите, центральную точку можно определить разными способами.Ниже я показываю вам примеры двух 2D-облаков точек с учетом этих предложений.

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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