überprüfen ob eine schnittmenge vorhanden ist

[napstar]

hallo ich studiere informatik im 1. semester..
wir haben eine aufgabe bekommen die ich bis heute abend fertig haben mus :(

leider komme ich nicht mehr weiter.. ich muss das ganze zwar in java realisieren.. aber mir geht es nicht um den code.. sondern eher wie ich es realisieren soll..

also ich habe eine klasse point und eine klasse rectange
nun muss ich ne methode schreiben die true zurückliefert, wenn 2 rechtecke eine schnittmenge haben..

kann mir jemand einen ansatz verraten?..

danke schonmal im vorraus..

[Der schöne Günther]

Das ist doch nicht kompliziert: :-)

Wäre ich faul, würde ich einfach

Delphi-Quellcode:

java.awt.geom.*

einbinden und die Klassen

Delphi-Quellcode:

Point2D

und

Delphi-Quellcode:

Rectangle2D = class(Arc2D)

verwenden ;-)

Aber wenn man selbst nachdenken soll: Wenn du die Schnittmenge nicht einmal bestimmen sollst, sondern nur feststellen, ob überhaupt eine vorhanden ist:

Ich hätte spontan einfach nur geschaut, ob auf der X-Achse die Punkte B1 oder B4 oder beide zwischen A1 und A4 liegen. Wenn ja, das gleiche nochmal für die Y-Achse.

[Sir Rufo]

Code:

P1 = Max( A.TopLeft, B.TopLeft )
P2 = Min( A.BottomRight, B.BottomRight )

dabei ist

Code:

Max( P1, P2 ) : Point
R.x = Max( P1.x, P2.x )
R.y = Max( P1.y, P2.y )

Das Minimum analog dazu

Jetzt muss nur noch die Bedingung erfüllt sein, dass

Code:

P1.x <= P2.x und P1.y <= P2.y

Eine Sonderbedingung ist, wenn P1=P2, dann ist die Schnittmenge ein Punkt

PS

Wichtig ist noch, die Bereiche vor der Analyse zu normalisieren (d.h. TopLeft liegt wirklich auch oben links) ;)

[Aphton]

Eine andere, einfachere Variante ist dieser hier:

EsGibtKeineSchnittmenge = NOT(EsGibtEineSchnittmenge)

Für EsGibtKeineSchnittmenge gibt es genau 4 Fälle:
(Beziehe mich auf die Graphik bei der Antwort #2)
A1.X > B4.X OR
A4.X < B1.X OR
A1.Y > B2.Y OR
A2.Y < B1.Y

Da du die Schnittmenge (Ein Rechteck) an sich nicht berechnen musst, reichen diese 4 Bedingungen!

[Der schöne Günther]

Das ist alles viel zu eindeutig, wir brauchen polarisierende Glaubensfragen.

Wäre die Software nicht gleich viel besser wartbar, wenn wir stattdessen eine Methode zur Bestimmung der Schnittmenge mit einem anderen Rechteck implementieren? Wenn es keine Schnittmenge in der Ebene gibt, wird eben

Delphi-Quellcode:

nil

oder ein spezielle Null-Instanz zurückgegeben. Klar verbraten wir unnütz Leistung wenn wir in 95% der Fälle wirklich nur wissen wollen, ob es überhaupt eine gibt. Aber ich meine ja nur :twisted:

[Aphton]

Ja klar; gilt aber nur für ordentliche Software.

Nicht für elementare Probleme, mit denen sich Studenten beschäftigen sollen, damit sie zuerst einmal ihre analytischen Skills verbessern. Klar könnte man das so machen, ist aber ned zwingendermaßen Ziel der Übung!

Designtechnische Sachen kommen später im Studium!

Meine Meinung :P