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

@insideone · Регистрация: 10.01.2010

Вопрос связанный с геометрией которая строится в дискретном пространстве (игровом).
Дан двумерный массив проходимости - map[Y][X]. Есть две точки А и Б. Между ними проводится линия, нужно найти первую (ab1) и вторую точку входа в препятствие (ab2) этой линией. Затем найти среднюю между ними точку (dab). Все вышеописанное мне кажется не таким сложным, а вот дальше... Нужно построить перпендикуляр к отрезку АБ в точке dab (в какую его сторону выводить пока что не важно). А потом найти первую свободную точку которую пересекает этот перпендикуляр. Дискретные точки пересечения я пометил крестиками. Как бы их получить?
Единственная идея которая мне пока пришла это создать массив

C++

#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. Тема так же связана собственно с продумыванием алгоритма, так что если по геометрической части идей долгое время не будет прошу перенести тему в алгоритмы

@delfamur · 19.04.2010, 22:52

блин, давно геометрия была... короче, перпендикуляр это тоже прямая и как и всякая прямая задается уравнением, точки ты конечно крупные выбрал)))для прямой, соединяющей две точки с задаными координатами сможешь уравнение составить? потом перпендикуляр в средней точке (то есть, перпендикуляр, проходящий через точку с задаными координатами). зная уравнение прямой и координаты границы просчитаешь точку выхода. +1 - то что тебе надо

@insideone · 19.04.2010, 23:11 **[ТС]**

Сообщение от delfamur

зная уравнение прямой и координаты границы

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

Если имеется ввиду граница препятствия то она не известна, вот как раз чтобы найти её надо проложить точки к ней...

@delfamur · 19.04.2010, 23:13

не пойму тогда - что дано тебе?))

@insideone · 19.04.2010, 23:19 **[ТС]**

Всего лишь двумерный массив и две точки (А и Б) указывающие на координаты в нем, фактически контуры препятствий это абстракция которая видна лишь на рисунке, а так там просто массив который содержит данные открыта эта точка или нет

@delfamur · 20.04.2010, 10:34

пододжи, а границы препятствия ты по рисунку определяешь? если да, то это тоже отрезки прямых простых функций типа x=a, y=b. приравнивая с той функцией, которой ты задашь прямую, соединяющую две точки, ты получишь точки входа и выхода. ну и так далее, как описал вначале

@Eugeniy · 20.04.2010, 18:32

insideone, твоя проблема в том, и это я уже не раз замечал, что ты выражаешся языком программиста, который хорошо разбирается в том о чем он говорит, но делает это так, как-будто его собеседник не хуже него посвящен в суть задачи.
Я толком ничего не понял из твоего условия. Скажи, как было бы людям, если бы я им отвечал языком кванторов и чистых формул? Обьясни нормально, с точки зрения математики, что ты хочеш.

Также и в прошлый раз, тебе просто нужно было уравнение кривой, а ты начал и то и сё, и так и так. Где-то на посту 15-ом я только понял, что ты хочешь. Будь проще - и люди к тебе потянутся

@insideone · 20.04.2010, 21:56 **[ТС]**

Eugeniy, я вот и не знаю как подступиться, особенно что касается геометрии. Попробую по рисунку: есть точка A{2, 7} и точка Б{4, 0}. Мне нужно найти угол (оносительно оси X или Y... не важно пока что) отрезка AБ + получить такой единичный вектор который можно прибавлять допустим к точке А и будет получаться новая точка на отрезке АБ. Благодаря этому найдутся точки ab1 и ab2 потом и средняя между ними точка. После этого мне нужно будет получить такой единичный вектор который позволит идти по отрезку (на рисунке перпендикуляр от АБ) так же как это делалось в случае с нахождением точек ab1 и ab2.
Так уже лучше?

@Eugeniy · 20.04.2010, 22:39

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).

@insideone · 21.04.2010, 00:15 **[ТС]**

Сообщение от 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 и никакую клетку не пропустишь, а при других углах уже можно оставить без внимания некоторые клетки которые линия задевает очень слабо. Как бы тут выкрутиться?

@Eugeniy · 21.04.2010, 01:07

Сообщение от insideone

Видимо опечатка, в числителе имелось ввиду: a1*b1+ a2*b2

Совершенно верно - извиняюсь

Сообщение от insideone

Если от вычисленного значения по этой формуле взять арктангенс

