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

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

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

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

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

Здравствуйте. Нужно найти координаты точки пересечения вектора(VX0,VY0,VZ0,VX1,VY1,VZ1) с прямоугольником (PX0,PY0,PZ0,PX1,PY1,PZ1,PX2,PY2,PZ2,PX3,PY3,PZ3) и сделать это "быстрым" алгоритмом.

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

Вычислительная геометрия (Даны координаты центра, R окружности, координаты точки вне окруж-ти. Найти точку пересечения одной из касательных с окруж-ю) - C++
Даны координаты центра (xc,yc) и радиус R окружности, координаты точки (x,y) вне окружности. Найти точку пересечения одной из касательных с...

Найти координаты точек пересечения - C++
Для заданной окружности и луча в плоскости определить, пересекает ли луч окружность. Найти координаты точек пересечения. На ввод...

Найти координаты четвертой вершины прямоугольника - C++
У меня задание такое: Даны целочисленные координаты трех вершин прямоугольника, стороны которого параллельны координатным осям. Найти...

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

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

Найти координаты точек пересечения параболы и экспоненты - C++
Есть два задания, которые так и не смог осилить (с остальными справился) Очень нужна помощь. 1 . С клавиатуры пользователь вводит...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 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.
1
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
15.03.2014, 22:11  [ТС] #3
Спасибо! А нельзя ли в стандартной форме?
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
15.03.2014, 23:34 #4
Что значит "в стандартной форме"?
0
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 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
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 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.
0
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
16.03.2014, 13:22  [ТС] #7
Цитата Сообщение от Somebody Посмотреть сообщение
Получается что-то типа
где vx01 = vx1 - vx0 и т. п.
Вот я и спрашиваю, Вы уверены, что это быстро?

Добавлено через 10 минут
Цитата Сообщение от Somebody Посмотреть сообщение
Если нужно, есть SIMD инструкции у CPU
Да, я об этом слышал)
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 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})}
Тут подвыражения в скобках одинаковые и не зависят от координат векторов, так что их можно хранить вместе с координатами прямоугольников, если это имеет смысл.
1
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
16.03.2014, 14:23  [ТС] #9
Цитата Сообщение от Somebody Посмотреть сообщение
если это имеет смысл
Имеете. Прямоугольников не много, а векторов уйма. Спасибо! Буду пытаться ещё оптимизировать.
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 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) - вершины.
0
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
16.03.2014, 16:01  [ТС] #11
Цитата Сообщение от Somebody Посмотреть сообщение
что они от 0 до 1
Мы говорим о CPU. Нет ли в данном направлении целочисленной математики?
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
16.03.2014, 16:41 #12
Цитата Сообщение от Retyrn0 Посмотреть сообщение
Мы говорим о CPU. Нет ли в данном направлении целочисленной математики?
Зачем? Вещественная математика по скорости сейчас почти такая же, как и целочисленная. Даже если каким-то извращённым способом можно приделать целочисленную математику, от этого скорее только потеряешь на всяких преобразованиях.
0
Retyrn0
45 / 45 / 3
Регистрация: 24.06.2013
Сообщений: 677
Завершенные тесты: 1
16.03.2014, 18:22  [ТС] #13
Цитата Сообщение от Somebody Посмотреть сообщение
от этого скорее только потеряешь на всяких преобразованиях
Ну есть идея, как отказаться от преобразований вообще. Спасибо за помощь, буду реализовывать.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2014, 18:22
Привет! Вот еще темы с ответами:

Найти координаты точек пересечения прямой и окружности - C++
Найти координаты точек пересечения прямой y=kx+b и окружности радиуса R с центром в начале координат. В каких координатных четвертях...

Найти количество и координаты точек пересечения 2-х эллипсов - C++
Нужно найти точки пересечения 2-х эллипсов заданных уравнениями вида: (x-x1)2/a12+(y-y1)2/b12=1 (x-x2)2/a22+(y-y2)2/b22=1 нужно...

По трем вершинам прямоугольника найти координаты четвертой - C++
Доброго времени суток! Помогите плз сделать эти задания на с++ в Builder XE 2 4. По известным трем вершинам прямоугольника (X1, Y1),...

Пересекаются ли прямые, и, если да, то найти координаты точки пересечения - C++
Ввод состоит из координат точек прямых (две точки - первая прямая, ещё две - вторая прямая). Так как это прямые, то ситуаций может...


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

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

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