Punkt innerhalb oder ausserhalb einer Polylinie?

03/09/2007 - 08:52 von Wolfgang Kraus | Report spam
Hallo Newsgroup,

ich will innerhalb meiner DB (Access 2000) prüfen, ob ein bestimmter
Punkt (mit x,
y, z Koordinaten) innerhalb einer Polylinie liegt oder nicht (die
Berechnung soll in der Ebene stattfinden, die 3. Dimension soll
ignoriert werden!) .

Die Polylinie ist in meiner DB in einer Punkte-Tabelle gespeichert
(Felder: ID (lfd. Nr des Punktes), x,y,z, ID1 (die Nr. der
Polylinie)). Ich will für jeden eingegebenen Punkt prüfen, ob er
innerhalb einer der Polylinien liegt.

Eventuell wàre auch das umgekehrte Vorgehen möglich, dass ich die
Polylinien durchgehe, und für jede Polylinie prüfe, ob der jeweilige
Punkt sich
darin befindet.

Ich habe recherchiert und gesehen, das es zahlreiche Verfahren für
diese Berechnungen gibt, habe auch Code (in C bzw. in C++) gefunden,
weiss aber nicht, welcher der schnellste ist bzw. wie man den von C++
nach VB konvertiert.

Hat jemand so etwas schon einmal mit VB gemacht? Für jeden Hinweis bin
ich sehr dankbar,

Viele Grüße

Wolfgang Krauss
 

Lesen sie die antworten

#1 Michaela Meier
03/09/2007 - 11:42 | Warnen spam
"Wolfgang Kraus" schrieb im Newsbeitrag
news:

Hat jemand so etwas schon einmal mit VB gemacht?




Ich verstehe das so, daß Du herausfinden willst, ob ein Punkt P innerhalb
eines Polygons liegt, das von einem geschlossenen Linienzug begrenzt wird.

Ich habe das damals nach der "Schnittpunkt"-Methode gelöst:
Schneidet die Verbindungslinie "P nach JWD (janzweitdraußen)" eine ungerade
Anzahl an Strecken, so liegt der Punkt innerhalb der Figur.
Ist nichts weiter als simple Vektorrechnung und ganz bestimmt auch unter den
Codebeispielen zu finden, die Du schon gesehen hast.
Die Geschwindigkeit hàngt dabei natürlich deutlich von der Gesamtzahl der
Linien pro Figur ab -für meine Zwecke war diese Lösung schnell genug, so daß
ich die anderen Algorithmen nicht ausprobiert habe - aber ich denke der
Rechenaufwand ist vergleichbar.

Schmutzig und langsam geht es natürlich auch: Polygon zeichnen, FillRegion
drüberziehen und dann fragen, welche Farbe das Pixel an der Position des
Punktes hat ;-)

Falls Du noch nicht drauf gestoßen sein solltest:
http://rw7.de/ralf/inffaq/polygon.html hat einen schönen Überblick. Der
"schnelle Aussortiertest" wàre erwàhnenswert.

Michaela

Ähnliche fragen