Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.70/43: Рейтинг темы: голосов - 43, средняя оценка - 4.70
1 / 1 / 1
Регистрация: 07.05.2010
Сообщений: 55
1

Метод трассировки луча

19.04.2011, 00:20. Просмотров 8077. Ответов 12
Метки нет (Все метки)

Нужно определить, находится ли точка в многоугольнике либо нет.
Как я понял надо задать луч проходящий через эту точку, и если будет нечетное кол-во пересечений
то точка находится внутри.
Вопрос: Нужно проверять пересечение луча с каждым отрезком из многоугольника?
т.е если в многоугольнике допустим 10 вершин, то надо сделать 10 проверок на пересечение?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.04.2011, 00:20
Ответы с готовыми решениями:

Нужно заменить в исходном коде метод горизонтального луча на метод углов
#pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; #include <vcl.h> #pragma...

Какие эффекты нельзя получить при использовании трассировки луча?
Помогите найти ответ на вопрос?! Какие эффекты ты не сможешь получить при использовании трассировки...

Какова степень поляризации отраженного луча, если угол падения светового луча на границу раздела двух диэлектриков равен углу Брюстера?
Подскажите как решить задачку

Лучевой алгоритм трассировки
Приветствую вас, коллеги, встал такой вопрос. Нужна реализация лучевого алгоритма трассировки на...

12
4194 / 1787 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
20.04.2011, 08:13 2
Трассировка лучей к этой задаче не относится. Трассировка лучей - это расчёт хода световых лучей в 3D сцене. Тебе же нужен геометрический луч, отличающийся от светового луча тем, что он прямой всегда и не подвержен ни рефракции, ни отражению, ни поглощению. Это совсем другое понятие луча и другие алгоритмы. Геометрический луч есть полупрямая, он описывается уравнением прямой и неравенством. Я предлагаю взять параметрическое уравнение прямой, тогда лучь описывается так: https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}  x=x_0+k_x*t  \\   y=y_0+k_y*t  \\  t\geq 0 \end{cases}. Стороны прямоугольника - это отрезки, то есть тоже части прямых, они описываются так:
https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}  x=x_0+k_x*t  \\   y=y_0+k_y*t  \\  t\geq 0 \\  t\leq 1 \end{cases}.
Тогда для каждого отрезка получаем систему: https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}  x=xl_0+kl_x*tl  \\   y=yl_0+kl_y*tl  \\  x=xo_0+ko_x*to  \\   y=yo_0+ko_y*to  \\  to\geq 0 \\  tl\geq 0 \\  tl\leq 1 \end{cases}. Число точек должно быть не чётным, а для выпуклого многоугольника точка должна быть ровно одна, но если попадёшь в угол, то такая точка принадлежит двум отрезкам и может сосчитаться дважды. Придумай, как надёжно обработать углы.

Добавлено через 4 минуты
Можно ещё так: соединить точку со всеми вершинами и сложить углы между этими отрезками. Для внутренней точки должно получиться ровно https://www.cyberforum.ru/cgi-bin/latex.cgi?360^0, но там опять надо флоат сравнивать.

Добавлено через 3 минуты
Цитата Сообщение от stark91 Посмотреть сообщение
т.е если в многоугольнике допустим 10 вершин, то надо сделать 10 проверок на пересечение?
Конечно.
1
1 / 1 / 1
Регистрация: 07.05.2010
Сообщений: 55
21.04.2011, 03:53  [ТС] 3
А если у меня луч задан двумя координатами, как можно вычислить пересечение с другим таким же лучем заданным с помощью двух точек ?
Цитата Сообщение от taras atavin Посмотреть сообщение
Можно ещё так: соединить точку со всеми вершинами и сложить углы между этими отрезками. Для внутренней точки должно получиться ровно 360 , но там опять надо флоат сравнивать.
с флотом не вариант так как будут погрешности, а так большое спасибо

а на счет названия метода, вот ссылка http://algolist.manual.ru/math... poly2d.php
0
4194 / 1787 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
27.04.2011, 05:41 4
Луч не может быть задан двумя координами. Если твоё пространство одномерно, то всякие лучи теряют смысл, луч должен иметь направление. Но тогда у тебя или плоскость, или трхёмерное пространство. Плоскость двумерна и две координаты на ней могут задавать положение только точки. А трёхмерное пространство - оно и в Африке трёхмерное, в нём двух координат не хватит даже на точку.

Добавлено через 1 минуту
Цитата Сообщение от stark91 Посмотреть сообщение
с флотом не вариант так как будут погрешности, а так большое спасибо
А ты интом собрался? Получишь суперпогрешности, так как величины задачи все вещественные, чтоб получить инт их надо округлять, а при округлении вносится погрешность округления.

