CODEWITHSUNDEEP
vbagraphicsgeometry
Overt_Agent
Overt_Agent

Reputation: 519

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

Upvotes: 0

Views: 136

Answers (3)

user1196549
user1196549

Reputation:

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.

Upvotes: 1

Dithermaster
Dithermaster

Reputation: 6343

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

Upvotes: 1

rendon
rendon

Reputation: 2363

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.

Upvotes: 1

Related Questions