Как вычислить центр многоугольника в 2D и 3D пространстве

Рассмотрим простой выпуклый многоугольник в двумерном декартовом пространстве. Если задан список координат вершин, отсортированных в ориентации против часовой стрелки, например, [[x0, y0], ..., [xn, yn]]. Как можно вычислить центр многоугольника (точку внутри многоугольника, которая равноудалена всем вершинам)?

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

Я могу читать C / C ++, Fortran, MATLAB и Python, однако любой псевдокод также приветствуется.

ИЗМЕНИТЬ

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


python c++ matlab geometry polygon
person Aeronaelius    schedule 19.08.2013    source источник
comment
mean(x) mean (y)? Я не уверен, существует ли точка, равноудаленная от всех вершин, для всех многоугольников (например, точки четырехугольника в точках (0,0), (0,1), (0, -1), (3,0)).   -  person Hugh    schedule 19.08.2013
comment
Это не четырехугольник, а Т-образная форма.   -  person Aeronaelius    schedule 19.08.2013
comment
В общем, большинство полигонов не имеют точки, равноудаленной от всех вершин. Вы знаете, что они регулярные?   -  person PeterM    schedule 19.08.2013
comment
ОК выпуклая оболочка этих точек (переместите (0,0) в (-0,0001, 0), если хотите). В любом случае, я думаю, что центра, как вы описали, вообще не существует. Вы можете посмотреть en.wikipedia.org/wiki/Centroid#Centroid_of_polygon if 'centroid 'это то, что вам нужно.   -  person Hugh    schedule 19.08.2013

Ответы (2)


arrow_upward
10
arrow_downward

Ваше определение центра вообще не имеет смысла.

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

Теперь нарисуйте четвертую точку, которая не лежит на окружности и образует четырехгранный многоугольник. Что такое центр? На плоскости нет точки, равноудаленной от всех вершин.

Также обратите внимание, что даже в случае треугольников с использованием точки, равноудаленной от вершин, вы можете получить точки вне и далеко от многоугольника, а также численно нестабильно (при любых ε> 0 и M> 0 вы всегда можете построить треугольник, в котором специфическое перемещение вершины на расстояние меньше ε перемещает центр на расстояние больше M).

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

Самый простой разумный (поскольку он не зависит от системы координат) - это барицентр вершин (код на Python):

xc = sum(x for (x, y) in points) / len(points)
yc = sum(y for (x, y) in points) / len(points)

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

sx = sy = sL = 0
for i in range(len(points)):   # counts from 0 to len(points)-1
    x0, y0 = points[i - 1]     # in Python points[-1] is last element of points
    x1, y1 = points[i]
    L = ((x1 - x0)**2 + (y1 - y0)**2) ** 0.5
    sx += (x0 + x1)/2 * L
    sy += (y0 + y1)/2 * L
    sL += L
xc = sx / sL
yc = sy / sL

Для них обоих расширение до 3d тривиально ... просто добавьте z, используя те же формулы.

В случае общего (не обязательно выпуклого, не обязательно односвязного) многоугольника «центром», который я нашел полезным, но который нетривиально вычислить, является () внутренняя точка, которая находится на максимальном расстоянии от границы (в другими словами «самая внутренняя» точка).

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

person 6502    schedule 19.08.2013

arrow_upward
4
arrow_downward

Прежде всего, для многоугольника центроид не всегда может означать равноудаленную длину от центроида до вершин. В большинстве случаев это, вероятно, НЕ правда. При этом вы можете найти центроид, просто найдя среднее значение ваших x координат и среднее значение ваших y координат. В Matlab: centroidx = mean(xcoords) и centroidy = mean(ycoords) - координаты центроида. См. это, если вам действительно нужно больше.

person voxeloctree    schedule 19.08.2013