Are points on max. two lines?

Question

I have a time problem with my program. Given a set of points, it has to say whether all of those points are lying on two different lines.

I wrote code, which has points in array and removes one by one and try calculate it's vector.

But this solution is slow, because it must control all cases of lines. On input with 10,000 points it takes over 10 seconds.

Can someone please tell me if, is here better solution for this problem?

I made this code in Pascal:

    uses
  math;

type
  TPoint = record
    x, y: real;
  end;

  TList = array of TPoint;

function xround(value: real; places: integer): real;
var
  muldiv: real;
begin
  muldiv := power(10, places);
  xround := round(value * muldiv) / muldiv;
end;

function samevec(A, B, C: TPoint): boolean;
var
  bx, by: real; // vec A -> B
  cx, cy: real; // vec A -> C
  lb, lc: real; // len AB, len AC
begin
  bx := B.x - A.x;
  by := B.y - A.y;
  cx := C.x - A.x;
  cy := C.y - A.y;

  lb := sqrt(bx * bx + by * by);
  lc := sqrt(cx * cx + cy * cy);

  // normalize
  bx := xround(bx / lb, 3);
  by := xround(by / lb, 3);
  cx := xround(cx / lc, 3);
  cy := xround(cy / lc, 3);

  samevec := ((bx = cx) and (by = cy)) or ((bx = -cx) and (by = -cy));
end;

function remove(var list: TList; idx: integer): TPoint;
var
  i: integer;
begin
  remove.x := 0;
  remove.y := 0;
  if idx < length(list) then
    begin
      remove := list[idx];
      for i := idx to length(list) - 2 do
        list[i] := list[i + 1];
      setlength(list, length(list) - 1);
    end;
end;

var
  i, j, lines: integer;
  list, work: TList;
  A, B: TPoint;

begin
  while not eof(input) do
    begin
      setlength(list, length(list) + 1);
      with list[length(list) - 1] do
        readln(x, y);
    end;

  if length(list) < 3 then
    begin
      writeln('ne');
      exit;
    end;

  lines := 0;

  for i := 1 to length(list) - 1 do
    begin
      work := copy(list, 0, length(list));

      lines := 1;

      B := remove(work, i);
      A := remove(work, 0);
      for j := length(work) - 1 downto 0 do
        if samevec(A, B, work[j]) then
          remove(work, j);
      if length(work) = 0 then
        break;

      lines := 2;

      A := remove(work, 0);
      B := remove(work, 0);
      for j := length(work) - 1 downto 0 do
        if samevec(A, B, work[j]) then
          remove(work, j);
      if length(work) = 0 then
        break;

      lines := 3; // or more
    end;

  if lines = 2 then
    writeln('YES')
  else
    writeln('NO');
end.

Thanks, Ferko

APPENDED:

program line;
{$APPTYPE CONSOLE}
uses
  math,
  sysutils;

type point=record
    x,y:longint;
  end;

label x;

var
Points,otherPoints:array[0..200001] of point;
n,n2,i,j,k,i1,i2:longint;

function sameLine(A,B,C:point):boolean;
var
  ABx,ACx,ABy,ACy,k:longint;
begin
  ABx:=B.X-A.X;
  ACx:=C.X-A.X;
  ABy:=B.Y-A.Y;
  ACy:=C.Y-A.Y;
  k:=ABx*ACy-ABy*ACx;
  if (k=0) then sameLine:=true
    else sameLine:=false;
  end;


begin
readln(n);
if (n<=4) then begin
  writeln('YES');
  halt;
  end;

for i:=1 to n do readln(Points[i].x,Points[i].y);

for i:=1 to 5 do for j:=i+1 to 5 do for k:=j+1 to 5 do if not (sameLine(Points[i],Points[j],Points[k])) then begin
  i1:=i;
  i2:=j;
  goto x;
  end;

writeln('NO');
halt; 

x:
n2:=0;
for i:=1 to n do begin
  if ((i=i1) or (i=i2)) then continue;
  if not sameLine(Points[i1],Points[i2],Points[i]) then begin
    inc(n2,1);
    otherPoints[n2]:=Points[i];
    end;
  end;

if (n2<=2) then begin
  writeln('YES');
  halt;
  end;

for i:=3 to n2 do begin
  if not sameLine(otherPoints[1],otherPoints[2],otherPoints[i]) then begin
    writeln('NO');
    halt;
    end;
  end;
writeln('YES');
end.

could you explain why the output is yes, I really didn't understand the relation — Nasreddine Galfout
@Nasreddine output is yes, because points are lying on 2 red lines on picture. When there will be [12,12] too, out will be no, because these points can't lying on 2 lines. — user7558351
The reason why I'm asking you this silly questions is that you could drive a lot of lines from the example you gave if you don't know the coordinates of at least two points from the line you want to test against then the hall thing is pretty useless when you have 10000 points — Nasreddine Galfout
if you want to see if 10000 point are in the same line then that is easy job. Find the equation of the line using two points and test the rest of points against that and you are done — Nasreddine Galfout
A much better formula to see if three points are on the same line: function OnSameLine( const A,B,C : TPoint): Boolean; begin // Result := dxAB*dyAC - dxAC*dyAB < epsilon; Result := Math.SameValue((A.x-B.x)*(A.y-C.y),(A.x-C.x)*(A.y-B.y)); end; — LU RD

MBo MBo · Accepted Answer · 2017-10-13T20:03:35

Three points A, B and C lie on the same straight line, if vectors AB and AC are collinear or anti-collinear. We can check for collinearity using cross product of vectors - it should be zero.

@LU RD already described this approach is comment, but author probably missed it.

Note that method doesn't suffer from division by zero - there is no division at all.

 ABx := B.X - A.X;
 ACx := C.X - A.X;
 ABy := B.Y - A.Y;
 ACy := C.Y - A.Y;
 Cross := ABx * ACy - ABy * ACx;
 // for integer coordinates
 if Cross = 0 then 
    A,B,C are collinear

If coordinates are float, one must consider some tolerance level. Variants:

 //better if available:
 if Math.IsZero(Cross)
 if Math.SameValue(Cross, 0)
 //otherwise
 if Abs(Cross) <= SomeEpsilonValue

If coordinate range is very large, numerical error might be significant, so it is worth to normalize tolerance by squared magnitude of coordinate differences:

 if Math.IsZero(Cross / Max(ABx * ABx + ABy * ABy, ACx * ACx + ACy * ACy))

Are points on max. two lines?

3 Answers