www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Sonstiges" - wie testet man eine Flaeche
wie testet man eine Flaeche < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

wie testet man eine Flaeche: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
wie testet man eine Flaeche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                
Bezug
wie testet man eine Flaeche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
        
Bezug
wie testet man eine Flaeche: Antwort
Status: (Antwort) fertig Status 
Datum: 08:32 Mo 11.10.2004
Autor: Paulus

Hallo Norbert

das Problem ist gar nicht trivial.

Vielleicht hilft dir aber dieser Link ein Wenig:

[]http://www.bauinf.tu-cottbus.de/Education/GIS/katja0001/datenanalyse.pdf

Ich habe das gefunden über die Google-suche "Punkt im Polygon"

Mit lieben Grüssen

Paul


Bezug
                
Bezug
wie testet man eine Flaeche: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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 []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 ...

Bezug
                        
Bezug
wie testet man eine Flaeche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                
Bezug
wie testet man eine Flaeche: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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 ... ;-)

Bezug
                                        
Bezug
wie testet man eine Flaeche: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                
Bezug
wie testet man eine Flaeche: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:15 Mo 11.10.2004
Autor: Norbert

Hallo Marc,

vielen Dank!
Das sollte als Arbeitsrichtlinie erst mal ausreichen.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de