Poisson-Disk-Sampling: Ein Algorithmus, der eine fast 1.000-seitige Mathematikarbeit in einer Seite übertrifft
Poisson Disk Sampling
Robert Bridsons Algorithmus aus dem Jahr 2007 löst ein zentrales Problem in Computergrafik und Simulation: das Platzieren von Punkten mit Mindestabstand. Der Artikel erklärt den Algorithmus klar und verständlich, präsentiert zwei Verbesserungen, die die Effizienz drastisch steigern, und zeigt Anwendungen wie Stippling. Zudem wird ein neuerer, deterministischer Ansatz von Scott A. Mitchell vorgestellt, der maximale und uniforme Verteilungen ohne Rejection Sampling erzeugt.
Im krassen Gegensatz dazu veröffentlichte Robert Bridson 2007 ein einseitiges Paper mit fast 1.000 Zitaten, das in weniger als 10 Minuten vollständig zu verstehen ist.
- akkartik
Immer noch eine der befriedigendsten Debug-Oberflächen, die ich je entwickelt habe.
- jacobolus
Für manche könnte https://observablehq.com/@fil/poisson-distribution-generator... nützlich sein.
- Terr_
> Betrachten Sie den Fall, dass der Algorithmus einen Punkt p platziert und dann seinen Ring abtastet, um einen neuen Punkt q zu erhalten.
Ich war eine Weile verwirrt, weil ich dachte, p und q wären hier vertauscht, im Vergleich zur Visualisierung unten. [0] Aber ich denke jetzt, dass ich übersehen habe, dass die Visualisierung zwei Punkte zeigt, die bereits fest etabliert sind, und die Frage ist, wo ein potenzieller dritter (unsichtbarer, unbenannter) Punkt platziert werden könnte.
Metaphorisch gesprochen geht es also darum, eine neue Reiserichtung zu wählen, die nicht garantiert in die eigenen letzten Schritte führt.
[0] Man könnte sagen, ich habe Probleme, meine p's und q's im Auge zu behalten.