Нахождение короткого пути, посторение линий

ЛЮДИ!!!
Вообчим есть две точки A(x1,y1) и B(x2,y2). Нужно провести линию из одной к другой и знать координату каждой точки на этой линии. Т.е. простое line (x1,y1)-(x2,y2) не подойдёт. Где-то слышал, что использовать векторы, но при их сложении всё-равно вылезает не то, что нужно.

Или сделаем проще: как процессор рисует линию. Формула какая-то млин нужна.

формула прямой
y = a * x + b

ограничиваем по координатам x1, x2 (или y1, y2) получаем формулу отрезка

Линии чаще всего рисуют с помощью алгоритма Брезенхема (есть и другие, но этот - один из самых быстрых). Подробности: http://www.enlight.ru/demo/faq/smth.phtml?query=alg_line_misc

А хочешь простейший алгоритм, ведь если ты немыл руки плохим мылом
как ты сможешь оценить все прелести хорошего в частности алг. Брезенхема.
В общем идея такая:
1. Вычисляем уравнение прямой т.е. находим a и b в формуле y=a*x+b.
2. Потом рисуем y ( y=a*x+b ) для каждого  x1<=x<=x2
3. Потом рисуем x (x=(y-b)/a  )для каждого  y1<=y<=y2

Шаг три нужен т.к. нет гарантии что после шага 2 линия будет сплошной.

из условия не очевидно, что x1 <= x2, может оказаться и наоборот, а y зависит от функции, тем более условие не верное.

Сообщение отредактировано: MeG - 01.12.03, 20:00

Цитата

из условия не очевидно, что x1 <= x2, может оказаться и наоборот, а y зависит от функции, тем более условие не верное

Ну вообщем да. Я забыл сказать что если х1>x2 To Их надо обменять значениями.
Аналогично нужно поступить для y1 и y2.
Мы же сейчас говорим не про абстрактный график а про прямую у которой есть особеность - каждому значению Y соответствует единственное значение X.

можно задать отрезок [AB]  параметрическим уравнением

x = t * a + b
y = t * c + d
где  a, b, c, d некоторые константы, t — параметр. При изменении t от минус бесконечности, до плюс бесконечности получим все точки (x, y)  прямой.
Поскольку нам нужен отрезок, ограничим параметр t, таким образом, чтобы при t = 0 получились координаты точки A(x1, y1), а при t = 1 — координаты точки B(x2, y2)

Найдем константы b, d системы уравнений. Подставляем координаты точки A(x1, y1) и значение параметра для этой точки t = 0
x1 = 0 * a + b
y1 = 0 * c + d
получаем b = x1; d = y1

дальше находим a, c через точку B(x2, y2) и t = 1
x2 = 1 * a + x1
y2 = 1 * c + y1

получаем a = x2 – x1;  c = y2 – y1

Таким образом получаем уравнение отрезка [AB] выраженное через координаты точек  A(x1, y1) и B(x2, y2):
x = t * (x2 - x1) + x1
y = t * (y2 - y1) + y1, при 0 <= t <= 1
Изменяя t от нуля до единицы получим все точки отрезка

ЗЫ: урок по геометрии ;D

Сообщение отредактировано: MeG - 01.12.03, 20:01

Пример использования параметрического уравнения прямой. Принадлежит ли точка заданному отрезку

Есть отрезок с координатами концов A(5, 1) и B(-1, -2).
Параметрическое уравнение для отрезка [AB]:
x = -6 * t + 5
y = -3 * t + 1

Найдем положение точки C(2, 3) относительно отрезка [AB].
Подставляем координаты отрезка в уравнение
2 = -6 * t + 5
3 = -3 * t + 1
упрощаем
-3 = -6 * t
2 = -3 * t
выражаем параметр
1/2 = t
-2/3 = t
получилось два разных значения параметра t, точка C не лежит на прямой

Точка D(7, 2)
Подставляем координаты отрезка в уравнение,
7 = -6 * t + 5
2 = -3 * t + 1
выражаем параметр
-2/6 = t
-1/3 = t
получили одно значение параметра t = -1/3, точка D лежит на прямой.
значение параметра t = -1/3 выходит за границы 0 <= t <= 1. Точка D находится вне отрезка [AB].

Точка E(1, -1)
1 = -6 * t + 5
-1 = -3 * t + 1
одно значение параметра t = 2/3, точка E лежит на отрезке [AB].
Точка E лежит на отрезке на расстоянии две третьих длинны |AB| от точки A. То есть |AE| = 2 * |EB|

Этот пример можно наглядно изобразить на бумажке  

Сообщение отредактировано: MeG - 01.12.03, 20:02

Помогите, пожалуйста с задачей.

Даны вершины A(7; − 4) , B(3; − 7) , C(−2; 5) треугольника. Требуется
найти:
1) длину стороны BC ;
2) площадь треугольника ABC ;
3) уравнение стороны BC ;
4) уравнение высоты, проведенной из вершины A;
5) длину высоты, проведенной из вершины A;
6) угол B в радианах с точностью до 0,01.
Сделать чертеж.

у МЕНЯ ПОЛУЧИЛОСЬ

1) ВС=13
2) площадь АВС = 31.5
3) что такое уравнение стороны? может напишите?
4-6) тоже не знаю.

Цитата olga0883@mail.ru @ 15.10.09, 17:03

что такое уравнение стороны?

Может имеется ввиду уравнение прямой, на которой лежит сторона. Уравнение прямой можно записать так: x2 = a * x1 + b , поочередно подставляем в это уравнение координаты точек, через которые должна проходить прямая, находим a и b. Отрезок [B(b1, b2), C(c1, c2)] можно задать параметрически, например так: x1 = t, тогда x2 = a * t + b и t меняется от b1 до c1

Добавлено 15.10.09, 19:02

Цитата olga0883@mail.ru @ 15.10.09, 17:03

4) уравнение высоты, проведенной из вершины A;

т.е. перпендикуляр к стороне BC, пусть уравнение ее x2 = a * x1 + b или x2 - a * x1 = b , тогда (-a, 1) - вектор нормали к этой прямой или направляющий вектор прямой, перпендикулярной BC. Нужно написать уравнение прямой проходящей через A с направляющим вектором (-a, 1)