Kürzeste entfernung

Kürzeste Entfernung

Für 2 Punkte A= und B= ist der Abstand
definiert durch:
d:=sqrt

du berechnest also lediglich den Abstand von einem Punkt zu allen aus dieser Liste und nimmst das Minimum.
Wenn diese Liste sehr groß ist kannst du das Verfahren verbessern wenn du Eigenschaften der Liste benutzt.
Ein Beispiel: Alle Punkte der Liste liegen auf einer Geraden.
Dann nutzt du zB Abstand Punkt - Gerade um den kürzesten Weg vom Punkt zur Geraden zu finden, und damit den Schnittpunkt, der den minimalen Abstand besitzt und auf der Geraden liegt.
Dann nimmst du den Punkt aus der Liste, der an diesem am nächsten dran liegt, sehr leicht für eine geordnete Liste.

das ist ja alles schön und gut, nur ich bräuchte eine art "Verfahren" mit dem möglichst effizient ohne womöglich die gesamte Liste nach dem nächsten punkt zu durchsuchen auf das Ergebnis komme. das mit den Vektoren hab ich mir auch schon gedacht und dann hätte ich bei einer Bildschirmauflösung von 1920*1080 mit ca 1250 pixeln in der liste
2,6 * 10^9 berechnungen und vergleiche. das ganze dann 60 mal die sekunde ist ne ganze ecke.

Ja, du sprichst aber nur von einer beliebigen Liste von Punkten.
Dafür gibt es kein effizienteres Verfahren.
Du musst schon genauer sagen was du willst.
Niemand berechnet heute alle Pixel selbstständig in seiner Software wenn diese irgendwie Graphik ausgeben soll.
Entweder kannst du wie im Beispiel die Art der Liste ausnutzen, wenn diese irgendwo eingebettet sind zum Beispiel.
Oder du nutzt die Grafikkartenfunktionalität und übergibst die Informationen an die Karte und lässt sie dein Problem lösen.
Was genau programmierst du denn?

wir wollen in ein 3D-Spiel eine Glow-Effekt einfügen. Das läuft in etwa so, dass wir das gesamte Bild rendern und dann dieses bild weiter verarbeiten. an den stellen vom bild wo glow sein soll, hat die textur einen Alpha-Wert!= 1.0
davon ausgehen schauen wir aktuell bei jedem pixel ob oben unten lins oder rechts in bestimmten abständen ein pixel mit alpha!= 1.0 ist und machen so eine Abstufung. da wir aus hardware-Gründen jedoch nur 16 Pixel pro pixel überprüfen können und nicht die exakte Entfernung kennen können wir nur einen bereich von ca. 8 pixeln wissen. daher haben wir kreise mit verschiedenen abstufungen die jeweils 8 pixel größer sind.
Wenn wir die genaue Entfernung wüssten, dann könnten wir eine eine davon abhängige exakte abstufung machen, bei der keine linien mehr erkennbar sind. Siehe Bild oben

Für genau diese Zwecke hat man Grafikkarten.
Ich kenne die befehle leider nicht, die man benutzt um Grafikkarten mir dem Problem zu "betrauen", aber sie existieren!
Für eine Grafikkarte ist ein solcher Glow-Effekt nichts anderes als eine Matrixmultiplikation, und dafür haben Grafikkarten Shader.
Such mal nach den Schnittstellen zur Grafikkarte, und das Problem wird "von jemand anderem" gelöst, der genau darauf spezialisiert ist