Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Точка на отрезке

Автор: olegkuzn 13.11.2007, 15:47

Есть отрезок определенный точками CPoint ptBeg, ptEnd. Подскажите простенький алгоритм нахождения точки (CPoint ptHit ) на заданном отрезке.
( Заранее прошу извинения. Вопрос возможно не для этого раздела. )

Автор: Andrey44 13.11.2007, 15:59

Смотри PtInRect(......), PtInRegion(........) smile

Автор: DigitSphinx 13.11.2007, 17:58

как я понял ему надо не это !
общая формула для прямой через 2 точки
(x – x1)/(x2 – x1) = (y – y1)/(y2 – y1)
общая формула прямой
y = ax + b
если привести первую формулу в этот вид получим (не уверен проверь)
a = (y2 – y1)/(x2 – x1)
b = x1*(y2 + y1)/(x2 – x1) + y1
где
x1, y1 – x2, y2 это координаты точек ptBeg, ptEnd соответственно
т.е. имея координаты этих точек задаем какой-то x random’ом и по формуле
y = ax + b получаем y

Добавлено @ 18:01
а для нахождения точки на этом отрезке, надо задать x1 < x < x2

Код


x = rand()%(x2 – x1) + x1;

P.S. вопрос ты не в том разделе задал.

Автор: zkv 13.11.2007, 21:57

Переместил из Visual С++

Автор: Dims 13.11.2007, 23:40

Цитата(olegkuzn @ 13.11.2007, 15:47

)

Есть отрезок определенный точками CPoint ptBeg, ptEnd. Подскажите простенький алгоритм нахождения точки (CPoint ptHit ) на заданном отрезке.

Можно такую модель предложить: эти две твои точки -- это два вектора B и E. Разница этих векторов H = E-B -- это вектор, который идёт от вычитаемого к уменьшаемому. Разница векторов есть почленная разность координат.

Если взять этот вектор-разницу и умножать его на число от beta = 0 до 1, то этот вектор будет менять длину от 0 до полной.

То есть, вектора X(beta) = B + H * beta будут бегать по отрезку от B до E при изменении beta от 0 до 1.

Автор: marcusmae 14.11.2007, 00:00

Весёлая тема smile

Ну, раз все способы задания уравнения прямой вспомнили (даже векторный!), то позвольте обратить внимание на скалярное произведение или теорему косинусов : для того, чтобы точка лежала на прямой, два различных вектора, образованные концами отрезков и точкой на прямой должны быть коллинеарны, то есть в скалярном произведении давать +/- 1.

Автор: olegkuzn 14.11.2007, 08:54

Формула y = y1 + (x-x1)*[(y2-y1)/(x2-x1)] а также вычисление с помощью коэффицентов k = ( y2 - y1 )/( x2 - x1 ) и b = y2 - k*x2 почему то не работает на вертикальных отрезках ( когда y1 = y2 ).

Нашел тупой способ вычисления длинн :

CSize size1 = ptEnd - ptBeg;
CSize size2 = ptEnd - ptHit;
CSize size3 = ptHit - ptBeg;

double length1 = sqrt((double)(size1.cx * size1.cx + size1.cy * size1.cy ));
double length2 = sqrt((double)(size2.cx * size2.cx + size2.cy * size2.cy ));
double length3 = sqrt((double)(size3.cx * size3.cx + size3.cy * size3.cy ));

double d = length1 - ( length2 + length3 );

if( fabs(d) <= 0.4 ) // число должно быть близко к нулю
return true;
else
return false;

Подскажите пожалуйста более оригинальный способ нахождения точки на ОТРЕЗКЕ.
Здесь слишком много вычислений.

Автор: Akina 14.11.2007, 09:15

ptN = pt1 + (pt2 - pt1) * K, где ptZ - любая из координат точки; К = число в диапазоне [0;1].
Само собой, для всех координат при вычислении точки К одинаково.

Автор: Dims 14.11.2007, 09:17

Цитата(olegkuzn @ 14.11.2007, 08:54

)

почему то не работает на вертикальных отрезках ( когда y1 = y2 ).

Так и должно быть, используй векторное представление.

Код



double k = 0.75; // получим точку, находящуются на 75% расстояния отрезка между началом и концом 
CSize diff = ptEnd - ptBeg; // вектор разницы

// домножаем вектор разницы на процент (0 - начальная точка, 1 - конечная, 0.5 -- середина, 1.5 -- на пол отрезка дальше конца и т.д.)
diff.cx *= k;
diff.cy *= k;

CSize res = ptBeg + diff; // искомая точка

Автор: Akina 14.11.2007, 09:22

Цитата(olegkuzn @ 14.11.2007, 09:54

)

почему то не работает на вертикальных отрезках ( когда y1 = y2 ).

Да потому что делить на ноль (x2-x1) настоятельно не рекомендуется...