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

Найти координаты пересечения вектора и прямоугольника - C++

Восстановить пароль Регистрация
 
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
15.03.2014, 19:03     Найти координаты пересечения вектора и прямоугольника #1
Здравствуйте. Нужно найти координаты точки пересечения вектора(VX0,VY0,VZ0,VX1,VY1,VZ1) с прямоугольником (PX0,PY0,PZ0,PX1,PY1,PZ1,PX2,PY2,PZ2,PX3,PY3,PZ3) и сделать это "быстрым" алгоритмом.

Добавлено через 2 минуты
Прямоугольник можно задать и по-другому, если это оправдает алгоритм. Например, не координатами вершин, а длинной и шириной+углы поворота прямоугольника вокруг центра - не важно, лишь бы быстро.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.03.2014, 19:03     Найти координаты пересечения вектора и прямоугольника
Посмотрите здесь:

C++ По трем вершинам прямоугольника найти координаты четвертой
C++ Найти координаты точек пересечения двух кругов
Вычислительная геометрия (Даны координаты центра, R окружности, координаты точки вне окруж-ти. Найти точку пересечения одной из касательных с окруж-ю) C++
C++ классы (имеются координаты углов прямоугольника, найти периметр)
Найти координаты вершины прямоугольника, зная одну из них C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
15.03.2014, 21:32     Найти координаты пересечения вектора и прямоугольника #2
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}(vx_1-vx_0)t = (px_1-px_0)u + (px_3-px_0)v\\ (vy_1-vy_0)t = (py_1-py_0)u + (py_3-py_0)v\\ (vz_1-vz_0)t = (pz_1-pz_0)u + (pz_3-pz_0)v\end{cases}
3 уравнения с 3 неизвестными.
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{pmatrix}x\\y\\z\end{pmatrix} =\begin{pmatrix}vx_0\\vy_0\\vz_0\end{pmatrix} + \begin{pmatrix}vx_1-vx_0\\vy_1-vy_0\\vz_1-vz_0\end{pmatrix}t
Вроде так.

Добавлено через 4 минуты
Да, и они пересекаются, если 0 <= t,u,v <=1.
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
15.03.2014, 22:11  [ТС]     Найти координаты пересечения вектора и прямоугольника #3
Спасибо! А нельзя ли в стандартной форме?
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
15.03.2014, 23:34     Найти координаты пересечения вектора и прямоугольника #4
Что значит "в стандартной форме"?
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
15.03.2014, 23:58  [ТС]     Найти координаты пересечения вектора и прямоугольника #5
Цитата Сообщение от Somebody Посмотреть сообщение
Что значит "в стандартной форме"?
Мне показалось, что здесь матрицы, а я с ними не дружу. Уравнения мне больше по душе.

На банальном примере: начало вектора совпадает с началом координат (0,0,0), вектор направлен по оси Z, т.е., пусть (0,0,100). Ширина и длина, для примера, равны по 101 у.е., т.е. вершины прямоугольника, например: (-50,-50,100),(50,-50,100),(50,50,100),(-50,50,100). Как эти числа по вышенаписанной формуле преобразуются к точке (0,0,100)?

Я не понимаю что есть t u v...можете меня запинать в незнании основ, но если сможете объяснить так, чтобы я понял, то буду безумно благодарен.

Добавлено через 1 минуту
Все вычисления на CPU, поэтому вся математика последовательная, хотя, понимаю, что такие вычисления, пожалуй, адекватнее было бы использовать на GPU
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
16.03.2014, 11:59     Найти координаты пересечения вектора и прямоугольника #6
Точнее, там
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}(vx_1-vx_0)t = px_0 + (px_1-px_0)u + (px_3-px_0)v\\ (vy_1-vy_0)t = py_0 + (py_1-py_0)u + (py_3-py_0)v\\ (vz_1-vz_0)t = pz_0 + (pz_1-pz_0)u + (pz_3-pz_0)v\end{cases}
Получается что-то типа
http://www.cyberforum.ru/cgi-bin/latex.cgi?t = \frac{vx01 \cdot (py01 \cdot pz03 - py03 \cdot pz01) + px01 \cdot (-vy01 \cdot pz03 + py03 \cdot vz01) - px03 \cdot (-vy01 \cdot pz01 + py01 \cdot vz01)}{px0 \cdot (py01 \cdot pz03 - py03 \cdot pz01) + px01 \cdot (-py0 \cdot pz03 + py03 \cdot pz0) - px03 \cdot (-py0 \cdot pz01 + py01 \cdot pz0)}\\x=vx0+vx10 \cdot t\\y=vy0+vy10 \cdot t\\z=vz0+vz10 \cdot t
где vx01 = vx1 - vx0 и т. п.
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Все вычисления на CPU, поэтому вся математика последовательная
Если нужно, есть SIMD инструкции у CPU.
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
16.03.2014, 13:22  [ТС]     Найти координаты пересечения вектора и прямоугольника #7
Цитата Сообщение от Somebody Посмотреть сообщение
Получается что-то типа
где vx01 = vx1 - vx0 и т. п.
Вот я и спрашиваю, Вы уверены, что это быстро?

