Нахождение центральной точки и границ произвольной замкнутой кривой (случайное блуждание)

Question

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

Answer 1

Есть два возможных толкования (возможно, больше) вашего вопроса.

Первый из них уже был рассмотрен @AakashM, и мы можем изобразить его на следующем графике:

Где красный квадрат - это "граница".
Я приведу здесь @AakashM, потому что я понимаю его замечание ОЧЕНЬ важное: "(отмечу, что для того, чтобы у вас была замкнутая кривая, вам нужно, чтобы конечная точка была не просто" близкой к ", а совпадающей с первой пункт) "

Что касается центральной точки, у вас есть по крайней мере два "естественных способа" для ее вычисления с помощью следующих определений:

1. Центральная точка = Средняя точка Красной площади
2. Центральная точка = {Среднее из x координат вашей кривой, Среднее из y координат вашей кривой}

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

Другой способ решения проблемы - найти выпуклую оболочку вашей кривой, как показано ниже:

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

Опять же, у вас есть два "естественных способа вычисления центральной точки:

1. Centerpoint = {Среднее по x координатам вашей кривой, Среднее по y координатам вашей кривой}
2. Центральная точка = {Среднее из x координат точек CH, Среднее из y координат точек CH}

НТН!

Answer 2

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

Если под «центральной точкой» вы имеете в виду центр масс и вы предполагаете равномерную плотность, то этот вопрос имеет то, что вы хотите.

Если под «границами» вы подразумеваете ограничивающий прямоугольник со сторонами, параллельными осям, вам просто нужны минимальные и максимальные значения x и y на кривой.

Если что-то из этого не то, что вы имеете в виду, пожалуйста, скажите ...

Answer 3

Для границ вы можете обратиться к ответам, данным @belisarius и @ AakashM.

Что касается центральной точки, вам нужен "центр масс".Good 'ol Википедия имеет объяснения и рецепты на http://en.wikipedia.org/wiki/Center_of_mass и http://en.wikipedia.org/wiki/Centroid.

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