# Problems with finding points along a line

I've drawn a line, using an X1, X2, Y1, Y2 variable. I'm looking to find any number of points along a this line, and to that extent I've written this:

Private Function genPointsArray(ByRef xPointArray() As Integer, ByRef yPointArray() As Integer, startX As Integer, finX As Integer, startY As Integer, finY As Integer, numPoints As Integer) As Integer ReDim xPointArray(numPoints) ReDim yPointArray(numPoints) xPointArray(0) = startX xPointArray(numPoints - 1) = finX yPointArray(0) = startY yPointArray(numPoints - 1) = finY For i = 1 To numPoints - 2 xPointArray(i) = xPointArray(i - 1) + (finX - startX) \ numPoints yPointArray(i) = yPointArray(i - 1) + (finY - startY) \ numPoints Next Return 0 End Function

As you can see, it accepts the X1, X2, Y1, Y2 variables (startX etc), two arrays to store the resultant points, and a number of points to find. The issue it has is that (worryingly often) a point is a pixel off (due to the actual result being a decimal). This then gets progressively worse as every following point is 2,3,4,5 etc pixels off, making the effect quite noticeable. Does anyone know of a way to make sure every point is along the line- either through a better algorithm or validation?

Thanks

## Answers

The reason why your generated points drift is because you're allowing the error of the integer rounding to accumulate. It's like walking with your eyes closed.

Instead of basing each point from the previous, keep going back to your original endpoints. Each point that results will be off at worst one due to rounding.

Replace

xPointArray(0) = startX xPointArray(numPoints - 1) = finX yPointArray(0) = startY yPointArray(numPoints - 1) = finY For i = 1 To numPoints - 2 xPointArray(i) = xPointArray(i - 1) + (finX - startX) \ numPoints yPointArray(i) = yPointArray(i - 1) + (finY - startY) \ numPoints Next

With just

For i = 0 To numPoints - 1 xPointArray(i) = startX + (finX - startX) * i / numPoints yPointArray(i) = startX + (finX - startX) * i / numPoints Next

Please forgive any syntax or loop bound errors; I don't write VBA

In terms of geometry a line is unidimensional, i.e. it doesn't have width and hence it's hard to know if a point is on a line without defining a criterion.

A common way to test if a point resides on a line is to compute the distance from that point to the line, and if such a distance is small enough (less than an epsilon value), then the point is considered to be on the line. I don't know VB but here is snippet that illustrates this idea:

boolean inLine(Point2D a, Point2D b, Point2D p) { double a1 = b.x() - a.x(); double b1 = b.y() - a.y(); double a2 = p.x() - a.x(); double b2 = p.y() - a.y(); double alpha = Math.atan2(b1, a1); double beta = Math.atan2(b2, a2); double theta = Math.abs(alpha - beta); double dist = Math.abs(a.distanceTo(p) * Math.sin(theta)); double eps = Math.abs(fx(3) - fx(0)); return dist < eps; }

This algorithm is known as Distance from a Point to a Line.

The epsilon value depends on your particular problem, how much precision is needed, for most applications **1e-9** will be OK.

The method distanceTo() in the code simply computes the Euclidean distance between two points.

A foolproof formula is ((N - I) * Start + I * Fin) / N. For I=0, gives you exactly Start, and for I=N, gives you exactly Fin. Intermediate values will be regularly aligned.

This works both in integer and floating-point coordinates, but mind overflows.