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

C++

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

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

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

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

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
taras atavin
Ушёл с форума.
3569 / 1753 / 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 проверок на пересечение?
Конечно.
1
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
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.04.2011, 05:41 #4
Луч не может быть задан двумя координами. Если твоё пространство одномерно, то всякие лучи теряют смысл, луч должен иметь направление. Но тогда у тебя или плоскость, или трхёмерное пространство. Плоскость двумерна и две координаты на ней могут задавать положение только точки. А трёхмерное пространство - оно и в Африке трёхмерное, в нём двух координат не хватит даже на точку.

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

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

Не по теме:

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

0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
28.04.2011, 07:13 #6
Можно и радиолучи трассировать, но луч в геометрии и в оптике с акустикой - разные лучи. Геомерический луч не отражается, не поглощается, не преломляется, не рассеивается. Можно провести аналогию оптики с аккустикой, расширить оптику на ИК, ультрафиолет, радиоволны, может быть даже на рентген и гамма лучи. Всё это одна задача: даны сцена, ракурс и волны, надо расчитать, как в этом ракурсе и в этих волнах эта сцена выглядит. А пули - это баллистика, там другие законы отклонения и рикошета. В геометрии же их вообще нет.
Цитата Сообщение от Deviaphan Посмотреть сообщение
Луч - это точка (2Д, 3Д - не важно) и направление.
. Так вот, для того, чтоб задать точку уже нужны как минимум две, а в 3D даже три координаты, плюс направление, а оно в 2D - одна полярная координата, а в 3D - две сферические. Итого, в 2D луч определяется тремя, а в 3D пятью координатами, а никак не двумя. Если же луч в четырёхмерном гиперспространстве, то он уже задаётся семью координатами. Общая формула 2n-1, где n - размерность пространства.
0
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1287 / 1221 / 50
Регистрация: 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2011, 16:33
Привет! Вот еще темы с ответами:

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

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

Метод медиан из трех элементов VS улучшенный быстрый метод сортировки(метод Бентли-Макилроя) - C++
Здравствуйте! Дали весьма интересное задание. Сравнить два вышеуказанных метода сортировки для массива из 10000 элементов, результаты...

Мой код - метод бисекции, метод секущих (метод хорд) - C++
Всем привет!!! Изучаем в институте С++. Сделал код, и там, и там одна и та же проблема - при любых вбиваемых значениях программа делает...


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

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

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