Код пересечения линии в паскале

Question

Я пытаюсь написать код пересечения линий, чтобы определить, пересекаются ли две линии.форма, в которой у меня есть вещи, это O объектов, которые могут иметь линии Lo (l индекс O), каждая строка имеет 2 точки, а каждая точка имеет топор и y.это формат записи.

 TPoint = record
    x,y:integer;
  end;
  TLine = record
    Point : array[0..1] of TPoint;
    Color : Tcolor;
  end;
  TFill = record
    Point : TPoint;
    Color : Tcolor;
  end;
  TDObject = record
    Lines : array of TLine;
    Fills : array of TFill;
    Rotation : integer;
    Position : Tpoint;
    BoundTop,Boundleft,Boundbottom,Boundright:integer;
  end;

Я вызываю Code для итерации каждой комбинации строк двух объектов, которые я хочу проверить на столкновение.

Function DoCollide(obj1,obj2:Tdobject):boolean;
var i,j:integer;
 coll:boolean;
begin
  coll:=false;
  for i:=0 to length(obj1.lines) do
  begin
    for j:=0 to length(obj2.lines) do
    begin
      coll:=DoesIntersect(obj2.lines[i],obj2.lines[j])or coll;
    end;
  end;
  result:=coll;
end;

каждый тест строки выполняется следующим образомтак что

Function DoesIntersect(Line1,Line2:Tline):boolean;

var
  m1,m2,c1,c2,intersect:real;
  v1,v2:Boolean;
begin
//return true if lines cross
  // if line if verticle do not workout gradient
  if ((line1.point[1].x)-(line1.point[0].x))=0 then
    v1:=true // remember line 1 is verticle
  else
  begin
    m1 := ((line1.point[1].y)-(line1.point[0].y))/((line1.point[1].x)-(line1.point[0].x));
    c1 := line1.point[0].y - (line1.point[0].x*m1);
  end;

  if ((line2.point[1].x)-(line2.point[0].x))=0 then
    v2:=true    // remember line 2 is verticle
  else
  begin
    m2 := ((line2.point[1].y)-(line2.point[0].y))/((line2.point[1].x)-(line2.point[0].x));
    c2 := line2.point[0].y - (line2.point[0].x*m2);
  end;

  if ((NOT(m1=m2)) and (NOT(v1 or v2))) then  // non parrellel and non verticle
  begin

      //lines cross find where
      intersect := (c2-c1)/(m1-m2);   //line intersect solved for x
      if ((round(intersect)>= Min(line1.point[0].x,line1.point[1].x))
      and(round(intersect)<=max(line1.point[0].x,line1.point[1].x))
      and(round(intersect)>=min(line2.point[0].x,line2.point[1].x))
      and(round(intersect)<=max(line2.point[0].x,line2.point[1].x))) then
        result := true
      else
        result := false

  end
  else if (v1 and v2) then  // both lines are parralel
  begin
      // double verticle parallel exeption
      if (((line1.Point[0].y>=min(line2.Point[0].y,line2.Point[1].y))
      and(line1.Point[0].y<=max(line2.Point[0].y,line2.Point[1].y)))
      or ((line1.Point[1].y>=min(line2.Point[0].y,line2.Point[1].y))
      and(line1.Point[1].y<=max(line2.Point[0].y,line2.Point[1].y)))
      or ((line2.Point[0].y>=min(line1.Point[0].y,line1.Point[1].y))
      and(line2.Point[0].y<=max(line1.Point[0].y,line1.Point[1].y)))
      or ((line2.Point[1].y>=min(line1.Point[0].y,line1.Point[1].y))
      and(line2.Point[1].y<=max(line1.Point[0].y,line1.Point[1].y)))) then
        result := true
      else
        result := false;

  end
  else if (v1 and not v2) then  // line 1 is verticle and line 2 is not
  begin

      if ((((line1.Point[0].x*m2+c2)>=min(line1.Point[0].y,line1.Point[1].y))
      and ((line1.Point[0].x*m2+c2)<=max(line1.Point[0].y,line1.Point[1].y)))) then
        result := true
      else
        result := false
  end
  else if (v2 and not v1) then  // line 2 is verticle and line 1 is not
  begin

      if (((line2.Point[0].x*m1+c1)>min(line2.Point[0].y,line2.Point[1].y))
      and ((line2.Point[0].x*m1+c1)<max(line2.Point[0].y,line2.Point[1].y))) then
        result := true
      else
        result := false

  end
  else if (m1=m2) then  // parrellel non verticle lines
  begin

      if (((line1.Point[0].x>=min(line2.Point[0].x,line2.Point[1].x))
      and(line1.Point[0].x<=max(line2.Point[0].x,line2.Point[1].x)))
      or ((line1.Point[1].x>=min(line2.Point[0].x,line2.Point[1].x))
      and(line1.Point[1].x<=max(line2.Point[0].x,line2.Point[1].x)))
      or ((line2.Point[0].x>=min(line1.Point[0].x,line1.Point[1].x))
      and(line2.Point[0].x<=max(line1.Point[0].x,line1.Point[1].x)))
      or ((line2.Point[1].x>=min(line1.Point[0].x,line1.Point[1].x))
      and(line2.Point[1].x<=max(line1.Point[0].x,line1.Point[1].x)))) then
        result := true
      else
        result := false;

  end;
end;

но, согласно моему коду, все линии всегда пересекаются ..... поэтому я ошибся ... я делаю это глупо, есть идеи, что я сделал неправильно?

Answer 1

Есть лучший способ определить, пересекаются ли два набора линий , но пока не беспокойтесь об этом.

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

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

Ваше вычисление intersect неверно.Вам нужно разделить разницу в уклонах на разницу в y -приятиях:

if c1 = c2 then
  intersect := c1
else
  intersect := (m1 - m2) / (c2 - c1);

Если обе линии вертикальные, то недостаточно проверить, перекрываются ли они в их y координаты.Вы также должны проверить, что их x координаты равны.Аналогично, с параллельными не вертикальными линиями, вам нужно проверить, равны ли y -интерпретации.

Если вы исправите все эти проблемы и по-прежнему получите неправильные результаты, то пришло время запылитьвыключить отладчикНайдите пару линейных сегментов, для которых ваша функция возвращает true , но которые в действительности не пересекаются.Вызовите функцию для этих значений и выполните пошаговое выполнение своей функции с помощью отладчика.Чтобы упростить отладку, вам нужно разбить эти многострочные условные выражения на несколько промежуточных переменных, чтобы вы могли проверить каждую из них по отдельности.Определите, какой расчет неверен, а затем исправьте его.Убедитесь, что ваш тестовый набор данных содержит элементы, которые будут использовать каждый возможный условный путь в вашей функции.