|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
01.12.2010, 11:39
|
#1
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,359
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Центр многоугольгика
Есть массив, в котором друг за другом идут 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 за это полезное сообщение:
|
|
01.12.2010, 12:06
|
#2
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Центр многоугольгика
По моему тебе пришла на ум верная идея, где нет сложных вычислений, а одни сравнения, только в конце center((xmin+xmax)/2,(ymin+ymax)/2).
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
|
|
01.12.2010, 12:10
|
#3
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Центр многоугольгика
Проблема, возможно, будет только с вогнутыми многоугольниками: вычисленный по BoundingBox центр может оказаться вне фигуры
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
|
|
01.12.2010, 13:54
|
#4
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Центр многоугольгика
А мне кажется это не проблема. Не у всех тел центр в их полости. Даже центр масс так же может быть не в полости тела.
|
(Offline)
|
|
01.12.2010, 14:03
|
#5
|
Дэвелопер
Регистрация: 06.04.2009
Адрес: Запорожье
Сообщений: 1,500
Написано 1,011 полезных сообщений (для 4,642 пользователей)
|
Ответ: Центр многоугольгика
Описывающий четырёхугольник не катит. Это видно, даже глядя на твой первый пример.
Центроид - он же барицентр, совпадает с центром масс (если плотность однородная).
Попробуй применить первую формулу из http://ru.wikipedia.org/wiki/Центр_масс . Ниже не смотри - там как раз "загогулина такая намоминающая букву S".
__________________
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
01.12.2010, 14:35
|
#6
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: Центр многоугольгика
Центр масс находится емнип как среднее координат ограничивающих фигуру.
__________________
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
01.12.2010, 21:32
|
#7
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,359
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Центр многоугольгика
Ух. Уфф. Как же это в код перевести, то?
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
|
Бывалый
Регистрация: 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)
|
|
Сообщение было полезно следующим пользователям:
|
|
01.12.2010, 21:57
|
#9
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,359
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Центр многоугольгика
Лолшто? Тупо складываем все точки и делим на их кол-во?
__________________
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
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Центр многоугольгика
ТЗ нечёткое: тебе нужен геометрический центр или центр масс?
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
01.12.2010, 22:09
|
#11
|
Дэвелопер
Регистрация: 06.04.2009
Адрес: Запорожье
Сообщений: 1,500
Написано 1,011 полезных сообщений (для 4,642 пользователей)
|
Ответ: Центр многоугольгика
Сообщение от Randomize
Лолшто? Тупо складываем все точки и делим на их кол-во?
|
Собственно говоря, да.
Радиус-центр - вектор, задающий положения точки в пространстве относительно некоторой заранее фиксированной точки, называемой началом координат (Википедия).
Например, треугольник (4; 2) (2; 6) (5; 8). Барицентр - (3,667; 5,333). Можешь построить и убедиться.
__________________
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
02.12.2010, 06:34
|
#12
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,359
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Центр многоугольгика
Спасибо всем, вот что получилось:
<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
__________________
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 за это полезное сообщение:
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 07:52.
|