Can we check points are in straight line

Hello,

I have a question

Consider i have 3 points, i need to check whether they are in straight line.

if its true output dispaly has TRUE else FLASE.

Answer 1

[John D'Errico]

The others have offered various solutions that CAN work, but they have flaws. In fact, many solutions can be caused to fail if you construct a carefully chosen counter-example.

For example, if the three points happened to be vertical, then all you need do is check if x is the same for all three points. But if they are vertical, then polyfit will fail.

So, is there a better solution? Well, yes, arguably there is a more robust solution. Assume that the (x,y) pairs are stored as rows of the matrix xy. Like this:

xy = [0 1;1 2;2 3];

The trick is to subtract ANY one of the rows from the other two rows. Then use rank. If your MATLAB release is no earlier than R2016b, then this test will be quite easy to write, and it is amazingly robust.

pointsAreCollinear = @(xy) rank(xy(2:end,:) - xy(1,:)) == 1;

Older MATLAB releases will require something like bsxfun in there. So in pre-R2016b, you would need to write:

pointsAreCollinear = @(xy) rank(bsxfun(@minus,xy(2:end,:),xy(1,:))) == 1;

Not nearly as clean looking, but it will work. Really old releases that are too old to have even bsxfun available? Still quite doable, but you desperately need to get a current release. ;-)

A nice thing is pointsAreCollinear always works for any nx2 array that contains points in the (x,y) plane, even if there are more than three points.

The function pointsAreCollinear will return true for any of the problem cases. But for three obviously non-collinear points, it will return false.

pointsAreCollinear(rand(3,2))
ans =
  logical
   0

Hmm. Constant x ot y? Of course it catches them.

pointsAreCollinear([1 2;1 3;1 4])
ans =
  logical
   1
pointsAreCollinear([2 1;3 1;4 1])
ans =
  logical
   1

4 points in a straight line? As you can see, it even gets that right.

pointsAreCollinear([0 1;1 2;2 3;3 4])
ans =
  logical
   1

Here is a tricky case. How about a replicated point, so really only two distinct points? Easy peasy.

pointsAreCollinear([1 1; 1 1; 2 3])
ans =
  logical
   1

It even works if you try to trick it and pass in only two points. Of course they will be collinear, but will it see that? But if you get even trickier, and pass in only one point? One point does not determine a line, so it should return false.

pointsAreCollinear([0 0; 0 1])
ans =
  logical
   1
pointsAreCollinear([0 0])
ans =
  logical
   0

The nice thing is, the construct I've suggested is pretty robust to failure. Can i make it fail? Of course.

pointsAreCollinear([0 0; 1e17 1e17;1e17 1e17+1])
ans =
  logical
   1

While it is clear those points are not collinear, the test failed. That is life. As I said, you can make just about any numerical code fail if you understand the mathematics behind it and if you understand floating point arithmetic. But that last problem is a pretty nasty one when working in double precision arithmetic.

[Pedro Guevara]

Hi. I have a question regarding the code. Is there a short and efficient way to get the indices of the points that are collinear? ¿ Is there any way to recognize a point as collinear if this point deviates slightly from the line drawn by the other 2 points?

I would really appreciate your help.

[John D'Errico]

The code that I gave returns true if all three points fall on a line. If they do not, then ANY pair of points falls on a line, and the other does not.

So your question makes no sense. If the points are NOT collinear, then arbitrarily pick any of the three points. It is not collinear with the other two. So asking for the index makes no sense.

If you have more than 3 points, then you can have arbitrarily many different configurations. Again, it makes no sense. I suppose you could make a list of all of the lines found in suh a set. But there would seem to be no simpler solution than brute force testing. Any pair of points defines a line. Now which of the others falls on the same line? You could break the set of points into subsets, finding all sets of points that appear to lie on the same lines. Again though, this would just require brute force, with no easy way out.

Are you asking to somehow specify your own tolerance? The test I gave uses rank, which implicitly uses a tolerance that is effectively a relative tolerance on the deviation from collinearity. An absolute tolerance makes no sense.

Consider the two points (0,0), (1,0). They form a straight line, that happens to lie on the x axis. Now we can investigate if the third point lies on the x axis. How far away is that third point? To answer that, it might seem we need only measure the value of y for that third point.

So now consider the triad of points (0,0), (1,0), (2,delta). If abs(delta) < tol, then we may chose to declare the third point to be collinear with that pair. But suppose our third point happens to lie at the location

(2 + k,k*delta)

I will assert that relatively, for any value of k, any member of this family of points lies equally far from the line defined by the original pair. Yet we can always choose k such that abs(k*delta) > tol. So it would seem an abolute tolerance makes no sense.

And that leaves me with the question of if you can specify your own RELATIVE tolerance. As I said, the test I posed uses rank. And in fact, rank allows the user to pass in a tolerance.

[Image Analyst]

For multiple points, you might want to consider using ismembertol().

Answer 2

[Star Strider]

If they are vertical (as in your posted image), just check to see if all the x-values are the same:

x1 = [0.5 0.5 0.5];
y1 = [1 2 3];

TF = all(x1(1)==x1);

producing:

TF =

  logical

   1

Answer 3

[Image Analyst]

You could use polyfit() to find a line, then use polyval to see how well the points fit it by summing the residuals. If the sum is small enough, they're on a line.

coefficients = polyfit(x, y, 1);
yFit = polyval(coefficients, x);
residualsSum = sum(abs(yFit - y))
if residualsSum < someNumber
        % They're considered to be on a line
else
        % They are not considered to be on a line.
end

Answer 4

[Rana]

you could use the area of the triangle formed between these points as a way of figuring out if they lie on the same line. if the area is 0 then they form a straight line.

create a 3*3 matrix and find the determinant to get the area.

area = 0.5 * abs(det(A));

however to account for floating point percision errors you must set a tolereance within your function that approximates zero. make sure to take the absolute value of the determinant.

if area <= tol

collinear = true;

else

collinear = false;