Форум программистов, компьютерный форум, киберфорум
Геометрия
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
Автор FAQ
3682 / 959 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
1

Точки массива входящие в перпендикуляр

19.04.2010, 22:40. Просмотров 1658. Ответов 13
Метки нет (Все метки)

Точки массива входящие в перпендикуляр

Вопрос связанный с геометрией которая строится в дискретном пространстве (игровом).
Дан двумерный массив проходимости - map[Y][X]. Есть две точки А и Б. Между ними проводится линия, нужно найти первую (ab1) и вторую точку входа в препятствие (ab2) этой линией. Затем найти среднюю между ними точку (dab). Все вышеописанное мне кажется не таким сложным, а вот дальше... Нужно построить перпендикуляр к отрезку АБ в точке dab (в какую его сторону выводить пока что не важно). А потом найти первую свободную точку которую пересекает этот перпендикуляр. Дискретные точки пересечения я пометил крестиками. Как бы их получить?
Единственная идея которая мне пока пришла это создать массив
C++
1
2
3
4
5
6
7
8
9
#define D3DX_PI 3.141592653
#define D3DXToRadian( degree ) ((degree) * (D3DX_PI / 180.0f))
#define D3DXToDegree( radian ) ((radian) * (180.0f / D3DX_PI))
    point dg_points[360];
    for (int i = 0; i < 360; i++)
    {
        if ( i > 178 ) dg_points[i].x = -4; else dg_points[i].x = 4;
        dg_points[i].y =(int)( (double)dg_points[i].x * tan(ToRadian((double)i)));
    }
