pontos equidistantes em um segmento de linha

Question

Vamos supor que você tem dois pontos (a, b) num plano bidimensional. Dado os dois pontos, o que é a melhor maneira de encontrar o máximo de pontos no segmento de linha que estão equidistantes de cada ponto mais próximo a ele com um distante mínimo de intervalo.

Eu uso C #, mas exemplos em qualquer língua seria útil.

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

Answer 1

Interpretando a questão como:

• Entre ponto start
• E ponto end
• Qual é o número máximo de pontos espaçados uniformemente isolada que são, pelo menos, minDistanceApart

Então, isso é bastante simples: o comprimento entre start e end dividido por minDistanceApart, arredondado para baixo menos 1. (sem a menos 1 você acabar com o número de distâncias entre os pontos finais em vez do número de pontos extras inbetween )

Implementação:

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

Se você quiser que todos os pontos, incluindo o ponto de início e fim, então você vai ter que ajustar o loop for, e começar a 'px' e 'aa' at 'start.x' e 'start.y' em vez . Note-se que se a precisão dos pontos finais é vital que você pode querer executar um cálculo de 'px' e 'aa' com base na relação 'ix / numPoints' em vez.

diretamente

Answer 2

Eu não tenho certeza se eu entendi sua pergunta, mas você está tentando dividir um segmento de linha como esta?

Antes:

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

Depois:

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

Onde "dois traços" é o seu distância mínima? Se sim, então vai haver um número infinito de conjuntos de pontos que satisfazem que, a menos que a sua distância mínima pode exatamente dividir o comprimento do segmento. No entanto, um tal conjunto pode ser obtido da seguinte forma:

1. Encontre a equação paramétrica vectorial da linha
2. Encontre o número total de pontos (piso (comprimento / minDistance) + 1)
3. Curva i de 0 a n, encontrando cada ponto ao longo da linha (se o seu equação paramétrica leva um t de 0 a 1, t = ((float) i) / n)

[EDIT] Depois de ver a resposta de jerryjvl, eu acho que o código que você quer é algo como isto: (fazer isso em 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: código não foi testado]

Answer 3

Encontre o número de pontos que se encaixam na linha. Calculam-se os passos para as coordenadas X e Y e gerar os pontos. Como assim:

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