Runde 3, Beispiel Konvneck

[Zatoichi]

Hallo! Ich habe Probleme bei einem Beispiel mit dem Titel Konvneck:

Aufgabenstellung:
Koordinatenpaare einlesen, die ein Vieleck bilden und herausfinden, ob das Vieleck konvex oder konkav ist oder ob sich Kanten des Vielecks schneiden.

Das mit dem Einlesen funktioniert, und die Konvex-/Konkavüberprüfung habe ich mit Hilfe des mitgebrachten Beispiels aus der ersten Runde auch schon hinbekommen(wenn alle Punkte "links" oder "rechts" von der Gerade liegen=> konvex, sonst konkav).

Bei der Schnittüberprüfung stehe ich aber an.
Ich hab mir schon Codes von anderen Leuten angesehen, die dieses Beispiel programmiert haben, aber irgendwie komme ich da nicht mit, hab grad erst mit Java angefangen.
Die meisten haben so Line2D Zeug verwendet, wie z.b. hier:
http://eprog.sourceforge.net/eprog/3154/0126697/Konvneck.java
Ich schaffs aber nicht, das in mein Programm umzumünzen, weil ich die Vorgänge nicht ganz verstehe.

Kann mir vielleicht jemand GENAU erklären, wie ich jede Linie in meinem Programm mit jeder anderen zu dieser "intersectLine" Überprüfung bringe?

Oder gibt es noch eine andere Möglichkeit zur Überprüfung ob sich Kanten schneiden?

Bin für jede Hilfe dankbar.

[Spike101]

Hallo,

Ich hatte das gleiche Bsp. in der 3. Runde. Ich habs folgendermaßen gelöst:
Du bekommst ja die "LINKS / RECHTS / DARAUF" Klasse mitgeliefert. Mit der kann man das recht einfach machen. Angenommen du willst zwei Linien auf Überschneidung prüfen:

Line1: a1-b1
Linie2: a2-b2

Jetzt überprüfst du mit der mitgelieferten Klasse, auf welcher Seite Punkt b1 gegenüber der Linie a1-a2 liegt, und auf welcher Seite Punkt b1 gegenüber der Linie a1-b2 liegt. Wenn der Punkt im ersten Fall links liegt, muss er im zweiten Fall rechts liegen, und umgekehrt.

Wenn das passt, überprüfst du noch die Position von a1 gegenüber a2-b2 und die Position von b1 gegenüber a2-b2. Die Punkte müssen wieder auf gegenüberliegenden Seiten liegen. Wenn das auch zutrifft schneiden sich die Linien.

Wenn das nicht zutrifft, oder ein Punkt AUF einer Linie liegt, schneiden sich die Linien nicht..

Mit dem Verfahren prüfst du jetzt einfach jede Linie mit jeder Linie. (Direkt benachbarte Linien brauchst du natürlich nicht prüfen weil sich die sowieso nicht überschneiden können)

[DePadA]

Morgen,

habe den gleichen Lösungsansatz für die Überschneidung von 2 Geraden verwendet.


Wenn das nicht zutrifft, oder ein Punkt AUF einer Linie liegt, schneiden sich die Linien nicht..

Mhh, ist glaube ich Ansichtssache ob ein Berührungspunkt (Punkt AUF einer Linie) die Gerade nun schneidet, sticht, kratzt usw. oder nicht, habe diesen Fall als Überschneidung angesehen und es gab keine Probleme. Eventuell werden solche dubiosen Eingabesätze bei der EProg Abgabe gar nicht verwendet und es passen beide Ansätze,...

[Zatoichi]

Okay, nachdem ich mir das mal aufgezeichnet habe, erscheint es mir richtig.
Aber wie seid ihr da eigentlich draufgekommen?

Noch eine Bitte: Könnte mir jemand einen einen Tipp geben, wie ich jede der Linien mit jeder außer der benachbarten schneide? (bzw. in welcher Form habt ihr die Koordinaten/Linien eigentlich abgespeichert?)

Vielleicht so in etwa mit einer Schleife in einer anderen, wobei die innere bei j-1,j,j+1 nicht ausgeführt wird???

[DePadA]

Draufgekommen, mhhh, analysiert und überlegt, manchmal kommt der Lösungsansatz schnell oder aber man rätselt ewig über Kleinigkeiten, vielleicht gibts ja ein Rezept...
Überleg dir das ganze mal mit einem konkreten Bsp. (aufzeichnen, Werte für Punkte angeben) und schau dir dann dein Problem mit den Linien an und versuche es zu verallgemeinern.
j-1,j,j+1 ist eine Möglichkeit

Grüße

[Zatoichi]

Habs jetzt einfach mit dem Geometriepackage gelöst...
Hat schließlich doch funktioniert...

Danke für die Denkanstöße.