Algorithmus: Sichtlinen überprüfen

Hi!

Für ein Projekt habe ich die Aufgabe mit digitalen Landkarten zu arbeiten und jetzt bin ich grad dabei eine Funktion zu schreiben, die die überprüft, ob eine Sichtlinie zwischen 2 Punkten existiert.

Die Karte liegt als Int-Array im Speicher und besitzt folgende Struktur (beispielhaft):

154 156 143 140 138 ...
155 152 140 128 120 ...
160 152 141 130 123 ...
... ... ... ... ...

sie ist natürlich um vielfaches größer und nach rechts lauft die x koordinate und nach unten die pos. y koordinate. an den punkten steht die höhe in metern. die auflösung zwischen den diskreten werten beträgt 25 meter. eine routine zur interpolation zwischen den diskreten werte habe ich bereits geschrieben, insofern ist es mir auch möglich zum beispiel einen wert zwischen 2 punkten zu schätzen.

nun ja, wie kann ich nun einen algorithmus formulieren, der mir sagt ob zwischen 2 punkten P1(x1,y1,z1) und P2(x2,y2,z2) eine sichtline besteht, oder ob es durch gelände verdeckt wird.

ich habe bereits eine idee, diese will ich aber noch nicht posten, weil vielleicht ja sonst die kreativen geister schon etwas vorbelastet wären

ideas? tia

ringi: das mit den kanten check ich jetzt nicht? woher nimmst du die kanten ?

ich hätte es so gemacht: ich hätte eine gerade strecke zwischen den beiden punkten (x1,y1)->(x2,y2) konstruiert, die steigung der sichtgerade berechnet höhe(x1,y1)->höhe(x2,y2), und hätte jeden punkt auf der gerade darauf geprüft, ob er höher ist, als die sichtgerade in diesem punkt.

die interpolation der höhenwerte ist als avg nett, aber für eine pessimistische-sichtanalyse könntest du das maximum der umgebenden 4 punkte verwenden.

falls du das für funkstrecken planst, mußt du evt noch die fresnelzone beachten - in dem fall wird die sichtgerade zu einem eliptoiden; oder du verwendest als näherung das max der fresnelzone für den ganzen verlauf.

danke erstmal für die antworten!

ich habs mir auch so vorgestellt, dass ich der gerade nachlaufe. aber ich bin mir noch nicht ganz sicher, wie ich es schaffe der gerade entlangzugehen. ich könnte es zum beispiel den vektor vom punkt 1 zum punkt 2 aufstellen, ihn irgendwie normieren auf einen ziemlich kleinen vektor und ihn entlanglaufen. allerdigns bin ich mir net ganz sicher, ob ich dann wirklich ankomm am endpunkt wenn ich das 10000 mal iteriere, weil die numerik ist ja sicher nicht ganz exakt (vermute ich).

also so:
zuerst x abwandern, und die y-höhen interpolieren/maximum wählen.

dann analag dazu, y abwandern und die höhen zwischen den x koordinaten interpolieren.

schließlich hat man alle relevanten punkte angesehen:

herzlichen dank für eure tips. wart mir echt eine große hilfe und jetzt gehts fröhlich ans programmieren