insideone, нужно брать арккосинус!

Сообщение от insideone

И ещё вопрос, насчет дискретности... при разных углах наклона линии по которой я буду идти шагом наверное нужен разный шаг

Чтобы не пропустить никакую клетку, шаг может быть единица при любом наклоне, потому что единица - это расстояние между двумя ребрами координатного квадрата. Можешь брать шаг и меньше, скажем 0,5 - всё зависит от того, что тебе надо

@insideone · 21.04.2010, 01:32 **[ТС]**

Сообщение от Eugeniy

Чтобы не пропустить никакую клетку, шаг может быть единица при любом наклоне, потому что единица - это расстояние между двумя ребрами координатного квадрата. Можешь брать шаг и меньше, скажем 0,5 - всё зависит от того, что тебе надо

Т.е. шаг равный единичному вектору подходит?
Название: temp.png
Просмотров: 32

Размер: 2.5 Кб

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

Сообщение от Eugeniy

нужно брать арккосинус!

у.. точно

@Eugeniy · 21.04.2010, 01:42

Сообщение от insideone

Т.е. шаг равный единичному вектору подходит?

А вот это уже зависит от стартовой точки. В таких случаях посчитай гипотенузу прямоугольного треугольника, которую жёлтые шаги на рисунке не проходят. Тогда длина шага не должна её превишать. В общем случае сделать тоже можно. Надо посчитать угловой коефициент наклона прямой, с его помощью посчитай длину отсекаемой гипотенузы, а значит ты и посчитаешь длину шага.

@delfamur · 21.04.2010, 09:27

честное слово, составшиь уравнение прямой, а не будешь использовать вектор, и сможешь проверять, проходит ли через точку сабсциссой x или с ординатой y.

@insideone 3682 / 959 / 114 Регистрация: 10.01.2010 Сообщений: 2,550
	21.04.2010, 01:32 [ТС]	12
	Сообщение от Eugeniy Чтобы не пропустить никакую клетку, шаг может быть единица при любом наклоне, потому что единица - это расстояние между двумя ребрами координатного квадрата. Можешь брать шаг и меньше, скажем 0,5 - всё зависит от того, что тебе надо Т.е. шаг равный единичному вектору подходит? Я просто подумал о такой ситуации, когда шаг находит клетки но не все. Найденные красно-желные, не найденые просто красные. Хм... Сообщение от Eugeniy нужно брать арккосинус! у.. точно 0

@delfamur 42 / 24 / 3 Регистрация: 16.03.2010 Сообщений: 199
	19.04.2010, 22:52	2
	блин, давно геометрия была... короче, перпендикуляр это тоже прямая и как и всякая прямая задается уравнением, точки ты конечно крупные выбрал)))для прямой, соединяющей две точки с задаными координатами сможешь уравнение составить? потом перпендикуляр в средней точке (то есть, перпендикуляр, проходящий через точку с задаными координатами). зная уравнение прямой и координаты границы просчитаешь точку выхода. +1 - то что тебе надо 0

@insideone 3682 / 959 / 114 Регистрация: 10.01.2010 Сообщений: 2,550
	19.04.2010, 23:11 [ТС]	3
	Сообщение от delfamur зная уравнение прямой и координаты границы Так я же границу как раз и ищу, она же и есть точка выхода. Заморочился я сегодня с этой проблемой что то не соображу совсем Если имеется ввиду граница препятствия то она не известна, вот как раз чтобы найти её надо проложить точки к ней... 0

@delfamur 42 / 24 / 3 Регистрация: 16.03.2010 Сообщений: 199
	19.04.2010, 23:13	4
	не пойму тогда - что дано тебе?)) 0

@insideone 3682 / 959 / 114 Регистрация: 10.01.2010 Сообщений: 2,550
	19.04.2010, 23:19 [ТС]	5
	Всего лишь двумерный массив и две точки (А и Б) указывающие на координаты в нем, фактически контуры препятствий это абстракция которая видна лишь на рисунке, а так там просто массив который содержит данные открыта эта точка или нет 0

@delfamur 42 / 24 / 3 Регистрация: 16.03.2010 Сообщений: 199
	20.04.2010, 10:34	6
	пододжи, а границы препятствия ты по рисунку определяешь? если да, то это тоже отрезки прямых простых функций типа x=a, y=b. приравнивая с той функцией, которой ты задашь прямую, соединяющую две точки, ты получишь точки входа и выхода. ну и так далее, как описал вначале 0

