Binäres Bild Kantenlinienerkennung "Lines-of-Sight"

Da Sie eine Bitmap haben, könnten Sie einen Bitmap-Algorithmus verwenden.

Hier ist ein funktionierendes Beispiel (in JSFiddle oder siehe unten). (Firefox, Chrome, aber nicht IE)

Pseudocode:

Zuerst klingt das ziemlich schrecklich ... Aber wirklich, es ist O(p) wo p ist die Anzahl der Pixel in Ihrem Bild.

Vollständiger Code hier, funktioniert am besten ganze Seite:

Ich würde nur die Sichtlinienkontur von P mit Strahlenkollisionen abschätzen.

Ссылка mit z.B. ein Z-Puffer ist relativ einfach. Die Kantenerkennung sieht viel komplizierter aus und erfordert wahrscheinlich ein wenig Feinabstimmung. Warum nicht einen vorhandenen Kantenerkennungsalgorithmus aus einer Bibliothek nehmen, die jemand anders abgestimmt hat, und dann einen Z-Puffercode eingeben, um die blaue Kontur aus dem Rot zu berechnen?

Erste Annäherung

Grundidee

1. Führen Sie einen Kantenerkennungsalgorithmus aus (Canny sollte es einfach machen).
2. Berechnen Sie für jeden Konturpunkt C das Triplet (slope, dir, dist) , wobei
   • slope ist die Steigung der Linie, die durch P und C
   verläuft
   • dir ist ein Bit, das gesetzt wird, wenn C rechts von P steht (auf der x Achse) und zurückgesetzt wird, wenn es sich links befindet; Es wurde verwendet, um zwischen Punkten mit gleicher Steigung, aber auf gegenüberliegenden Seiten von P zu unterscheiden
   • dist ist die Entfernung zwischen P und C .
3. Klassifizieren Sie die Menge der Konturpunkte so, dass eine Klasse die Punkte mit demselben Schlüssel (slope, dir) enthält, und behalten Sie den einen Punkt von jeder Klasse mit dem Minimum dist . Lassen Sie S die Menge dieser nächsten Punkte sein.
4. Sortiere S im Uhrzeigersinn.
5. Iteriere noch einmal durch die sortierte Menge und zeichne, wenn zwei aufeinanderfolgende Punkte zu weit voneinander entfernt sind, ein Segment dazwischen, ansonsten zeichne einfach die Punkte.

Notizen

• Sie müssen nicht wirklich die tatsächliche Entfernung zwischen P und C berechnen, da Sie nur dist verwenden, um den nächsten Punkt zu P in Schritt 3 zu ermitteln. Stattdessen können Sie% beibehalten. co_de% in C.x - P.x . Diese Information sollte Ihnen auch sagen, welcher der beiden Punkte mit der gleichen Steigung dem dist am nächsten kommt. Außerdem schluckt P den Parameter C.x - P.x (im Vorzeichenbit). Sie brauchen also nicht wirklich dir .

• Die Klassifizierung in Schritt 3 kann idealerweise durch Hashing erfolgen (also in linearer Anzahl von Schritten), aber da Double / Floats gerundet werden, müssen Sie möglicherweise kleine Fehler durch Runden der Werte zulassen von den Pisten.

Zweiter Ansatz

Grundidee

Sie können eine Art von BFS ab dir ausführen, etwa wenn Sie versuchen, das Land / die Zone zu ermitteln, in der sich P befindet. Sehen Sie sich für jedes Pixel die Pixel an, die BFS bereits besucht hat Nachbarn). Abhängig von der Verteilung der Nachbarpixel, die sich in der Sichtlinie befinden, bestimmen Sie, ob das aktuell besuchte Pixel auch in der Sichtlinie ist oder nicht. Sie können wahrscheinlich eine Art Faltungsoperator auf die benachbarten Pixel anwenden (wie bei jedem anderen Filter). Außerdem müssen Sie sich nicht sofort entscheiden, ob ein Pixel in der Sichtlinie sicher ist. Sie könnten stattdessen eine Wahrscheinlichkeit dafür berechnen, um wahr zu sein.

Notizen

• Aufgrund der Tatsache, dass Ihr Graph ein 2D-Bild ist, sollte BFS ziemlich schnell sein (da die Anzahl der Kanten in der Anzahl der Scheitelpunkte linear ist).
• Dieser zweite Ansatz beseitigt die Notwendigkeit, einen Kantenerkennungsalgorithmus auszuführen. Wenn das Land / die Zone P in wesentlich kleiner ist als das Bild, sollte die Gesamtperformance besser sein, als wenn nur ein Kantenerkennungsalgorithmus ausgeführt wird.