線分内の等距離点

Question

2 次元平面上に 2 つの点 (a 、 b) があると仮定します。2 つの点が与えられた場合、線分上の最も近い各点から最小の距離で等距離にある最大の点を見つける最良の方法は何ですか。

私は 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

「ダッシュ 2 つ」が最小距離です。その場合、最小距離がセグメントの長さを正確に分割できない限り、それを満たす点のセットが無限に存在することになります。ただし、そのようなセットの 1 つは次のように取得できます。

1. 直線のベクトルパラメトリック方程式を求めます
2. 合計ポイント数を求めます (floor(length / minDistance) + 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)
}