Добавлено через 2 минуты
Цитата Сообщение от stark91 Посмотреть сообщение
а на счет названия метода, вот ссылка
А если я на своём сайте двоичное дерево назову пятеричным хвостогрызом, а потом буду раздавать на него ссылки? В трассеровке лучей, причём, именно лучей во множественном числе, а не луча, лучи принимаются световыми, а у тебя геометрия.
0
Deviaphan
27.04.2011, 11:13
  #5

Не по теме:

Что вы к свету прикопались? При вычислении распространения звука тоже трассировка лучей происходит. Пули когда пуляете, тоже трассировка луча...
Луч - геометрическое понятие. Луч - это точка (2Д, 3Д - не важно) и направление.

0
4194 / 1787 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
28.04.2011, 07:13 6
Можно и радиолучи трассировать, но луч в геометрии и в оптике с акустикой - разные лучи. Геомерический луч не отражается, не поглощается, не преломляется, не рассеивается. Можно провести аналогию оптики с аккустикой, расширить оптику на ИК, ультрафиолет, радиоволны, может быть даже на рентген и гамма лучи. Всё это одна задача: даны сцена, ракурс и волны, надо расчитать, как в этом ракурсе и в этих волнах эта сцена выглядит. А пули - это баллистика, там другие законы отклонения и рикошета. В геометрии же их вообще нет.
Цитата Сообщение от Deviaphan Посмотреть сообщение
Луч - это точка (2Д, 3Д - не важно) и направление.
. Так вот, для того, чтоб задать точку уже нужны как минимум две, а в 3D даже три координаты, плюс направление, а оно в 2D - одна полярная координата, а в 3D - две сферические. Итого, в 2D луч определяется тремя, а в 3D пятью координатами, а никак не двумя. Если же луч в четырёхмерном гиперспространстве, то он уже задаётся семью координатами. Общая формула 2n-1, где n - размерность пространства.
0
Делаю внезапно и красиво
Эксперт С++
1309 / 1224 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
28.04.2011, 07:28 7
Цитата Сообщение от taras atavin Посмотреть сообщение
Общая формула 2n-1, где n - размерность пространств
Так с этим, кроме ТС, проблем и нету ни у кого.)

А вот если строго задан угол, под которым строится луч, то вполне можно обойтись и одной точкой (например, для горизонтали/вертикали). Только этот угол тоже знать нужно.)

Цитата Сообщение от taras atavin Посмотреть сообщение
В геометрии же их вообще нет.
Угол падения равен углу отражения. Это геометрия.)

А вообще, трассировка луча это просто проверка того, с чем и где этот луч взаимодействует. И в данном контексте "Луч", действительно, не геометрическое понятие, т.к. он имеет произвольный закон построения. Может быть геометрическим лучом, как у ТС. Может отражаться. Может иметь ограниченную длину. Много чего может.
0
silent_1991
28.04.2011, 13:29
  #8

Не по теме:

Цитата Сообщение от Deviaphan Посмотреть сообщение
Угол падения равен углу отражения. Это геометрия
Да ну... А не физика?

0
Deviaphan
28.04.2011, 13:42
  #9

Не по теме:

Цитата Сообщение от silent_1991 Посмотреть сообщение
Да ну... А не физика?
Физика, использующая геометрию!
Математика - царица наук!
Кукуруза - царица полей!

0
silent_1991
28.04.2011, 14:23
  #10

Не по теме:

Deviaphan, в геометрии разве существует понятие отражения?

0
Deviaphan
28.04.2011, 16:22
  #11

Не по теме:

Но ведь вычисляется оно при помощи геометрии/тригонометрии! .)

0
silent_1991
28.04.2011, 16:28
  #12

Не по теме:

Deviaphan, ну и что))) Есть физическое правило "Угол падения равен углу отражения" и есть тригонометрические способы вычисления углов. Понятия "отражение" в геометрии нет.

0
Deviaphan
28.04.2011, 16:33     Метод трассировки луча
  #13

Не по теме:

}{очу в школу.(

0
28.04.2011, 16:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2011, 16:33
Привет! Вот еще темы с ответами:

Заполнить таблицу трассировки
Имеется блок – схема алгоритма подсчёта десятичных разрядов в заданном положительном числе N. ...

Заполнить таблицу трассировки
Имеется блок – схема алгоритма подсчёта десятичных разрядов в заданном положительном числе N. ...

Лучевой алгоритм трассировки
Приветствую вас, коллеги, встал такой вопрос. Нужна реализация лучевого алгоритма трассировки на...

Алгоритм надежной трассировки
надо реализовать программу, которая ищет путь между двумя точками используя алгоритм надежной...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.