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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 675
Завершенные тесты: 1
#1

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

15.03.2014, 19:03. Просмотров 767. Ответов 12
Метки нет (Все метки)

Здравствуйте. Нужно найти координаты точки пересечения вектора(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++ Найти координаты точек пересечения двух кругов
Найти координаты точек пересечения прямой и окружности C++
Определить точки пересечения круга и прямоугольника C++
C++ Зная координаты углов прямоугольника, найти его периметр
Найти координаты точек пересечения окружности с экспонентой и сформировать из них множество А C++
Найти координаты точки пересечения высоты AH и высоты BG треугольника C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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++ Найти координаты точек пересечения параболы и экспоненты
Найти координаты четвертой вершины прямоугольника C++
Найти количество и координаты точек пересечения 2-х эллипсов C++
C++ Написать функцию проверки пересечения прямоугольника с окружностью

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

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

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