Método eficiente para encontrar o ponto mais próximo de um segmento de linha a partir de um conjunto de pontos, incluindo os vértices do segmento de linha

5

Digamos que eu tenha uma lista de pontos (no meu caso, objetos pontuais em uma implementação do Python). Eu então tenho um segmento de linha conectando dois desses pontos.

Eu quero saber se existe uma maneira de encontrar com eficiência o ponto da lista mais próxima do segmento de linha. Percebo que posso percorrer todos os pontos e verificar as distâncias individualmente, depois selecionar a menor distância, mas espero finalmente escalar o programa para lidar com talvez milhões de pontos. Então, você sabe, talvez algo mais eficiente do que isso?

Se isso ajudar, em termos de CCW, todos os pontos que estão sendo questionados devem ser "à esquerda" / "abaixo" ou "à direita" / "acima" do segmento de linha; Não acredito que minha implementação envolva a verificação de pontos em ambos os lados do segmento.

Os pontos serão objetos pontuais com coordenadas (x, y) e algum outro lixo não diretamente relevante para esta questão. Os segmentos de linha são atualmente implementados como objetos contendo referências a objetos de dois pontos (seus vértices) e seu comprimento.

Como mencionei, isso faz parte de uma implementação do Python. Eu estou tentando projetar uma maneira de encontrar um casco côncavo para um conjunto de pontos (dados alguns parâmetros pré-definidos de como decidir se um ponto não no casco convexo está no casco côncavo ou não). Eu quero encontrar o casco convexo primeiro, então para cada segmento de linha no casco convexo encontrar o ponto mais próximo a ele, faça um triângulo com aquele ponto, então decida se aquele triângulo tem "apagamento tal que o ponto interno está agora no casco". .

Considerei colocar isso em matemática, mas não preciso de uma equação de distância - preciso de ajuda com um algoritmo eficiente para encontrar pontos mais próximos a um segmento de linha. Note também que não estou procurando o ponto mais próximo em uma linha para um ponto de entrada; Estou procurando o ponto mais próximo de um conjunto para um segmento de linha de entrada.

Obrigado a todos!

    
por acm_myk 20.01.2015 / 21:02
fonte

3 respostas

6

Você terá que percorrer todos os pontos e calcular a distância. Há uma ótima pergunta no StackOverflow sobre como calcular a distância: Distância mais curta entre um ponto e um segmento de linha

Alguns dos trabalhos podem ser pré-calculados, já que você precisa fazer isso mais de uma vez para um determinado segmento de linha. Você também não precisa descobrir a menor distância, apenas a menor distância ao quadrado (já que a quadratura está aumentando estritamente). Eu converti a resposta mais votada nessa pergunta para uma versão Java que faz esse pré-cálculo (no construtor), e é mais fácil de ler e seguir. Infelizmente eu não conheço o Python bem o suficiente para fornecer código Python, mas você deve ser capaz de descobrir isso.

import java.util.Arrays;
import java.util.List;

public class LineSegment {
    public static class Point {
        public final double x;
        public final double y;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return "(" + x + "," + y + ")";
        }
    }

    public static void main(String[] args) {
        LineSegment segment = new LineSegment(new Point(0, 3), new Point(2, 0));
        List<Point> pointList =
                Arrays.asList(new Point[] { new Point(-5, 3), new Point(1, 1),
                        new Point(2, 3), new Point(0, 5) });

        Point answer = segment.closestPoint(pointList);
        System.out.println("The closest point is: " + answer);
    }

    private static double sqr(double x) {
        return x * x;
    }

    private static double distanceSquared(Point v, Point w) {
        return sqr(v.x - w.x) + sqr(v.y - w.y);
    }

    private final Point firstSegPoint;
    private final Point secondSegPoint;
    private final double segmentDistance;
    private double xDifference;
    private double yDifference;

    public LineSegment(Point firstSegPoint, Point secondSegPoint) {
        this.firstSegPoint = firstSegPoint;
        this.secondSegPoint = secondSegPoint;
        this.segmentDistance = distanceSquared(firstSegPoint, secondSegPoint);
        this.xDifference = secondSegPoint.x - firstSegPoint.x;
        this.yDifference = secondSegPoint.y - firstSegPoint.y;
    }

    public Point closestPoint(List<Point> pointList) {
        double minDistance = Double.POSITIVE_INFINITY;
        Point answer = null;

        for (Point point : pointList) {
            double distSquared = distToSegmentSquared(point);
            if (distSquared < minDistance) {
                answer = point;
                minDistance = distSquared;
            }
        }

        return answer;
    }

    private double distToSegmentSquared(Point input) {
        if (segmentDistance == 0)
            return distanceSquared(input, firstSegPoint);

        double xComponent = (input.x - firstSegPoint.x) * xDifference;
        double yComponent = (input.y - firstSegPoint.y) * yDifference;
        double t = (xComponent + yComponent) / segmentDistance;
        if (closestPointIsFirst(t))
            return distanceSquared(input, firstSegPoint);
        if (closestPointIsSecond(t))
            return distanceSquared(input, secondSegPoint);
        Point closestPointOnLine =
                new Point(firstSegPoint.x + t * xDifference, firstSegPoint.y
                        + t * yDifference);
        return distanceSquared(input, closestPointOnLine);
    }

    private boolean closestPointIsFirst(double t) {
        return t < 0;
    }

    private boolean closestPointIsSecond(double t) {
        return t > 1;
    }
}

