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=6806)

SBJoker

07.10.2008 18:24

Поворот массива точек

В принципе я понимаю, что задачка несложная, тут весь вопрос в методе и его красоте/скорости.

Дано: массив точек вида (х, y) расположеных в плоских координатах на плоскости.

Задача: повернуть всю систему вокруг любой выбраной из массива наобум точки.
Дополнительно: определить угол поворота всей плоскости относительно любой другой точки.

У кого какие мысли?

zheland

07.10.2008 18:51

Ответ: Поворот массива точек

Подвинуть матрицу на позицию осевой точки.
(Что-бы выбранная точка была в центре)
Повернуть матрицу.
Подвинуть матрицу обратно.

Первое, что в голову пришло. :)

SBJoker

07.10.2008 19:39

Ответ: Поворот массива точек

Мне кажется в этом случае результат будет неточным

Tadeus

07.10.2008 19:46

Ответ: Поворот массива точек

Цитата:

Сообщение от SBJoker (Сообщение 88089)

Мне кажется в этом случае результат будет неточным

Когда я смотрю на свиборга, мне кажется, что он смотрит на меня, как на дерьмо!

Сори, не удержался :lol:

impersonalis

07.10.2008 21:14

Ответ: Поворот массива точек

Чо-то кроме банальных тригнометрчиеских операций на ум ничего не идёт =\

dimanche13

08.10.2008 10:13

Ответ: Поворот массива точек

грабануть картинку, и поставив хендл в нужную точку, повернуть

zheland

08.10.2008 15:39

Ответ: Поворот массива точек

Цитата:

грабануть картинку, и поставив хендл в нужную точку, повернуть

Очень медленно; не точно.

SBJoker

08.10.2008 15:46

Ответ: Поворот массива точек

Товарищи в условии про картинку ничо несказано.

HolyDel

08.10.2008 15:58

Ответ: Поворот массива точек

SBJoker, вот, набросал пример:
http://www.forum.likosoft.ru/showthr...=newpost&t=321

1000 точек поворачивается быстро.
управление - навести на точку, зажать ЛКМ и возить мыша влево-вправо.

SBJoker

08.10.2008 17:44

Ответ: Поворот массива точек

Отлично. Надо придумать ещё что-нибудь занимательное..

zheland

08.10.2008 19:00

Ответ: Поворот массива точек

1)Удивительно: только-что проверил:

Код:

(x1-x2)*(x1-x2)

100 точек: время поворота на 360 градусов: 6037
быстрее чем:

Код:

(x1-x2)^2

100 точек: время поворота на 360 градусов: 6054

2)Вроде можно вычислить косинус из готового синуса угла быстрее,
чем вычислять новый.

HolyDel

08.10.2008 19:06

Ответ: Поворот массива точек

drunnik, мсье маньяк?
увеличение скорсти на 0.28 процента вполне укладывается в погрешность.

zheland

08.10.2008 19:30

Ответ: Поворот массива точек

А проверял раз 5:
В первом варианте было всегда 6037(один раз было 6036);
А во втором всегда 6054.
Это скорее не погрешность.

SBJoker

08.10.2008 19:48

Ответ: Поворот массива точек

Цитата:

Сообщение от drunnik (Сообщение 88261)

2)Вроде можно вычислить косинус из готового синуса угла быстрее,
чем вычислять новый.

Неверно, на современном этапе развития процессор вычисляя Синус и Косинус тратит времени меньше чем тратится при доступе к памяти чтобы прочитать готовое значение.

jimon

08.10.2008 20:38

Ответ: Поворот массива точек

SBJoker
а cos и sin одного угла можно вообще одной операцией посчитать

Код:

inline void jeSinCos(float Angle,float & SinValue,float & CosValue )

{

__asm

{

fld Angle;

fsincos;

mov eax,[CosValue];

fstp [eax];

mov eax,[SinValue];

fstp [eax];

}

}

zheland

08.10.2008 21:22

Ответ: Поворот массива точек

Цитата:

Сообщение от jimon (Сообщение 88268)

SBJoker
а cos и sin одного угла можно вообще одной операцией посчитать

Это я и имел в виду.
Оно вроде быстрее.

Цитата:

Сообщение от SBJoker (Сообщение 88265)

Нет.
Прочитать готовое значение—1 такт.
Синус и Косинус—241(193-279) тактов на процессоре i80486.
Но я думаю немогло это так быстро уменьшится.
Потом я читал что где-то даже увеличивалась.
Во первых сложная операция, во вторых сопроцессор(FPU) работает медленней процессора.

SBJoker

08.10.2008 21:49

Ответ: Поворот массива точек

Блин ну проверь, что быстрее будет выборка по таблице или расчёт на месте. И сам удивишся но выборка из заранее просчитаного массива проигрывает и оч. сильно.

Ибо! Расчёт син и кос на совр процессоре с частотой пусть 2000Mhz занимает хоть и много тактов, но они проводятся со скоростью 2000Mhz, а выборка из памяти ДДР-2 при частоте 400 Mhz, уже проигрывает в скорости в 5 раз на такт, но чтобы прочитать из памяти нежен не один такт! а несколько! А именно суммируем все 4 основновные задержки у меня это 4-4-4-16 в сумме(28нс) так что нетрудно догадаться что чтение займёт больше.

Вот если таблицу синусов загнать в кэш процессора то да, скорость будет намного больше вычисления.

Кароче сделай тест, который считает пару десятков тысяч синусов, и берущий из таблицы алгоритм. На современном компе быстрее будет расчёт. На древнем 486м быстрее будет из таблицы.

З.Ы. значения из таблицы так же сильно проигрывают в точности, т.к. расчёт таблицы ведётся с опр. шагом, и код функции выбирающий ближайшее значение так же внесёт вклад в задержки.

jimon

08.10.2008 21:50

Ответ: Поворот массива точек

drunnik
в последнее время в x86 процессорах архитектура поменялась, теперь в центре стоит risc ядро, а вокруг него обвязка x86 выполненая в большей части на микрокоде
потому такт как рабочая единица сложно применима, да и данные для 80486 слишком сильно устарели
а выборка из масива, да, зачастую медленее расчёта на процессоре

Черный крыс

10.10.2008 14:48

Ответ: Поворот массива точек

Тоже сначала сильно удивилсо....когда увидел результаты тестов Оксида в модуле oxi.SinCos. Провел независимое тестирование....это подтвердилось. Теперь тока на проце и щитаю....стараясь - где нужно сразу юзать sincos().

Если Джокеру надо повернуть полигон, вершины которого загнаны в массив, - SetRotation ? Полигон можно хэндлить. а насчет 2-го то тут уже чистая математика.

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