Home c How to determine if the points are on one straight line?

How to determine if the points are on one straight line?

Author

Date

Category

Set the coordinates of 4 points from the keyboard (x and y).
How to write a condition that determines whether at least three of these points lie on one straight line?


Answer 1, Authority 100%

can take advantage of the equation of a straight line passing in two points:

(x - x_1) / (x_2 - x1) = (y - y_1) / (y_2 - y_1)

If the equation is performed for any other point – it is on this straight

UPD:
Actually, for three points, the condition will look like this:

if ((x_3 - x_1) / (x_2 - x_1) == (y_3 - y_1) / (y_2 - y_1)) / * points 1, 2, 3 - lie on one straight * /

Answer 2, Authority 46%

All correctly except the sign “==”. When specifying the coordinates of points, we always round the result to the accuracy provided by the computer algebra system or programming language. Therefore, in practice, such equality is extremely rare. Except if you take points (1,2); (2.4); (3.6), etc. Correctly set the accuracy of TOL computing and compare the difference with it:

tol = 1e-10 // according to the requirements of the task or set as the input parameter
IF ABS ((x_3 - x_1) / (x_2 - x_1) - (y_3 - y_1) / (y_2 - y_1)) & lt; = tol // Points lie on the line

second option, usually faster:

tol2 = 1e-20 // square permissible error
if ((x_3 - x_1) / (x_2 - x_1) - (y_3 - y_1) / (y_2 - y_1)) ^ 2 & lt; = tol2 // Points lie on the line

It is even more correct. Calculate the coefficients of the equation direct between points 1 and 2, and then calculate the “distance from the point to the straight”. The algorithm easily googles. If this distance is less than TOL, then the point lies on the straight line. However, for most tasks it is excessive complication.


Answer 3, Authority 8%

For integer coordinates, you can use the formula:

bool function ispointsonline (int x1, int y1, int x2, int y2, int x3, int y3) {
 Return (x3 * (y2 - y1) - y3 * (x2 - x1) == x1 * y2 - x2 * y1);
}

or the same, but with caching:

void preispointsonline (int x1, int y1, int x2, int y2, int & amp; dx, int & amp; dy, int & amp ; DS) {
 dx = x2 - x1;
 DY = Y2 - Y1;
 ds = x1 * y2 - x2 * y1;
}
BOOL ISPOINTSONLINE (INT DX, INT DY, INT DS, INT X3, INT Y3) {
 RETURN (X3 * DY - Y3 * DX == DS)
}

For four points, you can overdo four conditions, alternately excluding one of the points:

bool function ispointsonline (int x1, int y1, int x2, int y2,
              INT X3, INT Y3, INT X4, INT Y4) {
 if (iSpointSonline (x2, y2, x3, y3, x4, y4) ||
   ISPOINTSONLINE (X1, Y1, X3, Y3, X4, Y4) ||
   ISpointSonline (x1, y1, x2, y2, x4, y4) ||
   ISPOINTSONLINE (X1, Y1, X2, Y2, X3, Y3) ||) {
  RETURN TRUE;
 }
 RETURN FALSE;
}

In order not to be overflow, the numbers should not be close to the boundaries of an integer type of variable.


Answer 4

Error with an error The proposed V_MIL does not work.

If anyone suddenly need:

Equation direct in two points:

(x – x1) / (x2-x1) = (y-y1) / (y2-y1)

Hence:

x * (y2-y1) + x1 * (y1-y2) + y * (x2-x1) + y1 * (x2-x1) = 0

Thus for the equation direct AX + BY + C = 0 we have

a = y2 – y1

b = x1 – x2

c = x1 * (y1 – y2) + y1 * (x2 – x1)

Distance from point M (x, y) to straight Count the formula:

d = math.abs (A * MX + B * MY + C) / Math.SQRT (A ^ 2 + B ^ 2)

This distance can already be compared with some kind of error.

Programmers, Start Your Engines!

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.

Recent questions