Äquidistante Punkte in einem Liniensegment

Question

Nehmen wir an, Sie haben zwei Punkte (a, b) in einer zweidimensionalen Ebene. In Anbetracht der beiden Punkte, was ist der beste Weg, um die maximale Punktzahl auf dem Liniensegment zu finden, die von jedem Punkt am nächsten mit einem minimalen entfernten gleich weit voneinander entfernt ist.

verwende ich C #, aber Beispiele in jeder Sprache wären hilfreich.

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

Answer 1

Die Interpretation der Frage:

• Zwischen dem Punkt start
• Und Punkt end
• Was ist die maximale Anzahl der Punkte dazwischen gleichmäßig beabstandet, dass zumindest minDistanceApart

Dann, das ist ziemlich einfach: die Länge zwischen start und end durch minDistanceApart geteilt, minus 1 abgerundet (ohne minus 1 Sie mit der Anzahl der Abstände zwischen den Endpunkten am Ende eher als die Anzahl der Extra-Punkte dazwischen )

Umsetzung:

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

Wenn Sie alle Punkte wollen, einschließlich der Start- und Endpunkt, dann werden Sie die for-Schleife einstellen müssen, um, und starten Sie ‚px‘ und ‚py‘ auf ‚start.x‘ und ‚start.y‘ statt . Beachten Sie, dass, wenn die Genauigkeit der Endpunkte von entscheidender Bedeutung ist, dass Sie eine Berechnung von ‚px‘ ausführen möchten und ‚py‘ direkt basierend auf dem Verhältnis ‚ix / numPoints‘ statt.

Answer 2

Ich bin mir nicht sicher, ob ich verstehe Ihre Frage, aber versuchen Sie, ein Liniensegment wie folgt aufzuteilen?

Bevor:

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

Nach:

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

Wo „zwei Striche“ ist Ihr Mindestabstand? Wenn ja, dann gibt es unendlich viele Sätze von Punkten, die überzeugen, dass, es sei denn, Ihr Mindestabstand genau die Länge des Segments teilen kann. Allerdings kann ein solcher Satz wie folgt erhalten werden:

1. Finden Sie die vektorielle Parametergleichung der Zeile
2. Finden Sie die Gesamtzahl der Punkte (Boden (Länge / MinDistance) + 1)
3. Schleife i von 0 bis n, jeden Punkt entlang der Linie zu finden (wenn Ihre Parametergleichung nimmt t von 0 bis 1, t = ((float) i) / n)

[EDIT] jerryjvl Antwort Nachdem ich, glaube ich, dass der Code, den Sie so etwas wie dies wollen, ist: (tut dies in 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);
}

[Warning: Code wurde nicht geprüft]

Answer 3

Hier finden Sie die Anzahl der Punkte, die auf der Linie passen. Berechnen Sie die Schritte für die X- und Y-Koordinaten und die Punkte erzeugen. Wie so:

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