Равноудаленные точки на отрезке прямой

Question

Предположим, у вас есть две точки (a, b) на двумерной плоскости.Учитывая две точки, каков наилучший способ найти максимальное количество точек на отрезке прямой, которые равноудалены от каждой ближайшей к нему точки с минимальным расстоянием друг от друга?

Я использую C #, но примеры на любом языке были бы полезны.

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

Answer 1

Интерпретируя вопрос как:

• Между точками start
• И точка end
• Каково максимальное количество точек между ними, расположенных равномерно, которые, по крайней мере, minDistanceApart

Тогда это довольно просто:длина между start и end разделенный на minDistanceApart, округленный в меньшую сторону минус 1.(без минус 1 вы получаете количество расстояний между конечными точками, а не количество дополнительных точек между ними)

Реализация:

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;
}

Если вам нужны все точки, включая начальную и конечную, то вам придется настроить цикл for и вместо этого запускать 'px' и 'py' в 'start.x' и 'start.y'.Обратите внимание, что если точность конечных точек жизненно важна, вы можете вместо этого выполнить вычисление 'px' и 'py' непосредственно на основе соотношения 'ix / numPoints'.

Answer 2

Я не уверен, правильно ли я понял ваш вопрос, но вы пытаетесь разделить отрезок таким образом?

До того, как:

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

После:

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

Где "два тире" - это ваше минимальное расстояние?Если это так, то будет бесконечно много наборов точек, которые удовлетворяют этому, если только ваше минимальное расстояние не может точно разделить длину сегмента.Однако один такой набор может быть получен следующим образом:

1. Найдите векторное параметрическое уравнение прямой
2. Найдите общее количество точек (этаж (длина / расстояние до ума) + 1)
3. Выполните цикл i от 0 до n, находя каждую точку вдоль линии (если ваше параметрическое уравнение принимает значение t от 0 до 1, t = ((float)i) / n)

[РЕДАКТИРОВАТЬ] Увидев ответ jerryjvl, я думаю, что код, который вам нужен, примерно такой:(делаю это на Java-языке)

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);
}

[Предупреждение:код не был протестирован]

Answer 3

Найдите количество точек, которые поместятся на линии.Вычислите шаги для координат X и Y и сгенерируйте точки.Вот так:

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)
}