Mathematisches Problem: Punkt in Fläche???

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

1

Tuesday, February 25th 2003, 10:20am

Hallo an alle!
Ich stehe hier vor einem mathematischen Problem, das gelöst werden will(muss)!!!

Ich möchte wissen, wie kann man herausfinden, ob ein beliebiger Punkt in so einer ähnlichen Fläche liegt???
Die Fläche ist nur durch Punkte vorgegeben. Es können beliebig viele sein. Ausserdem liegt die Fläche mit beiden Seiten auf den x- und y-Achsen. Ist das Finden, ob der Punkt darin liegt mit diesen Angaben möglich??? Wenn ja, dann wie???
mfg
MAX

Go to the top of the page

silence

Junior Schreiberling

Posts: 177

Date of registration: Dec 11th 2001

Location: reagenzglas

Occupation: tellerwäscher

2

Tuesday, February 25th 2003, 11:07am

Quoted

Original von MAX
Hallo an alle!
Ich stehe hier vor einem mathematischen Problem, das gelöst werden will(muss)!!!
[

Das Problem ist nicht sonderlich schwierig zu lösen, aber dumm in Worte zu fassen.

Es wird in dem <b>Skript "Einführung in die Graphische Datenverarbeitung 1"</b> von Prof. Wolter sehr anschaulich gelöst.

"Wir stecken immer in der Scheisse, nur die Tiefe ändert sich."

(Ein unbekannter Softwareentwickler)

Go to the top of the page

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

3

Tuesday, February 25th 2003, 11:22am

hmm...

Das ist sehr gut!
Ich habe aber das Skript nicht. Wo kriege ich das her???
mfg
MAX

Go to the top of the page

T2k

Erfahrener Schreiberling

Posts: 339

Date of registration: Oct 9th 2002

Location: da drüben, gleich dort.

Occupation: Warum? Hmm, weil ich sonst nix mit meiner Zeit anzufangen weiß :D

4

Tuesday, February 25th 2003, 12:02pm

is doch ganz einfach

also als erstes ziehste ne linie von dem punkt in eine beliebige richtung und solang das sie auf jedenfall das polygon verlassen würde, dann zählst du die schnitte zwischen dieser linie und den randlinien des polygons. Ist die Anzahl grade biste außerhalb, ungerade innerhalb, eckpunkte des polygons müssen gesondert behandelt werden...

T2k

Die zweithäufigste Todesursache eines Soldaten ist das Gewicht seines Rückentornisters ("http://olnigg.de/" Aug05/Nr120)

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

5

Tuesday, February 25th 2003, 12:50pm

Quoted

Original von MAX
Ich möchte wissen, wie kann man herausfinden, ob ein beliebiger Punkt in so einer ähnlichen Fläche liegt???

Vielleicht hilft Dir Abschnitt 2.03 der FAQ zu comp.graphics.algorithms weiter:

http://exaflop.org/docs/cgafaq/

Oder das hier:
http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

Go to the top of the page

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

6

Tuesday, February 25th 2003, 1:58pm

Danke für eure Antworten!!!

Ich werde noch eure Vorschläge mir angucken.
Ich habe aber mittlerweile eine andere Lösung gefunden.

Ich teile meine Fläche in solche Dreiecke, wie auf dem Bild gezeigt und betrachte nur (hier) dick gemalte Strecken. Dann muss für einen Punkt, der auf einer Strecke zwischen zwei Punkten liegt, gelten:

	Source code
1	y = ( x - x1) * ( (y2 - y1)/(x2 - x1) ) + y1 ***

Dabei P1 = (x1, y1), P2 = (x2, y2) und der "interessante" Punkt P0 = (x, y).
Dann kann man folgendes Sagen:
Ist y < ***, dann liegt der Punkt definitiv nicht in der Fläche.
sonst ja

Ich hoffe, das war so einigermaßen verständlich!
Falls dieser Ansatz falsch ist, dann bitte ich um Meldungen/Kommentare.
mfg
MAX

Go to the top of the page

MAX

Senior Schreiberling

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

7

Tuesday, February 25th 2003, 2:27pm

Hurra

Quoted

Vielleicht hilft Dir Abschnitt 2.03 der FAQ zu comp.graphics.algorithms weiter:

http://exaflop.org/docs/cgafaq/

Jipi!!!
Ich habe mir diesen Abschnitt angeguckt und habe festgestellt, dass ich es genauso gemacht habe, wie dort beschrieben ist!!! JIPI

Das freut mich sehr!!!
mfg
MAX

Go to the top of the page

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

8

Tuesday, February 25th 2003, 3:36pm

Der Ansatz ist falsch

...aber nur für nicht-konvexe Polygone. Für konvexe ist er ok, aber wenn Du Konkavitäten, Selbstüberschneidungen etc. hast, solltest Du definitiv in Betracht ziehen, Prof. Wolters Skript/Vorlesung zu betrachten, oder bei mir oder Martin Reuter in der Sprechstunde vorbeischauen.

Niklas Peinecke