2
$\begingroup$

Let's say we have points $A$, $B$ and $C$. These points are collinear if the area of the triangle they form is $0$. So our collinearity check looks something like this:

$x_A*y_B + x_B*y_C + x_C*y_A = y_A*x_B + y_B*x_C + y_C*x_A$

This works just fine if the coordinates of our points are something like $(3,2)$, $(0,2)$ and $(-4,2)$ (as in, exactly on the same line):

$3*2 + 0*2 + (-4)*2 = 2*0 + 2*(-4) + 2*3$

But in other cases, we might run into rounding errors.

Let's consider the case of a regular triangle whose circumradius is $50$ and first vertex on the $x$ axis. We take its vertices to be at $(50,0)$, $(-25,43.3)$ and $(-25,-43.3)$. These are rounded values. That $43.3$ is actually more like $43.301270189221932338186158537647$, but keeping all those decimals is crazy, so we've rounded the value. Now let's consider the intersection between the first edge of this triangle (the one between the $(50,0)$ and $(-25,43.3)$ points) and the $y$ axis - this is $(0,28.9)$ (again, that $28.9$ is actually more like $28.867513459481288225457439025098$).

So these three points - $(50,0)$, $(-25,43.3)$ and $(0,28.9)$ should be almost collinear, which means our formula from above would change to something like:

$Δ = |(x_A*y_B + x_B*y_C + x_C*y_A) - (y_A*x_B + y_B*x_C + y_C*x_A)| < ε$

where $ε$ is a threshold error - anything smaller than that, and our points are close enough to being collinear.

Now the question is: how can we determine a good value for $ε$?

For example, $(.00001,0)$, $(0,0)$ and $(-.00001,1.74524e-7)$ are almost collinear and so are $(1000,0)$, $(0,0)$ and $(-1000,17.4524)$ (the angle is a $179°$ one in both cases), but $Δ$ is $-1.74524e-12$ in the first case and $17452.4$ in the second case.

$\endgroup$
  • $\begingroup$ You must make $\Delta$ dimensionless, dividing it by a square length, for instance $AB^2+BC^2+CA^2$. $\endgroup$ – Aretino Jan 14 '17 at 15:43
  • $\begingroup$ @Aretino That's computing the edges of the triangle which is exactly what I'm trying to avoid at this step (otherwise, I have the option of computing angles using the law of cosines). $\endgroup$ – Ana Jan 14 '17 at 17:34
  • $\begingroup$ @Aretino Buuut... that gives me an idea, which is to divide $Δ$ by the product between the average of the $x$ coordinates in absolute value and the average of the $y$ coordinates in absolute value. 🤔 $\endgroup$ – Ana Jan 14 '17 at 18:06
  • $\begingroup$ That might be dangerous when you have a small triangle whose vertices have large coordinates. $\endgroup$ – Aretino Jan 14 '17 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.