Люди, допустим у меня есть две прямые, известны их координаты, как найти координаты точки их пересечения, я решил эту задачу геометрически, но вышел слишком грамоздкий ответ, может как полегче можно ?

Находим уравнения прямой для обоих прямых, а именно k и b, далее приняв значения по y равными находим точку пересечения по x, подставляем точку пересечения по оси абсцисс в любое из двух уравнений прямых и подсчитываем точку пересечения по y.

Нечто древнее и не очень оптимальное, но рабочее. Есть простор для оптимизации.

Код

interface type  TIntersectStatus = (liNone, liParallel, liCombine, liEqual, liIntersect, liDot); function LineIntersect(const A, B, C, D: TPoint; var I: TPoint): TIntersectStatus; // Отрезок AB пересекает CD в точке I implementation function LineIntersect(const A, B, C, D: TPoint; var I: TPoint): TIntersectStatus; {            (YA-YC)(XD-XC)-(XA-XC)(YD-YC)        r = -----------------------------  (1)            (XB-XA)(YD-YC)-(YB-YA)(XD-XC)            (YA-YC)(XB-XA)-(XA-XC)(YB-YA)        s = -----------------------------  (2)            (XB-XA)(YD-YC)-(YB-YA)(XD-XC) } var  r, s: Double;  ri, si, f: integer; begin  if ((A.X = C.X) and (A.Y = C.Y) and (B.X = D.X) and (B.Y = D.Y)) or     ((A.X = D.X) and (A.Y = D.Y) and (B.X = C.X) and (B.Y = C.Y))  then begin    Result := liEqual;    Exit;  end;  f := ((B.X - A.X)*(D.Y - C.Y)) - ((B.Y - A.Y)*(D.X - C.X));  ri := ((A.Y - C.Y)*(D.X - C.X)) - ((A.X - C.X)*(D.Y - C.Y));  if f = 0 then begin    if ri = 0 then begin      Result := liCombine;      Exit;    end;    Result := liParallel;    Exit;  end;  si := ((A.Y - C.Y)*(B.X - A.X)) - ((A.X - C.X)*(B.Y - A.Y));  r := ri / f;  s := si / f;  if (r < 0.0) or (r > 1.0) or     (s < 0.0) or (s > 1.0)  then begin    Result := liNone;    Exit;  end;  if (r = 0.0) or (r = 1.0) or (s = 0.0) or (s = 1.0) then    Result := liDot  else    Result := liIntersect;  I.X := A.X + Round(r*(B.X - A.X));  I.Y := A.Y + Round(r*(B.Y - A.Y)); end;

Не пробовал, но уверен что правильно, спасибо !

гы а если так
рисуем прямую номер 1
потом прямую номер 2
и проверяем
а не совпадают ли у нас там гдето координаты точек? а?
будет быстро работать

Есть и такой вариант.
Создаем массивы с элементами обеих кривых (+ массивы индексов),
Переписываем массивы в 1-н, смотрим, а не совпадут ли где нибудь массивы типа
..., i, i, ...
В смысле 2-а одинаковых индекса будут стоять рядом.

Применимо для любого числа кривых.

oleg1973 а на каком помежутке будем искать пересеченме? Ведь если прямые практически паралельно, то енто будет НЕМНОГО долго!!! Black_Joker аналогично с массивом, тока тут ещё всё завязывается на размере массива!

Dmitry V.Abramov Чем тебе не нравится мой способ? Ведь он намноге меньше

Полудненко Олег
интересно чеж там долгово?
рисуеш одновременно две прямые (алгоритм не важен хоть любимым брезенхамом)
и сравниваеш тут же координаты точки от 1 прямой и от 2
прямые то в любом случае рисовать нада

По-моему, самый оптимальный алгоритм, предложенный Dmitry V.Abramov, быстрее всего работает

oleg1973 кода ты расиуеш прямые, то ты указываеш только две точки (я надеюсь), а не рисуеш их поточечно. Енто раз. Два, и самое главное!!!, пересечение этих двух прямых может и не наблюдаться визуально, имхо оно может оказаться высоко в небе или под землёй, но не у тя на мониторе!!!

Имеем 8 координат 4-х точек, которые пренадлежат исходным прямым: (x1,y1),(x2,y2),(x3,y3) & (x4,y4).
Вся наёбка идёт по ур-нию прямой вида y=k*x+b.
Находим k1:=(y1-y2)/(x2-x1); k2:=(y3-y4)/(x4-x3);
Находим b1:=(Form1.Image1.Height-y2-x2*k1); b2:=(Form1.Image1.Height-y4-x4*k2);
Далее находим отчку пересечения по x= (b2-b1)/(k1-k2);
Далее подставляем полученный х в y=k1*x+b1 откуда находим у.
Так в четыре строки находим координаты точки пересечения!!!!

Цитата

то ты указываеш только две точки (я надеюсь), а не рисуеш их поточечно.

хаха
интересная теория
знаеш когда оно само рисуется? когда хардварно (vesa по стандарту поддерживает)
ну а так в любом случае любой алгоритм будет просчитывать каждую точку прямой и не важно где на экране или в бэк буфере
канешно если ты используеш там супер пупер компоненты или либы которым на входе даеш 2 точки и получаеш прямую то оно может и показатся что все так просто
так что не вижу смысла сначало рисовать линии
а потом пытатся определить пересикаемость их
если можно сделать все за 1 раз непосредственно во время рисования

oleg1973 а кто сказал, что их вообще надо рисовать, допустим у тебя массив из 100 прямых, нужно определить все точки пересечения, ты что будешь по всему этому массиву поточечно проходить ?

Sheff
ну так с этого и надо было начинать