@Eugeniy 3128 / 1321 / 156 Регистрация: 19.12.2009 Сообщений: 1,808
	20.04.2010, 18:32	7
	insideone, твоя проблема в том, и это я уже не раз замечал, что ты выражаешся языком программиста, который хорошо разбирается в том о чем он говорит, но делает это так, как-будто его собеседник не хуже него посвящен в суть задачи. Я толком ничего не понял из твоего условия. Скажи, как было бы людям, если бы я им отвечал языком кванторов и чистых формул? Обьясни нормально, с точки зрения математики, что ты хочеш. Также и в прошлый раз, тебе просто нужно было уравнение кривой, а ты начал и то и сё, и так и так. Где-то на посту 15-ом я только понял, что ты хочешь. Будь проще - и люди к тебе потянутся 0

@insideone 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

@Eugeniy 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) равен = (a1a2 + b1b2)/sqrt(a1^2+a2^2)*sqrt(b1^2+b2^2) Для нахождения единичного вектора тебе достаточно найти направляющий вектор, пускай его координаты (a , b) далее ты его нормируешь, делишь каждую координату на sqrt(a^2+b^2). Перпендикулярный вектор к (a , b) имеет направление (-b , a). 1

@insideone 3682 / 959 / 114 Регистрация: 10.01.2010 Сообщений: 2,550
	21.04.2010, 00:15 [ТС]	10
	Сообщение от Eugeniy (a1a2 + b1b2)/sqrt(a1^2+a2^2)sqrt(b1^2+b2^2) Видимо опечатка, в числителе имелось ввиду: a1b1+ a2b2 Если от вычисленного значения по этой формуле взять арктангенс то получится как раз 74 градуса что соответствует рисунку (угол получился от оси Х) Единичный вектор получился {0.275,-0.999}. Для того чтобы получить точку на отрезке АБ прибавлю к А единичный вектор умноженый допустим на 5 (большой шаг ), т.е. {2+0.2755, 7+(-0.999*5)} = {3.375, 2.005}. Эта точка по идее должна принадлежать отрезку АБ, пренадлежит, отлично. Однако я неверно указал вначале точки они же посередине клеток, поэтому равны не А{2,7} а выходит A{2.5, 7.5}. И ещё вопрос, насчет дискретности... при разных углах наклона линии по которой я буду идти шагом наверное нужен разный шаг? Ведь если линия идет под 90гр можно брать шаг и 1 и никакую клетку не пропустишь, а при других углах уже можно оставить без внимания некоторые клетки которые линия задевает очень слабо. Как бы тут выкрутиться? 0

@Eugeniy 3128 / 1321 / 156 Регистрация: 19.12.2009 Сообщений: 1,808
	21.04.2010, 01:07	11
	Сообщение от insideone Видимо опечатка, в числителе имелось ввиду: a1b1+ a2b2 Совершенно верно - извиняюсь Сообщение от insideone Если от вычисленного значения по этой формуле взять арктангенс insideone, нужно брать арккосинус! Сообщение от insideone И ещё вопрос, насчет дискретности... при разных углах наклона линии по которой я буду идти шагом наверное нужен разный шаг Чтобы не пропустить никакую клетку, шаг может быть единица при любом наклоне, потому что единица - это расстояние между двумя ребрами координатного квадрата. Можешь брать шаг и меньше, скажем 0,5 - всё зависит от того, что тебе надо 0

Опции темы

@Eugeniy 3128 / 1321 / 156 Регистрация: 19.12.2009 Сообщений: 1,808
	21.04.2010, 01:42	13
	Сообщение от insideone Т.е. шаг равный единичному вектору подходит? А вот это уже зависит от стартовой точки. В таких случаях посчитай гипотенузу прямоугольного треугольника, которую жёлтые шаги на рисунке не проходят. Тогда длина шага не должна её превишать. В общем случае сделать тоже можно. Надо посчитать угловой коефициент наклона прямой, с его помощью посчитай длину отсекаемой гипотенузы, а значит ты и посчитаешь длину шага. 0

@delfamur 42 / 24 / 3 Регистрация: 16.03.2010 Сообщений: 199
	21.04.2010, 09:27	14
	честное слово, составшиь уравнение прямой, а не будешь использовать вектор, и сможешь проверять, проходит ли через точку сабсциссой x или с ординатой y. 0