Добавлено через 10 минут
Цитата Сообщение от Somebody Посмотреть сообщение
Если нужно, есть SIMD инструкции у CPU
Да, я об этом слышал)
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
16.03.2014, 14:09     Найти координаты пересечения вектора и прямоугольника #8
Не знаю, насколько это оптимально - просто это то, что в голову пришло пока.
Насчёт оптимального представления и математического решения - это скорее в математический раздел, а не C++.
Что касается самого метода решения системы уравнений, это чисто для примера, тут можно и лучше сделать. Например, если всё правильно выразил:
http://www.cyberforum.ru/cgi-bin/latex.cgi?t = \frac{vx_{01} \cdot (py_{01} \cdot pz_{03} - py_{03} \cdot pz_{01}) - vy_{01} \cdot (px_{01} \cdot pz_{03} - px_{03} \cdot pz_{01}) + vz_{01} \cdot (px_{01} \cdot py_{03} - px_{03} \cdot py_{01})}{px_{0} \cdot (py_{01} \cdot pz_{03} - py_{03} \cdot pz_{01}) - py_{0} \cdot (px_{01} \cdot pz_{03} - px_{03} \cdot pz_{01}) + pz_{0} \cdot (px_{01} \cdot py_{03} - px_{03} \cdot py_{01})}
Тут подвыражения в скобках одинаковые и не зависят от координат векторов, так что их можно хранить вместе с координатами прямоугольников, если это имеет смысл.
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
16.03.2014, 14:23  [ТС]     Найти координаты пересечения вектора и прямоугольника #9
Цитата Сообщение от Somebody Посмотреть сообщение
если это имеет смысл
Имеете. Прямоугольников не много, а векторов уйма. Спасибо! Буду пытаться ещё оптимизировать.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
16.03.2014, 14:33     Найти координаты пересечения вектора и прямоугольника #10
Да, я забыл, что тут не бесконечные плоскости, а ограниченные прямоугольники. Так что надо u и v аналогично найти, чтобы проверить, что они от 0 до 1. Но там скобки тоже не будут зависеть от векторов.

Добавлено через 1 минуту
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Я не понимаю что есть t u v...
t - координата точки на прямой, на которой вектор. При t=0 это начало вектора, при t=1 - конец.
u, v - координаты точки на плоскости, в которой прямоугольник. (0;0), (1;0), (1;1), (0;1) - вершины.
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
16.03.2014, 16:01  [ТС]     Найти координаты пересечения вектора и прямоугольника #11
Цитата Сообщение от Somebody Посмотреть сообщение
что они от 0 до 1
Мы говорим о CPU. Нет ли в данном направлении целочисленной математики?
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
16.03.2014, 16:41     Найти координаты пересечения вектора и прямоугольника #12
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Мы говорим о CPU. Нет ли в данном направлении целочисленной математики?
Зачем? Вещественная математика по скорости сейчас почти такая же, как и целочисленная. Даже если каким-то извращённым способом можно приделать целочисленную математику, от этого скорее только потеряешь на всяких преобразованиях.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2014, 18:22     Найти координаты пересечения вектора и прямоугольника
Еще ссылки по теме:

C++ Найти координаты точек пересечения параболы и экспоненты
Найти координаты четвертой вершины прямоугольника C++
Найти количество и координаты точек пересечения 2-х эллипсов C++

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

Или воспользуйтесь поиском по форуму:
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
16.03.2014, 18:22  [ТС]     Найти координаты пересечения вектора и прямоугольника #13
Цитата Сообщение от Somebody Посмотреть сообщение
от этого скорее только потеряешь на всяких преобразованиях
Ну есть идея, как отказаться от преобразований вообще. Спасибо за помощь, буду реализовывать.
Yandex
Объявления
16.03.2014, 18:22     Найти координаты пересечения вектора и прямоугольника
Ответ Создать тему
Опции темы

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