Где на каждый градус будет указываться точка - перемещение для прохода по такой траектории. Например для 45 градусов это будет точка {4, 4} (т.е. если мы пойдем из текущей точки на 4 точки влево и вверх то угол между начальной и конечной точкой будет как раз 45 градусов. Однако никак не соображу как это все связать вместе, да и кажется не точно выйдет, а может вообще есть метод попроще? Конечная цель напомню именно дискретные координаты. В конкретном случае требовалось бы найти точку {8, 5}

PS. Тема так же связана собственно с продумыванием алгоритма, так что если по геометрической части идей долгое время не будет прошу перенести тему в алгоритмы
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.04.2010, 22:40
Ответы с готовыми решениями:

Перпендикуляр к пространственной прямой из точки
Дано: Прямая в 3-х-мерном Декартовом пространстве в каноническом виде: (x-x0)/ax = (y-y0)/ay =...

Можно ли провести перпендикуляр из точки к прямой ?
Есть точка (x0; y0) и прямая ((x1; y1), (x2; y2)), как можно проверить, можно ли из точки провести...

Из заданной точки восстановить перпендикуляр к диаметру
Специально для Байта, а также всех экспертов в области аналитической геометрии, простая задача. ...

Найдите перпендикуляр, опущенный из точки на плоскость.
Помогите решить задачу,пожалуйста! Зарание спасибо!

13
42 / 24 / 3
Регистрация: 16.03.2010
Сообщений: 199
19.04.2010, 22:52 2
блин, давно геометрия была... короче, перпендикуляр это тоже прямая и как и всякая прямая задается уравнением, точки ты конечно крупные выбрал)))для прямой, соединяющей две точки с задаными координатами сможешь уравнение составить? потом перпендикуляр в средней точке (то есть, перпендикуляр, проходящий через точку с задаными координатами). зная уравнение прямой и координаты границы просчитаешь точку выхода. +1 - то что тебе надо
0
Автор FAQ
3682 / 959 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
19.04.2010, 23:11  [ТС] 3
Цитата Сообщение от delfamur Посмотреть сообщение
зная уравнение прямой и координаты границы
Так я же границу как раз и ищу, она же и есть точка выхода. Заморочился я сегодня с этой проблемой что то не соображу совсем Если имеется ввиду граница препятствия то она не известна, вот как раз чтобы найти её надо проложить точки к ней...
0
42 / 24 / 3
Регистрация: 16.03.2010
Сообщений: 199
19.04.2010, 23:13 4
не пойму тогда - что дано тебе?))
0
Автор FAQ
3682 / 959 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
19.04.2010, 23:19  [ТС] 5
Всего лишь двумерный массив и две точки (А и Б) указывающие на координаты в нем, фактически контуры препятствий это абстракция которая видна лишь на рисунке, а так там просто массив который содержит данные открыта эта точка или нет
0
42 / 24 / 3
Регистрация: 16.03.2010
Сообщений: 199
20.04.2010, 10:34 6
пододжи, а границы препятствия ты по рисунку определяешь? если да, то это тоже отрезки прямых простых функций типа x=a, y=b. приравнивая с той функцией, которой ты задашь прямую, соединяющую две точки, ты получишь точки входа и выхода. ну и так далее, как описал вначале
0
3128 / 1321 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
20.04.2010, 18:32 7
insideone, твоя проблема в том, и это я уже не раз замечал, что ты выражаешся языком программиста, который хорошо разбирается в том о чем он говорит, но делает это так, как-будто его собеседник не хуже него посвящен в суть задачи.
Я толком ничего не понял из твоего условия. Скажи, как было бы людям, если бы я им отвечал языком кванторов и чистых формул? Обьясни нормально, с точки зрения математики, что ты хочеш.
Также и в прошлый раз, тебе просто нужно было уравнение кривой, а ты начал и то и сё, и так и так. Где-то на посту 15-ом я только понял, что ты хочешь. Будь проще - и люди к тебе потянутся
0
Автор FAQ
3682 / 959 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
20.04.2010, 21:56  [ТС] 8
Eugeniy, я вот и не знаю как подступиться, особенно что касается геометрии. Попробую по рисунку: есть точка A{2, 7} и точка Б{4, 0}. Мне нужно найти угол (оносительно оси X или Y... не важно пока что) отрезка AБ + получить такой единичный вектор который можно прибавлять допустим к точке А и будет получаться новая точка на отрезке АБ. Благодаря этому найдутся точки ab1 и ab2 потом и средняя между ними точка. После этого мне нужно будет получить такой единичный вектор который позволит идти по отрезку (на рисунке перпендикуляр от АБ) так же как это делалось в случае с нахождением точек ab1 и ab2.
Так уже лучше?
0
3128 / 1321 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
20.04.2010, 22:39 9
insideone, так даже на очень много лучше
Начнем с угла. Это элементарно. Находишь направляющий вектор своей прямой - просто от точки В отнимаешь скажем точку А. Далее выбераешь угл с какой осью тебе нужен. Направляющий вектор осей координат (1 , 0) для оси OX и (0 , 1) для оси OY. Далее работает формула
косинус угла между векторами a , b и с координатами (a1,a2) и (b1,b2) равен
= (a1*a2 + b1*b2)/sqrt(a1^2+a2^2)*sqrt(b1^2+b2^2)
Для нахождения единичного вектора тебе достаточно найти направляющий вектор, пускай его координаты (a , b) далее ты его нормируешь, делишь каждую координату на sqrt(a^2+b^2).
Перпендикулярный вектор к (a , b) имеет направление (-b , a).
1
Автор FAQ
3682 / 959 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
21.04.2010, 00:15  [ТС] 10
Цитата Сообщение от Eugeniy Посмотреть сообщение
(a1*a2 + b1*b2)/sqrt(a1^2+a2^2)*sqrt(b1^2+b2^2)
Видимо опечатка, в числителе имелось ввиду: a1*b1+ a2*b2

Если от вычисленного значения по этой формуле взять арктангенс то получится как раз 74 градуса что соответствует рисунку (угол получился от оси Х)
Единичный вектор получился {0.275,-0.999}. Для того чтобы получить точку на отрезке АБ прибавлю к А единичный вектор умноженый допустим на 5 (большой шаг ), т.е. {2+0.275*5, 7+(-0.999*5)} = {3.375, 2.005}. Эта точка по идее должна принадлежать отрезку АБ, пренадлежит, отлично. Однако я неверно указал вначале точки они же посередине клеток, поэтому равны не А{2,7} а выходит A{2.5, 7.5}.

