wie testet man eine Flaeche < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:08 So 10.10.2004 | | Autor: | Norbert |
Hallo,
gegeben ist eine unregelmaessige Flaeche durch ihre Koordinaten in einem kartesischen System.
Gesucht wird ein Algoritmus, der bestimmt, ob eine zufaellige Koordinate innerhalb oder ausserhalb der gegebenen Flaeche liegt.
Da ich nicht weiss, wie man dieses Problem genau benennt, habe ich mich fuer dieses Forum entschieden.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:40 So 10.10.2004 | | Autor: | Paulus |
Hallo Norbert
> Hallo,
>
> gegeben ist eine unregelmaessige Flaeche durch ihre
> Koordinaten in einem kartesischen System.
> Gesucht wird ein Algoritmus, der bestimmt, ob eine
> zufaellige Koordinate innerhalb oder ausserhalb der
> gegebenen Flaeche liegt.
> Da ich nicht weiss, wie man dieses Problem genau benennt,
> habe ich mich fuer dieses Forum entschieden.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
Ich glaube, wenn jemand diese Frage vernünftig beantworten soll, dann solltest du sie etwas präziser formulieren.
Es gibt ja geschlossene Flächen im [mm] $\mathbb{R}^{3}$ [/mm] (Zum Beispiel Seifenblasen, bevor sie geplatzt sind) oder auch im [mm] $\mathbb{R}^{2}$ [/mm] (Zum Beispiel Kreise, Ellipsen, Polygone)
Und was soll das denn Bedeuten: die unregelmässige Fläche ist durch ihre Koordinaten gegeben?
Ich kann mir darunter wirklich nichts vorstellen.
Befindest du dich etwa auf einer Ebene, und es ist ein Polygon durch die Koordinaten seiner Eckpunkte gegeben?
Mit lieben Grüssen
Paul
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:03 Mo 11.10.2004 | | Autor: | Norbert |
Hallo Paulus,
vielen Dank fuer Deine Hinweise - hier meine Praezisierung:
In einer Ebene sind Polygone durch die Koordinaten ihrer Eckpunkte gegeben.
Fuer eine zufaellige Koordinate soll das dazugehoerige Poligon ermittelt werden.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 10:55 Mo 11.10.2004 | | Autor: | Norbert |
Hallo Paulus,
die Trivialitaet des Problemes kann ich nicht einschaetzen.
Zumindestens gehoert es zur den Grundtechniken im WWW
mit sogenannten ![[]](/images/popup.gif) ImageMaps umgehen zu koennen.
Von daher muss eine gute und schnelle Umsetzung schon existieren.
Der Artikel von Frau Heine zeigt zumindest den moeglichen Weg auf:
- eine Grobentscheidung durch Punkt-im-Rechteck-Test
- anschliessende Feinauswertung mit dem Theorem von Jordan
- oder etwas groeber nach dem Rasterverfahren
Letzteres wird IMHO von den aktuellen Browsern fuer ImageMaps angewendet.
Vielleicht finde ich ja ein dokumentiertes Verfahren mit Deiner Suchangabe fuer Google.
Deshalb schon mal vielen Dank fuer die Hilfe ...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:21 Mo 11.10.2004 | | Autor: | Marc |
Hallo Norbert,
> die Trivialitaet des Problemes kann ich nicht
> einschaetzen.
> Zumindestens gehoert es zur den Grundtechniken im WWW
> mit sogenannten
> ImageMaps
> umgehen zu koennen.
> Von daher muss eine gute und schnelle Umsetzung schon
> existieren.
Jetzt verstehe ich erst, dass es sich um ein zwei-dimensionales Problem handelt.
Wie effizient soll denn das Verfahren sein?
Oder anders gefragt: Wie häufig ändern sich die Koordinaten des Polygons und wie häufig soll die Punkteprobe durchgeführt werden?
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:19 Mo 11.10.2004 | | Autor: | Norbert |
Hallo Marc,
ueber die Haeufigkeit kann ich ganz allgemein nichts sagen (vorlaeufig).
Die Koordinaten der Flaechen liegen in einer SQL-Datenbank und werden
sich sicher nicht haeufig aendern.
Aber der Umfang der Sammlung wird fortlaufend zunehmen.
Wie oft das Problem: "In welcher Flaeche liegt dieser Punkt?"
auftreten wird kann man derzeit auch noch nicht abschaetzen.
Ich stelle mir das so vor, dass ausgehend von der durchschnittlichen
X-Y-Ausdehnung der Flaechen ein "unscharfes" Zielgebiet (Rechteck)
ermittelt wird.
Dann werden de Koordinaten der Flaechen, die mindestens mit einen
Punkt im Zielgebiet liegen ermittelt, um daraus die "Getroffene" zu
bestimmen.
Nur das WIE, macht mir derzeit noch einigen Kummer ... 
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:02 Mo 11.10.2004 | | Autor: | Marc |
Hallo Norbert!
Wir haben also eine Liste von Punkten [mm] $P_1=(x_1,y_1),P_2(x_2,y_2),\ldots,P_n(x_n,y_n)$ [/mm] mit [mm] $P_1=P_n$, [/mm] die das Polygon bestimmen und einen Punkt $Q(a,b)$ von dem wir gerne wissen wollen, ob er innerhalb des Polygons liegt.
Der Einfachheit halber nenne ich die die Strecken [mm] $s_i:=\overline{P_iP_{i+1}}$, [/mm] so dass das Polygon aus den n-1 Strecken [mm] $s_1,\ldots,s_{n-1}$ [/mm] gebildet wird.
Ich würde so vorgehen, zunächst vielleicht nur die Idee (ich hoffe, sie ist richtig, denn sie ist überraschend einfach):
Durch den Punkt Q zeichne eine vertikale Hilfslinie.
Nun ermittle ich alle Strecken [mm] s_i, [/mm] die die vertikale Hilfslinie schneiden, und bringe diese Strecken in die Reihenfolge der y-Koordinaten ihrer Schnittpunkte mit der Hilfslinie.
Übrigens erwarte ich dabei -- von Spezialfällen abgesehen, eine gerade Anzahl Strecken, die die vertikale Hilfslinie schneiden
Jetzt schaue ich mir die y-Koordinate des Punktes Q an und ermittle seine Position in der Liste der Strecken -- nur, wenn sich der Punkt Q an einer geraden Position in der Liste befindet (also an 2. Position, 4. Position), liegt er innerhalb des Polygons.
Das war's.
Rechnerisch aufwendig ist also nur die Bestimmung des Schnittpunkts der Hilfslinie mit den in Frage kommenden Strecken; der Rest ist Sortieren eines Feldes (zur Ermittlung der in Frage kommenden Strecken) und eine Suche im Feld der in Frage kommenden Strecken (zur Positionsbestimmung von Q).
Programmiertechnisch aufwendig wird dann noch die Beachtung der Spezialfälle (z.B. senkrechte Strecken).
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:15 Mo 11.10.2004 | | Autor: | Norbert |
Hallo Marc,
vielen Dank!
Das sollte als Arbeitsrichtlinie erst mal ausreichen.
|
|
|
|
