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.


Need Your Help

Function is not defined, don't know why

javascript function javascript-events

Here's the code. Button1 and button2 come up as undefined.

How to call methods inside of a Backbone Collection

javascript backbone.js

I'm new to Backbone.js, well even new to Javascript, not sure how to put my question in phrase, I want a function to be called and returns result as an attribute in the same collection.