Эквидистантные точки в отрезке - PullRequest
Новая
       10

Эквидистантные точки в отрезке

1 голос
/ 29 мая 2009

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

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

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

Ответы [ 3 ]

4 голосов
/ 29 мая 2009

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

  • Между точками 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».

2 голосов
/ 29 мая 2009

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

До:

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

После того, как:

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

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

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

[EDIT] После просмотра ответа jerryjvl я думаю, что код, который вам нужен, выглядит примерно так: (делает это в 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);
}

[Внимание: код не был протестирован]

1 голос
/ 29 мая 2009

Найдите количество точек, которые поместятся на линии. Рассчитайте шаги для координат 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)
}
...