Äquidistante Punkte in einem Liniensegment

Question

Angenommen, Sie haben zwei Punkte (a, b) in einer zweidimensionalen Ebene. Mit den zwei Punkten ist es am besten möglich, die maximalen Punkte auf dem Liniensegment zu finden, die äquidistant von jedem Punkt sind, der ihr am nächsten liegt, mit einem minimalen Abstand voneinander.

Ich benutze C#, aber Beispiele in jeder Sprache wären hilfreich.

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

Answer 1

Interpretation der Frage:

• Zwischen Punkt start
• Und Punkt end
• Was die maximale Anzahl an Punkten zwischen gleichmäßig verteilt, das sind mindestens minDistanceApart

Dann ist das ziemlich einfach: die Länge zwischen start und end dividiert durch minDistanceApart, abgerundet minus 1. (ohne die minus 1 enden Sie mit der Anzahl der Abstände zwischen den Endpunkten und nicht die Anzahl der Extrapunkte 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, und starten Sie ‚px‘ und ‚py‘ at 'einstellen müssen, um start.x 'und' start.y 'stattdessen. Wenn die Genauigkeit der Endpunkte entscheidend ist, sollten Sie eine Berechnung von 'px' und 'py' direkt basierend auf dem Verhältnis 'ix/numPoints' durchführen.

Answer 2

Ich bin mir nicht sicher, ob ich Ihre Frage verstehe, aber versuchen Sie, ein Liniensegment so zu teilen?

Vorher:

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

Nach:

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

Wo ist "zwei Bindestriche" der Mindestabstand? Wenn dies der Fall ist, dann gibt es unendlich viele Sätze von Punkten, die das erfüllen, es sei denn, Ihr minimaler Abstand kann genau die Länge des Segments teilen. Jedoch kann ein solcher Satz wie folgt erhalten werden:

1. Finden der vektoriellen parametrischer Gleichung der Geraden
2. die Gesamtzahl der Punkte (Boden (Länge/MinDistance) + 1)
3. Schleife I aus 0 bis n, jeden Punkt entlang der Linie zu finden (nimmt, wenn Ihre Parametergleichung bei Temperaturen von 0 bis 1, t = ((float) i)/n)

[EDIT] nach jerryjvl Antwort sehen, ich glaube, dass der Code, den Sie wollen, ungefähr so ​​lautet: (tun Sie 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

Suchen Sie die Anzahl der Punkte, die auf die Linie passen.Berechnen Sie die Schritte für X- und Y-Koordinaten und generieren Sie die Punkte. 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) 
}