algorithm - 线段中的等距点

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 循环，并在 'start.x' 和 'start.y' 处开始 'px' 和 'py'。请注意，如果端点的准确性至关重要，您可能希望直接根据比率“ix / numPoints”执行“px”和“py”的计算。

Answer 2

我不确定我是否理解您的问题，但是您是否要像这样划分线段？

前：

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

后：

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

“两个破折号”是您的最小距离？如果是这样，那么将有无限多的点集满足这一点，除非您的最小距离可以精确地划分线段的长度。但是，可以按如下方式获得这样的一组：

1. 求直线的矢量参数方程
2. 求总点数（floor(length / minDistance) + 1）
3. 从 0 到 n 循环 i，找到沿线的每个点（如果您的参数方程从 0 到 1，则 t = ((float)i)/n）

[编辑] 看到 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);
}

[警告：代码未经测试]

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