Equidistant points in a line segment

Question

Let assume you have two points (a , b) in a two dimensional plane. Given the two points, what is the best way to find the maximum points on the line segment that are equidistant from each point closest to it with a minimal distant apart.

I use C#, but examples in any language would be helpful.

List<'points> FindAllPointsInLine(Point start, Point end, int minDistantApart)  
{  
//    find all points  
}

Answer 1

I'm not sure if I understand your question, but are you trying to divide a line segment like this?

Before:

A +--------------------+ B

After:

A +--|--|--|--|--|--|--+ B

Where "two dashes" is your minimum distance? If so, then there'll be infinitely many sets of points that satisfy that, unless your minimum distance can exactly divide the length of the segment. However, one such set can be obtained as follows:

1. Find the vectorial parametric equation of the line
2. Find the total number of points (floor(length / minDistance) + 1)
3. Loop i from 0 to n, finding each point along the line (if your parametric equation takes a t from 0 to 1, t = ((float)i)/n)

[EDIT] After seeing jerryjvl's reply, I think that the code you want is something like this: (doing this in Java-ish)

List<Point> FindAllPointsInLine(Point start, Point end, float distance)
{
    float length = Math.hypot(start.x - end.x, start.y - end.y);
    int n = (int)Math.floor(length / distance);
    List<Point> result = new ArrayList<Point>(n);

    for (int i=0; i<=n; i++) {  // Note that I use <=, not <
        float t = ((float)i)/n;
        result.add(interpolate(start, end, t));
    }

    return result;
}

Point interpolate(Point a, Point b, float t)
{
    float u = 1-t;
    float x = a.x*u + b.x*t;
    float y = a.y*u + b.y*t;
    return new Point(x,y);
}

[Warning: code has not been tested]

Answer 2

Find the number of points that will fit on the line. Calculate the steps for X and Y coordinates and generate the points. Like so:

lineLength = sqrt(pow(end.X - start.X,2) + pow(end.Y - start.Y, 2))
numberOfPoints = floor(lineLength/minDistantApart)
stepX = (end.X - start.X)/numberOfPoints
stepY = (end.Y - start.Y)/numberOfPoints
for (i = 1; i < numberOfPoints; i++) {
    yield Point(start.X + stepX*i, start.Y + stepY*i)
}

Answer 3

Interpreting the question as:

• Between point start
• And point end
• What is the maximum number of points inbetween spaced evenly that are at least minDistanceApart

Then, that is fairly simply: the length between start and end divided by minDistanceApart, rounded down minus 1. (without the minus 1 you end up with the number of distances between the end points rather than the number of extra points inbetween)

Implementation:

List<Point> FindAllPoints(Point start, Point end, int minDistance)
{
    double dx = end.x - start.x;
    double dy = end.y - start.y;

    int numPoints =
        Math.Floor(Math.Sqrt(dx * dx + dy * dy) / (double) minDistance) - 1;

    List<Point> result = new List<Point>;

    double stepx = dx / numPoints;
    double stepy = dy / numPoints;
    double px = start.x + stepx;
    double py = start.y + stepy;
    for (int ix = 0; ix < numPoints; ix++)
    {
        result.Add(new Point(px, py));
        px += stepx;
        py += stepy;
    }

    return result;
}

If you want all the points, including the start and end point, then you'll have to adjust the for loop, and start 'px' and 'py' at 'start.x' and 'start.y' instead. Note that if accuracy of the end-points is vital you may want to perform a calculation of 'px' and 'py' directly based on the ratio 'ix / numPoints' instead.