forum.boolean.name - Центр многоугольгика

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Центр многоугольгика (http://forum.boolean.name/showthread.php?t=13803)

Randomize

01.12.2010 11:39

Центр многоугольгика

Есть массив, в котором друг за другом идут X и Y. Таким образом описана геометрия многоугольника. От 4 до 10 точек на каждый. Отрезки не пересекаются.
Есть ли простой алгоритм по вычислению центройда для такой фигуры. Универсального средства не требуется. Первое, что пришло на ум - это взять и высчитать так называемый BoundingBox (описывающий четырёхугольник) и поделив каждую строну пополам - получаю центройд. Но терзают меня смутные сомнения, что существуют более грамотные решений. Светлые умы - подскажите верный путь. Я птушник, так что просьба не кидать супер формулу где под переменной циферки и над ней тоже, а также загогулина такая намоминающая букву S :-D .

Для ясности пример:
Входящие данные: 0,0, 0,5, 10,5, 10,10, 15, 10, 15,15, 0,15

pax	01.12.2010 12:06

Ответ: Центр многоугольгика

По моему тебе пришла на ум верная идея, где нет сложных вычислений, а одни сравнения, только в конце center((xmin+xmax)/2,(ymin+ymax)/2).

impersonalis

01.12.2010 12:10

Ответ: Центр многоугольгика

Проблема, возможно, будет только с вогнутыми многоугольниками: вычисленный по BoundingBox центр может оказаться вне фигуры

pax	01.12.2010 13:54

Ответ: Центр многоугольгика

А мне кажется это не проблема. Не у всех тел центр в их полости. Даже центр масс так же может быть не в полости тела.

.Squid

01.12.2010 14:03

Ответ: Центр многоугольгика

Описывающий четырёхугольник не катит. Это видно, даже глядя на твой первый пример.
Центроид - он же барицентр, совпадает с центром масс (если плотность однородная).
Попробуй применить первую формулу из http://ru.wikipedia.org/wiki/Центр_масс . Ниже не смотри - там как раз "загогулина такая намоминающая букву S".

SBJoker

01.12.2010 14:35

Ответ: Центр многоугольгика

Центр масс находится емнип как среднее координат ограничивающих фигуру.

Randomize

01.12.2010 21:32

Ответ: Центр многоугольгика

Ух. Уфф. Как же это в код перевести, то?
i - внизу - это циклический перебор.
rc - радиус вектор. Он в x и y или дистанция и угол поворота?
Моя не понимать ваши формулы. Где почитать, то как это перевести в код? Или кто вразумит нерадивого неуча псевдо кодом отличным?

h1dd3n

01.12.2010 21:51

Ответ: Центр многоугольгика

Код:

double SummX = 0;

double SummY = 0;

foreach (Point a in AllPoints)

{

SummX += a.x;

SummY += a.y;

}

Point Centroid = new Point(SummX / AllPoints.count, SummY / AllPoints.count);

Randomize

01.12.2010 21:57

Ответ: Центр многоугольгика

Лолшто? Тупо складываем все точки и делим на их кол-во?

impersonalis

01.12.2010 22:06

Ответ: Центр многоугольгика

ТЗ нечёткое: тебе нужен геометрический центр или центр масс?

.Squid

01.12.2010 22:09

Ответ: Центр многоугольгика

Цитата:

Сообщение от Randomize (Сообщение 170505)

Лолшто? Тупо складываем все точки и делим на их кол-во?

Собственно говоря, да.
Радиус-центр - вектор, задающий положения точки в пространстве относительно некоторой заранее фиксированной точки, называемой началом координат (Википедия).
Например, треугольник (4; 2) (2; 6) (5; 8). Барицентр - (3,667; 5,333). Можешь построить и убедиться.

Randomize

02.12.2010 06:34

Ответ: Центр многоугольгика

Спасибо всем, вот что получилось:

PHP код:




<script type="text/javascript"> 
            function FindCentroid(points){ 
 
                var count = points.length; 
                var Sx = 0; 
                var Sy = 0; 
 
                for (i=0;i<count;i+=2){ 
                    Sx+= parseInt(points[i]); 
                    Sy+= parseInt(points[i+1]); 
                } 
 
 
 
                Sx = Sx / (points.length * 0.5); 
                Sy = Sy / (points.length * 0.5); 
 
                document.write( '<br /> Centroid: <b>' + Sx +' , '+ Sy +'</b><br />'); 
                var result = new Array(parseInt(Sx), parseInt(Sy)); 
                return result; 
 
            } 
 
            var arr; 
 
            document.write('<fieldset> <legend>Poly</legend>'); 
 
            arr = [0,0, 0,5, 10,5, 10,10, 15,10, 15,15, 0,15]; 
            FindCentroid(arr); 
            document.write('</fieldset>'); 
 
            document.write('<fieldset> <legend>Square</legend>'); 
            arr = [0,0, 0,5, 5,5, 5,0]; 
            FindCentroid(arr); 
            document.write('</fieldset>'); 
 
            document.write('<fieldset> <legend>Triangle</legend>'); 
            arr = [0,10, 10,10, 10,20]; 
            FindCentroid(arr); 
            document.write('</fieldset>'); 
 
        </script>

И результаты:

Цитата:

Poly
0,0; 0,5; 10,5; 10,10; 15,10; 15,15; 0,15;
Centroid: 7.14 , 8.57

Square
0,0; 0,5; 5,5; 5,0;
Centroid: 2.50 , 2.50

Triangle
0,10; 10,10; 10,20;
Centroid: 6.67 , 13.33

То, что надо :D

Часовой пояс GMT +4, время: 10:31.