Реализация геометрической медианы

Question

Когда я гуглял по геометрической медиане, я получал эту ссылку Геометрическая медиана но я понятия не имею, как реализовать это в C. Я не очень хорошо понимаю это математическое объяснение. Допустим, у меня есть 11 пар координат, как рассчитать геометрическую медиану для того же.

Я пытаюсь решить эту проблему Grid CIty . Мне дали подсказку, что геометрическая медиана поможет мне достичь этого. Я не ищу окончательного решения. Если кто-то может направить меня на правильный путь, который поможет.

Спасибо за продвижение

Ниже приведен список координат a (контрольный пример). результат: 3 4

1 2
1 7
2 2
2 3
2 5
3 4
4 2
4 5
4 6
5 3
6 5

Answer 1

Я не думаю, что это разрешимо без итеративного алгоритма.

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

CurrentPoint = Mean(Points)
While (CurrentPoint - PreviousPoint) Length > 0.01 Do
    For Each Point in Points Do
        Vector = CurrentPoint - Point
        Vector Length = Vector Length - 1.0
        Point2 = Point + Vector
        Add Point2 To Points2
    Loop
    PreviousPoint = CurrentPoint
    CurrentPoint = Mean(Points2)
Loop

Примечания:

Константа 0,01 не гарантирует, что результат будет в пределах 0,01 от истинного значения.Используйте меньшие значения для лучшей точности.

Константа 1.0 должна быть скорректирована до (я предполагаю) примерно 1/5 расстояния между самыми дальними точками.Слишком малые значения будут замедлять алгоритм, но слишком большие значения приведут к неточностям, которые могут привести к бесконечному циклу.

Answer 2

Ответ (x _i , y _j ), где x _i медиана всех х и у _j медиана всех у.

Answer 3

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

Answer 4

Вы не обязаны использовать понятие геометрической медианы; так что, посчитав, что это не легко вычислить, лучше решить свою проблему, не вычисляя ее!

Вот идея алгоритма / реализации.

1. Начало в любой точке (например, в первой точке заданных данных).
2. Рассчитать сумму расстояний для текущей точки и 8 соседних точек (+/- 1 в каждом направлении, x и y)
3. Если один из соседей лучше текущей точки, обновите текущую точку и начните с 1
4. (найдено оптимальное расстояние; теперь выберите лучшую точку среди равных по расстоянию)
5. Рассчитать сумму расстояний для текущей точки и трех соседних точек (-1 в каждом направлении, x и y)
6. Если один из соседей совпадает с текущей точкой, обновите текущую точку и продолжайте с 5

Answer 5

Когда я комментирую, решение вашей проблемы - не среднее геометрическое, а среднее арифметическое.

Если вам нужно вычислить среднее арифметическое, вам нужно сложить все значения столбца и разделить ответ на количество элементов.