Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 01.12.2010, 11:39   #1
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,354
Написано 2,470 полезных сообщений
(для 6,850 пользователей)
Центр многоугольгика

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

Для ясности пример:
Входящие данные: 0,0, 0,5, 10,5, 10,10, 15, 10, 15,15, 0,15
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо Randomize за это полезное сообщение:
Harter (01.12.2010), impersonalis (01.12.2010)
Старый 01.12.2010, 12:06   #2
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: Центр многоугольгика

По моему тебе пришла на ум верная идея, где нет сложных вычислений, а одни сравнения, только в конце center((xmin+xmax)/2,(ymin+ymax)/2).
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
impersonalis (01.12.2010), Randomize (01.12.2010)
Старый 01.12.2010, 12:10   #3
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Центр многоугольгика

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

__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
pax (01.12.2010), Randomize (01.12.2010)
Старый 01.12.2010, 13:54   #4
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: Центр многоугольгика

А мне кажется это не проблема. Не у всех тел центр в их полости. Даже центр масс так же может быть не в полости тела.
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Старый 01.12.2010, 14:03   #5
.Squid
Дэвелопер
 
Аватар для .Squid
 
Регистрация: 06.04.2009
Адрес: Запорожье
Сообщений: 1,500
Написано 1,011 полезных сообщений
(для 4,642 пользователей)
Ответ: Центр многоугольгика

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

(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Randomize (01.12.2010)
Старый 01.12.2010, 14:35   #6
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений
(для 9,330 пользователей)
Ответ: Центр многоугольгика

Центр масс находится емнип как среднее координат ограничивающих фигуру.
__________________
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
h1dd3n (01.12.2010)
Старый 01.12.2010, 21:32   #7
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,354
Написано 2,470 полезных сообщений
(для 6,850 пользователей)
Ответ: Центр многоугольгика

Ух. Уфф. Как же это в код перевести, то?
i - внизу - это циклический перебор.
rc - радиус вектор. Он в x и y или дистанция и угол поворота?
Моя не понимать ваши формулы. Где почитать, то как это перевести в код? Или кто вразумит нерадивого неуча псевдо кодом отличным?
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
(Offline)
 
Ответить с цитированием
Старый 01.12.2010, 21:51   #8
h1dd3n
Бывалый
 
Аватар для h1dd3n
 
Регистрация: 19.06.2008
Сообщений: 679
Написано 264 полезных сообщений
(для 450 пользователей)
Ответ: Центр многоугольгика

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);
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Randomize (01.12.2010)
Старый 01.12.2010, 21:57   #9
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,354
Написано 2,470 полезных сообщений
(для 6,850 пользователей)
Ответ: Центр многоугольгика

Лолшто? Тупо складываем все точки и делим на их кол-во?
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
(Offline)
 
Ответить с цитированием
Старый 01.12.2010, 22:06   #10
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Центр многоугольгика

ТЗ нечёткое: тебе нужен геометрический центр или центр масс?
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 01.12.2010, 22:09   #11
.Squid
Дэвелопер
 
Аватар для .Squid
 
Регистрация: 06.04.2009
Адрес: Запорожье
Сообщений: 1,500
Написано 1,011 полезных сообщений
(для 4,642 пользователей)
Ответ: Центр многоугольгика

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

(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Randomize (01.12.2010)
Старый 02.12.2010, 06:34   #12
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,354
Написано 2,470 полезных сообщений
(для 6,850 пользователей)
Ответ: Центр многоугольгика

Спасибо всем, вот что получилось:
<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,00,510,510,1015,1015,150,15];
            
FindCentroid(arr);
            
document.write('</fieldset>');

            
document.write('<fieldset> <legend>Square</legend>');
            
arr = [0,00,55,55,0];
            
FindCentroid(arr);
            
document.write('</fieldset>');

            
document.write('<fieldset> <legend>Triangle</legend>');
            
arr = [0,1010,1010,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
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо Randomize за это полезное сообщение:
Harter (02.12.2010), Mr_F_ (02.12.2010)
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


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


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com