algorithm - 线段中的等距点

Question

假设您在二维平面上有两个点 (a , b)。给定这两个点，找到线段上最大点的最佳方法是什么，这些点与离它最近的每个点等距且相距最小。

我使用 C#，但任何语言的示例都会有所帮助。

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

Answer 1

将问题解释为:

• 点之间 开始
• 并点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”的计算。