Veja a implementação completa aqui: link

    
por 20.01.2015 / 21:41
fonte
1

Por que vale a pena, para um conjunto estático de pontos, verificar o segmento de linha em relação a:

A pré-computação usando diagramas de voronoi ( link ) é útil, pois reduz o problema do vizinho mais próximo a uma consulta de interseção de linha de polígono.

O diagrama de voronoi é composto de polígonos. Cada ponto do conjunto de pontos que você está tentando comparar está dentro de seu próprio polígono. Nenhum ponto está contido em mais de um polígono e não há outros pontos dentro desse polígono.

Se você apenas cruzar um polígono, terá sua resposta. Se você cruzar mais de um polígono, deverá verificar cada polígono que cruzou.

A pré-computação do diagrama de voronoi não ajudará em conjuntos dinâmicos de pontos para consulta.

    
por 24.01.2015 / 16:31
fonte
0

Que pergunta divertida! Eu amo grades pessoalmente. Eu amo em, eu amo em, eu amo em. Eu quero particionar tudo em uma grade sem motivo.

Mas a maneira como eu tentaria isso começaria com a grade. Você pode particionar os pontos nas células da grade. Cada célula da grade pode ser um índice de 32 bits. Cada ponto pode ter um índice next apontando para o próximo ponto na célula, assim:

EntãovocêpoderasterizarsualinhanagradeusandoBresenham,assim:

Agora,paraencontraropontomaispróximodosegmento,procureospontosdentrodascélulasplotadospelalinha.Sevocênãoencontrarnenhumponto,entãoexpandaeprocureportodosospontosnascélulasvizinhas,eassimpordiante,deumamaneirageral.

Esteprovavelmentenãoéoalgoritmomaisidealeopiorcenárioéquandovocêtemquefazeressetipodepesquisaporváriasfasesantesdeencontrarumúnicoponto,maséotipoqueeusempreacheimuitofácildeajustarevocêpodejogarcomadensidade/grossuraapropriadadecadacéluladagrade(célulasmenoresvs.célulasmaiores)combasenassuasentradas.Sevocêpuderpagarumpós-processamentoapósparticionarospontosnascélulas,poderáfazerumpassedeadequaçãoaocacheparagarantirquecadapontoemcadacélulasejacontíguoaopróximopontonacélulaparaalocalidadeespacial.

Estouassumindoque,alémdeterummontedepontos,vocêtambémtemmuitossegmentosdelinhaparapesquisar.Eutambémuseiessetipodesolução,excetoem3dimensões,emeuobjetivonãoeraencontraropontomaispróximodeumsegmento,masquaispontosestavammaispróximosdequaissegmentos.Meuobjetivoeraencontrá-losparasegmentosdelinha3drepresentandoumossoemumahierarquiadeesqueleto,daseguinteforma:

Usandoumrasterizador3Dbresenhamusandoumtipodeabordagemvoxel:

...paraproduzirpesosdeossoparacaracteres:

...ecomeceaanimar'em:

Em um teste de estresse, consegui gerar os pesos de esfola para uma malha com um milhão de vértices (pontos) contra algumas centenas de ossos (segmentos de linha 3d) em cerca de 20ms usando essa abordagem de grade burra. Eu queria esse tipo de performance para que os artistas pudessem desenhar os ossos no personagem e começar a animá-lo, ajustar as posições dos ossos, etc. sem esperar por uma barra de progresso a cada vez.

Em produtos concorrentes, muitas vezes descobri que esse processo pode levar alguns minutos e estou disposto a apostar que estão usando algoritmos muito mais sofisticados e mais inteligentes do que uma grade simples e antiga. Na verdade, sou muito incompetente matematicamente e algoritmicamente, mas consegui superar colegas um milhão de vezes mais inteligentes do que eu usando soluções idiotas como essa, apenas ajustando muito e brincando com a ideia de bits e bytes em vez de uma árvore KD com uma ponta algoritmo de divisão mediana. Às vezes, uma solução mais burra como essa pode ser perfeita para suas necessidades, desde que seja eficiente em termos de padrões de acesso à memória e assim por diante, em oposição a soluções muito mais sofisticadas, como BVHs, KD-trees, quad-trees, octrees. É claro que eu não recomendo escrever um raytracer usando uma grade tridimensional, há limites, mas você pode fazer muitas coisas competitivamente rápido usando apenas uma grade antiga.

Que tipo de aplicação isso tem em 2 dimensões com o casco convexo e tudo mais? Eu quero implementá-lo agora e ver o quão bem as tarifas da rede nesse caso.

    
por 20.12.2017 / 08:45
fonte