И ещё вопрос, насчет дискретности... при разных углах наклона линии по которой я буду идти шагом наверное нужен разный шаг? Ведь если линия идет под 90гр можно брать шаг и 1 и никакую клетку не пропустишь, а при других углах уже можно оставить без внимания некоторые клетки которые линия задевает очень слабо. Как бы тут выкрутиться?
0
3128 / 1321 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
21.04.2010, 01:07 11
Цитата Сообщение от insideone Посмотреть сообщение
Видимо опечатка, в числителе имелось ввиду: a1*b1+ a2*b2
Совершенно верно - извиняюсь
Цитата Сообщение от insideone Посмотреть сообщение
Если от вычисленного значения по этой формуле взять арктангенс
insideone, нужно брать арккосинус!
Цитата Сообщение от insideone Посмотреть сообщение
И ещё вопрос, насчет дискретности... при разных углах наклона линии по которой я буду идти шагом наверное нужен разный шаг
Чтобы не пропустить никакую клетку, шаг может быть единица при любом наклоне, потому что единица - это расстояние между двумя ребрами координатного квадрата. Можешь брать шаг и меньше, скажем 0,5 - всё зависит от того, что тебе надо
0
Автор FAQ
3682 / 959 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
21.04.2010, 01:32  [ТС] 12
Цитата Сообщение от Eugeniy Посмотреть сообщение
Чтобы не пропустить никакую клетку, шаг может быть единица при любом наклоне, потому что единица - это расстояние между двумя ребрами координатного квадрата. Можешь брать шаг и меньше, скажем 0,5 - всё зависит от того, что тебе надо
Т.е. шаг равный единичному вектору подходит?
Название: temp.png
Просмотров: 32

Размер: 2.5 Кб
Я просто подумал о такой ситуации, когда шаг находит клетки но не все. Найденные красно-желные, не найденые просто красные. Хм...

Цитата Сообщение от Eugeniy Посмотреть сообщение
нужно брать арккосинус!
у.. точно
0
3128 / 1321 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
21.04.2010, 01:42 13
Цитата Сообщение от insideone Посмотреть сообщение
Т.е. шаг равный единичному вектору подходит?
А вот это уже зависит от стартовой точки. В таких случаях посчитай гипотенузу прямоугольного треугольника, которую жёлтые шаги на рисунке не проходят. Тогда длина шага не должна её превишать. В общем случае сделать тоже можно. Надо посчитать угловой коефициент наклона прямой, с его помощью посчитай длину отсекаемой гипотенузы, а значит ты и посчитаешь длину шага.
0
42 / 24 / 3
Регистрация: 16.03.2010
Сообщений: 199
21.04.2010, 09:27 14
честное слово, составшиь уравнение прямой, а не будешь использовать вектор, и сможешь проверять, проходит ли через точку сабсциссой x или с ординатой y.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.04.2010, 09:27

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Найти перпендикуляр, опущенный из точки на плоскость треугольника.
Помогите решить задачу пожалуйста!

Перпендикуляр из точки на прямую
Привет. Прямая задана двумя точками (x1,y1) (x2,y2). Есть третья точка (x3,y3). Из точки нужно...

Из одной точки к прямой проведены перпендикуляр и наклонная
Из одной точки к прямой проведены перпендикуляр и наклонная. По длинам отрезков определить, который...

перпендикуляр к прямой из точки на этой прямой
Подскажите пожалуйста алгоритм. есть прямая на плоскости заданная двумя точками(x1,y1)(x2,y2). на...

Точки, входящие в область
Помогите, пожалуйста с задачкой Определить количество точек, входящих в заштрихованную область....

Заданы два массива A и B. Удалить из массива А все элементы, входящие в состав массива В
Половину я сделала, задала массивы, а дальше не получается :sorry: %-) Поможете? program...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

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