Вычисление геометрического центра

Сложить все координаты и поделить на количество точек.

http://en.wikipedia.org/wiki/Geometric_median

Вот это гуглить.

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

сумма расстояний от данной точки до каждой из данных точек минимальна
Что гуглить?

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

Это все нужно, если искать центр тяжести, когда нужно найти минимум суммы квадратов расстояний. А ТС просит минимум суммы расстояний, а тут просто сложить и поделить достаточно будет, как фроб сказал.

Но скорее всего ТС сам не знает, чего ему надо.

Но скорее всего ТС сам не знает, чего ему надо.

Это почти наверняка.

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

P.S. Плохо ТЗ прочитал. Если центр — точка с минимумом расстояний до краев фигуры, нужно погуглить методику определения центра выпуклой оболочки. Грубо говоря, строим конусы с вершиной в 90° на всех точках, расположенных на границе фигуры. Их пересечение внутри фигуры даст эдакую область, ограничивающую искомый центр. «Глубина» на конусе будет являться расстоянием от искомой точки до соответствующей точки края фигуры.

Гуглить: выкуклая оболочка, эрозия и дилатация…

Где-то в литературе я натыкался на искомый автором алгоритм, но не могу припомнить, увы.

мне кажется вам нужно просто найти границы вашей фигуры(min,max по X и по Y) и найти центр прямоугольника - он и будет центром фигуры(хотя я мог неправильно прочитать задачу)

http://en.wikipedia.org/wiki/Geometric_median#Computation

Господи, открой им глаза.

Дано множество точек в R^2, нужно найти геометрический центр. Допустим, геометрический центр задан как точка в которой сумма расстояний от данной точки до каждой из данных точек минимальна.

сумма всех расстояний является «выпуклой». А значит, что любой численный метод будет однозначно сходиться.

Заюзай например fminsearch из octave.

А ТС просит минимум суммы расстояний, а тут просто сложить и поделить достаточно будет, как фроб сказал.

а вот фиг.

А докажь!

А докажь!

http://ompldr.org/vZjVyMw/tabelle2.csv

если просто среднее считать, то получишь точку (7.8250,4.8800) и расстояние 102.90

а если считать как нужно, то будет точка (8.0,5.0) и расстояние 102.62

иллюстрация:

http://ompldr.org/vZjVyNA/t.png

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

Гуглить: выкуклая оболочка, эрозия и дилатация…

это к сабжу отношения не имеет.

Среднее не катит даже в одномерном случае: x = 0 1 5, среднее будет 2. Сумма расстояний = 6 = |0-2| + |1-2| + |5-2|, но |0-1| + |1-1| + |5-1| = 5.

Поделить статический момент инерции на площадь фигуры http://sopromat.org/info/1/1_1_.php. Правда это будет центр тяжести сечения, но он ЕМНИП совпадает с геометрическим.

Угу... сообразил уже. Спасибо.

о будет центр тяжести сечения, но он ЕМНИП совпадает с геометрическим.

это то же среднее арифметическое => не катит.

Господи, открой им глаза.

А главное, находят же еще что обсудить после, казалось бы, исчерпывающего ответа. Там же даже какая-то итерационная формула приведена (хотя, если честно, не совсем понятно, почему там не метод Ньютона).

Если фигура сложная, проще сделать графическими методами, нежели аналитическими.

Если фигура сложная, проще сделать графическими методами, нежели аналитическими.

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

ну и чтобы найти оптимальную точку в любом случае надо численными методами приближать. «графическим» ты лишь стартовую точку хорошую найдешь.

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

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

почитал ссылки повнимательней. Там какая-то жесть :) Может и можно как-то присобачить к сабжу, но зачем? :)

Затем, что если у тебя, скажем, сотня-другая точек, то аналитический метод — самое оно, а когда их миллионы или даже миллиарды, быстрее будет геометрическим. При желании можно потом уточнить положение упрощенным аналитическим.

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

если эффективность графического метода хотя бы меньше O(n^3), то да.

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

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

Можно. А потом пройтись по центрам кластеров с той же самой операцией.

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

Спасибо всем ответившим в данной ветке.