Учитывая список краев voronoi, как я могу получить центр масс каждой ячейки за разумное время ?, обратите внимание, что у меня есть только края диаграммы Voronoi, но я должен идентифицировать центр масс.Центр масс в ячейках voronoi
Диаграмма Вороного построена с учетом триангуляции Делоне, так что триангуляция также доступна для расчетов.
Спасибо!
Этот algorithm from wikipedia должен работать. Это требует только ввода координат точек, которые ограничивают каждую ячейку. Поскольку клетки Вороного гарантированы как несамопересекающиеся и выпуклые, этого должно быть достаточно. Перекодирование немного (StackOverflow не делает хороший математике)
Центроид не-самопересекающихся замкнутого полигона, определяемой '' N '' вершин (х , у), (х , у), ..., (х п , у п) является точка (С х, С у), задается
Cx = 1/(6*A) * sum((x[i] + x[i+1]) * (x[i]*y[i+1] - x[i+1]*y[i]) Cy = 1/(6*A) * sum((y[i] + y[i+1]) * (x[i]*y[i+1] - x[i+1]*y[i])С A области, рассчитанный как
A = 1/2 * sum(x[i]*y[i+1] - x[i+1]*y[i])Где все те
sumпредставляют Σ от I = 0 до I = п-1
Проблема в том, что я не могу получить вершины каждого многоугольника с учетом списка ребер –
Но я должен сделать это в разумные сроки. Я хочу знать, существует ли какое-либо свойство, использующее триангуляцию Делоне, для построения многоугольников или чего-то подобного. –
@ValentinaRamirez: вы можете найти вершины многоугольников из списка ребер при прохождении по всем краям и найти расстояния между сайтом и серединой ребер. Сортируйте список по возрастанию и добавьте первые два ребра в многоугольник voronoi с сайтом в центре. – Bytemain
Сначала определите все ребра для конкретной ячейки, а затем для этой ячейки возьмем среднее значение х-компонента, тогда среднее значение y-компонента будет разделено, тогда линейная комбинация будет «центром массы» ячейки. Тогда просто сделайте то же самое для каждой ячейки диаграммы Вороного.
Этот метод работает для треугольников. Он не работает для многоугольников с 4 или более вершинами. Простым встречным примером является многоугольник с вершинами (1,0), (2,0), (3,1), (0,1).Среднее значение y равно 'y = 1/2', но центр массы равен' y = 7/12'. – user3386109
Знаете ли вы края ячеек или просто набор ребер на всей диаграмме? –
@hege_hegedus Я не kwno по краям ячеек –
Я предполагаю, если вы знаете края, что знаете их вершины? – tucuxi