Metodo efficiente per trovare il punto più vicino a un segmento di linea da un insieme di punti compresi i vertici del segmento di linea

Dovrai attraversare tutti i punti e calcolare la distanza. C'è una bella domanda su StackOverflow su come calcolare la distanza: Distanza minima tra un punto e un segmento di linea

Alcuni lavori possono essere precalcolati, dato che devi farlo più di una volta per un dato segmento di linea. Inoltre, non è necessario calcolare la distanza più piccola, ma solo la distanza più piccola al quadrato (dal momento che la quadratura è strettamente crescente). Ho convertito la risposta più votata in quella domanda in una versione Java che esegue questo calcolo preliminare (nel costruttore) ed è più facile da leggere e seguire. Sfortunatamente non conosco Python abbastanza bene da darti il codice Python, ma dovresti riuscire a capirlo.

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

Vedi l'implementazione completa qui: link

Per quel che vale, per un set statico di punti per controllare il segmento di linea rispetto a:

Il precomputing utilizzando diagrammi di voronoi ( link ) è utile in quanto riduce il problema del vicinato più vicino a una query di intersezione di una linea poligonale.

Il diagramma di voronoi è composto da poligoni. Ogni punto dall'insieme di punti che stai cercando di confrontare è all'interno del proprio poligono. Nessun punto è contenuto in più di 1 poligono e nessun altro punto si trova all'interno di quel poligono.

Se intersechi solo 1 poligono, hai la tua risposta. Se intersechi più di 1 poligono, devi controllare ciascun poligono che hai intersecato.

Il precomputo del diagramma di voronoi non sarà di aiuto per gli insiemi dinamici di punti su cui eseguire una query.

Che domanda divertente! Adoro le griglie personalmente. Mi piacciono molto, mi piacciono molto, mi piacciono molto. Voglio dividere tutto in una griglia senza motivo.

Ma il modo in cui farei una prova comincerebbe con la griglia. È possibile suddividere i punti nelle celle della griglia. Ogni cella della griglia può essere un indice a 32 bit. Ogni punto può avere un indice next che punta al punto successivo nella cella, in questo modo:

QuindipuoirasterizzarelatualineanellagrigliausandoBresenham,inquestomodo:

Orapertrovareilpuntopiùvicinoalsegmento,cercaipuntiall'internodellecelletracciatedallalinea.Senontrovialcunpunto,espandiecercatuttiipuntinellecelleadiacentiecosìviainunmodopiùsemplice.

Probabilmentequestononèl'algoritmopiùottimaleeloscenariopeggioreèquandodevifarequestotipodiricercainampiezzapermoltefasiprimaditrovareunsingolopunto,maèiltipochehosempretrovatomoltofaciledasintonizzareepuoigiocareconladensità/ruvidezzaappropriatadiciascunacelladellagriglia(cellepiùpiccoleopiùgrandi)inbaseaituoiinput.Sepuoipermettertiunpostprocessodopoaversuddivisoipuntinellecelle,puoieseguireunpassaggiodicompatibilitàdellacacheperassicurarticheognipuntodiciascunacellasiacontiguoalpuntosuccessivonellacellaperlocalitàspaziale.

Suppongocheoltreadavereuncaricodipuntidiunabarca,haianchemoltisegmentidilineadacercarecontro.Hoancheutilizzatoquestotipodisoluzionetrannechein3dimensionieilmioobiettivononeraquelloditrovareilpuntopiùvicinoaunsegmento,maqualipuntieranopiùviciniaqualisegmenti.Ilmioobiettivoeratrovarlipersegmentidilinee3dcherappresentanounossoinunagerarchiascheletrica,inquestomodo:

Utilizzodiunrasterizzatore3DdiBresenhamcheutilizzaunapproccioditipovoxel:

...perprodurrequindipesiosseipericaratteri:

...einiziaadanimareem:

In uno stress test sono stato in grado di generare pesi di skinning per una mesh con un milione di vertici (punti) contro poche centinaia di ossa (segmenti di linea 3D) in circa 20ms usando semplicemente questo semplice vecchio approccio a griglia. Volevo quel tipo di esibizione in modo che gli artisti potessero solo disegnare le ossa nel personaggio e iniziare a animarlo, modificare le posizioni dell'osso, ecc. Senza aspettare ogni volta una barra di progresso.

In prodotti concorrenti ho trovato spesso che questo processo può richiedere alcuni minuti e sono disposto a scommettere che stanno utilizzando algoritmi più elaborati e più intelligenti di una semplice vecchia griglia. In realtà sono molto incompetente matematicamente e algoritmicamente, ma sono riuscito a superare i colleghi un milione di volte più intelligente di me utilizzando soluzioni muti come questo appena sintonizzati molto e giocare con l'idea di bit e byte invece di un KD-albero con un taglio-bordo algoritmo di divisione mediana. A volte una soluzione più stupida come questa può essere perfetta per le tue esigenze, a patto che sia efficiente in termini di schemi di accesso alla memoria e così via rispetto a soluzioni molto più elaborate come BVH, alberi KD, alberi quadrangolari, alberi. Ovviamente non consiglio di scrivere un raytracer usando una griglia tridimensionale, ci sono dei limiti, ma puoi fare molte cose velocemente in modo competitivo usando solo una semplice vecchia griglia.

Che tipo di applicazione ha questo in 2 dimensioni con lo scafo convesso e tutto il resto? Mi piacerebbe implementarlo ora e vedere come la griglia si adatta in tal caso.