Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.61
stark91
1 / 1 / 0
Регистрация: 07.05.2010
Сообщений: 55
#1

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

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

Нужно определить, находится ли точка в многоугольнике либо нет.
Как я понял надо задать луч проходящий через эту точку, и если будет нечетное кол-во пересечений
то точка находится внутри.
Вопрос: Нужно проверять пересечение луча с каждым отрезком из многоугольника?
т.е если в многоугольнике допустим 10 вершин, то надо сделать 10 проверок на пересечение?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.04.2011, 00:20     Метод трассировки луча
Посмотрите здесь:

пересечение луча и треугольника в пространстве Visual C++
Точка пересечения луча (прямой) с треугольником. C++
Метод деления отрезка пополам для решения нелинейных уравнений (метод дихотомии) C++
C++ Метод медиан из трех элементов VS улучшенный быстрый метод сортировки(метод Бентли-Макилроя)
Расстояние от точки до луча (описание внутри) C++
C++ Получение отражённого луча
C++ Builder Нужно заменить в исходном коде метод горизонтального луча на метод углов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.04.2011, 08:13     Метод трассировки луча #2
Трассировка лучей к этой задаче не относится. Трассировка лучей - это расчёт хода световых лучей в 3D сцене. Тебе же нужен геометрический луч, отличающийся от светового луча тем, что он прямой всегда и не подвержен ни рефракции, ни отражению, ни поглощению. Это совсем другое понятие луча и другие алгоритмы. Геометрический луч есть полупрямая, он описывается уравнением прямой и неравенством. Я предлагаю взять параметрическое уравнение прямой, тогда лучь описывается так: http://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}. Стороны прямоугольника - это отрезки, то есть тоже части прямых, они описываются так:
http://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}.
Тогда для каждого отрезка получаем систему: http://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 минуты
Можно ещё так: соединить точку со всеми вершинами и сложить углы между этими отрезками. Для внутренней точки должно получиться ровно http://www.cyberforum.ru/cgi-bin/latex.cgi?360^0, но там опять надо флоат сравнивать.

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

а на счет названия метода, вот ссылка http://algolist.manual.ru/maths/geom/belong/poly2d.php
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.04.2011, 05:41     Метод трассировки луча #4
Луч не может быть задан двумя координами. Если твоё пространство одномерно, то всякие лучи теряют смысл, луч должен иметь направление. Но тогда у тебя или плоскость, или трхёмерное пространство. Плоскость двумерна и две координаты на ней могут задавать положение только точки. А трёхмерное пространство - оно и в Африке трёхмерное, в нём двух координат не хватит даже на точку.

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

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

Не по теме:

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

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

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

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

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

Не по теме:

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

Deviaphan
28.04.2011, 13:42
  #9

Не по теме:

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

silent_1991
28.04.2011, 14:23
  #10

Не по теме:

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

Deviaphan
28.04.2011, 16:22
  #11

Не по теме:

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

silent_1991
28.04.2011, 16:28
  #12

Не по теме:

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

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2011, 16:33     Метод трассировки луча
Еще ссылки по теме:

C++ СЛАУ. Метод обратной матрицы, метод Гаусса, метод Крамера, метод Зейделя
Пересечение луча и отрезка C++
C++ Мой код - метод бисекции, метод секущих (метод хорд)
C++ Не сходится теория и практика метод Шелла и метод простого выбора
C++ Исследовать итерационный метод- метод касательных для решения нелинейных уравнений

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

Или воспользуйтесь поиском по форуму:
Deviaphan
28.04.2011, 16:33     Метод трассировки луча
  #13

Не по теме:

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

Yandex
Объявления
28.04.2011, 16:33     Метод трассировки луча
Ответ Создать тему
Опции темы

Текущее время: 03:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru