Отправляет email-рассылки с помощью сервиса Sendsay

Программирование. Форум !!!

Подписаться Бесплатный дискуссионный лист Подписчиков 308
←   Ноябрь 2005   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
10.11.2005
14:00:47
21:33:28
11
12
13
14
15
15.11.2005
04:18:32
06:38:07
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт листа: http://codeguru.ru
Открыт: 21-09-2003
Пре-модерация: Нет
Адрес для писем в лист: comp.soft.prog.prog-list@subscribe.ru
Адрес модератора: comp.soft.prog.prog-owner@subscribe.ru

Модератор
3V

Статистика

308 подписчиков
0 за неделю

Re: Персечение фигур

Hello,

Два или больше? (знаю что глупый вопрос :)
Прямоугольники произвольно ориентированы или стороны
параллельны осям (axis-aligned)?

Сорри, но не совсем понял, что имеется ввиду? Поясните, пожалуйста :)

Все-таки не понимаю чем именно может не устраивать просто проверить
пересечения соответствующих диапазонов по x и y, если они axis-aligned.
Если нет - то проверяем в какой стороне от каждой плоскости лежат вершины прямоугольника...

Так по крайней мере советуют вот здесь:
http://www.narod.ru/guestbook/index.xhtml?owner=12139292&c=18
только там был вопрос про пересечение двух кубов в трехмерном пространстве.

Про пересечения прямоугольников написано в книге А.Борескова по компьютерной
графике(в самой первой - Динамика, реалистичные изображения)

Другая полезная вещь - Препарата, Шаймос "Вычислительная геометрия":
http://algolist.manual.ru/maths/geom/prsh/

а именно - главы про пересечения:
http://algolist.manual.ru/download.php?path=/maths/geom/prsh/prsh7.zip

Там есть про пересечения двумерных и трехмерных (произвольных, разумеется, не
только прямоугольников и кубов :), метод "трапеций", метод "серпов" и другие.
Можно было бы их в кратце здесь изложить, но лучше посмотрите книгу :)

Good luck!

Best regards,
Alexey

Номер выпуска : 5039
Возраст листа : 781 (дней)
Количество подписчиков : 543
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/473043
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Ответить  
night_wolf
Thu, 10 Nov 2005 21:33:07 +0300 (#473043)

 

Ответы:

Здравствуйте, night_wolf,

В принципе приемлимое решение я уже нашел:
1. вычислить дХ и дУ между центров прямоугольников
2. вычислить суммы дХ и дУ от центра обоих прямоугольников
3. Сравнить сумму дХ(дУ) и дХ(дУ) между центрами.

Именно 2 прямоугольника.

Параллельны осям.

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

Можно проверять вершины, т.е. брать каждую вершину 2-го прямоугольника
и проверять ее на нахождение в области первого прямоугольника. Это 4
условных выражений.
Можно сверять не вершины, а грани - это 2 условных выражения.
Предложенный вариант использует одно условие.

Про книжки и ссылки - обязательно посмотрю... Нужно вспомнить, так
хорошо забытое.

Ответить  
Шистеров Павел
Fri, 11 Nov 2005 08:42:26 +0500 (#473263)

 

Hello, Павел

подскажите, пожалуйста: основную идею уловил, однако тем не менее можно взглянуть
на код?

Классно, простите, что лажанулся с такой простой задачей.
Это кстати можно потом на произвольно ориентированные
перенести, только сравнивая bounding-boxы.

Best regards,
Alexey

Номер выпуска : 5044
Возраст листа : 785 (дней)
Количество подписчиков : 544
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/474907
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Ответить  
night_wolf
Mon, 14 Nov 2005 12:26:50 +0300 (#474907)

 

Здравствуйте, night_wolf,

Есть код на ЛИСПе, но думаю тут будет уместнее формализованный(если я
правильно понял смысл) алгоритм, не привязанный к языку.

;Точки центра - можно считать по другому, просто высчитывая
координаты/
Входные данные: Область1 и область2
область = массив точек (Точка1,точка2)
Расчет:
ц1 - Центр Области1 - (точка - массив 2-х элементов или запись)
Хц1= (Х1Области1 + Х2Области1) / 2
Хц2= (Х1Области2 + Х2Области2) / 2
Уц1= (У1Области1 + У2Области1) / 2
Уц2= (У1Области2 + У2Области2) / 2
;dX и dY областей
дХ1 = (Хц1 + Х1Области1) / 2
дХ2 = (Хц2 + Х1Области2) / 2
дУ1 = (Уц1 + У1Области1) / 2
дУ2 = (Уц2 + У1Области2) / 2
SumX = дХ1 + дХ2
SumY = дУ1 + дУ2
;dX и dY между центрами
дХ = (Хц1 + Хц2) / 2
дУ = (Уц1 + Уц2) / 2
Пересекаются (<= дХ SumX) И (<= дУ SumY)

З.Ы. Возможно сам-бы дошел, но мне подсказали...

Ответить  
Шистеров Павел
Tue, 15 Nov 2005 08:25:53 +0500 (#475386)

 

Здарова, Шистеров!!!

Дык значит это на ЛИСПе сравнение дольше, чем операция?
Или вообще везде?
С трудом вериться, что везде. Точнее не вериться совсем. 8)
Откуда такая информация?

Счас вот даже не поленился попробовать и этот код:

int a=5;
int b=3;
int t1=GetTickCount();
for (int i=0; i<1000000000;++i){
a=b;
/*
if (a<b){
a=b;
}//*/
}
printf("%d",GetTickCount()-t1);
getc(stdin);
return 0;

показал, что в обоих случаях результат отличается незначительно.
И сравнение и приравнивание длиться где-то 0.2 секунды.

Номер выпуска : 5052
Возраст листа : 796 (дней)
Количество подписчиков : 551
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/480229
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru

Ответить  
Neco
Fri, 25 Nov 2005 03:12:45 +0500 (#480229)