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

C++

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

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

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

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

Пересечение луча и отрезка - C++
Помогите решить задачу: пересекает ли луч отрезок. Дано: начало луча О(х0, y0); луч параллелен оси Ox, и сонаправлен с ней отрезок AB...

Получение отражённого луча - C++
Доброго времени суток. Проблема скорее с математикой, чем с программированием. Есть ф-ия, которая по отрезку и стрелке возвращает...

Пересечение луча и треугольника в пространстве - Visual C++
Нужно узнать пересекает ли луч треугольник в трехмерном пространстве, если да то в какой точке.Вывести на экран....старайтесь писать целый...

Точка пересечения луча (прямой) с треугольником. - C++
Как найти точку пересечения луча (прямой) с треугольником в пространстве? Добавлено через 4 часа 7 минут Как найти точку пересечения...

Расстояние от точки до луча (описание внутри) - C++
Помогите люди добрые :) Расстояние от точки до луча Даны координаты точки (x,y) и координаты начала и конца вектора (x1,y1) и (x2,y2). ...

Программа для нахождения общих точек отрезка и луча - C++
Программа для нахождения общих точек отрезка и луча. + в карму

метод отражений(метод Хаусхолдера - C++ Builder
Добрый день, товарищи программисты. Обращаюсь к вам за помощью. Задали написать программку по Решению СЛАУ различными методами. Вроде как с...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
Ушёл с форума.
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
Ушёл с форума.
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++
1286 / 1220 / 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++
Сгенерировать одномерный массив из N случайных чисел xi ∈. Отсортировать массив методом пузырька и методом слияния. Подсчитать число...

Метод оптимизации. Метод Фибоначчи - C++
Дан отрезок минимизации и точность минимизации Е=0.01. Помогите пожалуйста решить данную задачу. Вроде как то через цикл надо все это...

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

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

Алгоритм надежной трассировки - Алгоритмы
Есть задача: найти путь с точки А в точку В, но искать его надо в процессе движения (тоесть волновой алгоритм, Дейкстры и поисков в глубину...


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

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

Не по теме:

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

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

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