# schneiden von Rechtecken



## tyr700 (25. Nov 2011)

Hallo !
Ich soll eine Methode schreiben, die konrolliert, ob sich zwei Rechtecke schneiden.
Zwei Rechtecke schneiden sich, wenn sie mind. einen Punkt gemeinsam haben. 
Dazu habe ich mir überlegt die 4 Eckpunkte der beiden Rechtecke zu kontrollieren ob sie im anderen Rechteck enthalten sind. (Vorher habe ich schon eine Methode geschrieben die genau das kontrolliert und wie folgt aussieht:


```
public boolean contains(Point p){
double a= p.getX()-bottomLeftCorner.getX();
double b = p.getY()-bottomLeftCorner.getY();
if (a>=0 && a<= width){
if (b>=0 && b <= height){
return true;
}
}
return false;
}
```

bottomLeftCorner, width und height sind oben in meiner Klasse deklariert.

nun könnte ich ja 8 if-Abfragen mit dieser Methode machen. Aber dann habe ich ja nicht alle Fälle untersucht. Es könnte ja auch sein das die beiden Rechtecke sich genau in der Mitte schneiden, ohne das ein Eckpunkt drin ist....

Der Kopf meiner Methode, zum testen ob sie sich schneiden, soll wie folgt lauten:

```
public boolean intersect(Rectangle r)
```

Ich komm einfach nicht weiter und die Sachen die ich hier gefunden habe, haben mir auch nicht geholfen :-(
Für Hilfe bin ich sehr dankbar!!


----------



## Andi_CH (25. Nov 2011)

tyr700 hat gesagt.:


> Zwei Rechtecke schneiden sich, wenn sie mind. einen Punkt gemeinsam haben.



Wer hat dir den Käse erzählt???:L

Zwei Rechtecke überschneiden sich, wenn mindestens einer der Eckpunkte des einen Rechteckes innerhalb des anderen Rechteckes  liegen.

Der Fall dass ein Rechteck komplett innerhalb des anderen liegt, kann nur so abgefangen werden, dass der oben erwähten Test gegenseitig ausgeführt wird.


----------



## SlaterB (25. Nov 2011)

wie tyr700 schreibt gibt es auch Fälle ohne die Eckpunkte,
dreist kopiert:

```
----
  |  |
--|  |--
| |  | |
--|  |--
  |  |
  ----
```

Schneiden zweier Rechtecke - Delphi-Forum.de

edit:
da steht auch was von Lösungen, wenn das nicht reicht:
dann sollte für diese Fälle reichen zu prüfen ob sich je eine beliebige Diagonale pro Rechteck mit der anderen schneidet, 
dieser Schnittpunkt innerhalb beider Rechtecke liegt,

Schnittpunkt von Geraden ist auch ein Standard-Theme in Mathematik, 
wieder mit Sonderfällen wie waagerecht/ senkrecht


----------



## tyr700 (25. Nov 2011)

das steht als hinweis auf dem aufgabenblatt...


----------



## Andi_CH (25. Nov 2011)

hm - ok SlaterB das stimmt natürlich, nur ist das mit dem gemeinsamen Punkt immer noch nicht richtig, ausser ich hätte einen Fehlschluss gezogen - unter "Punkt" hab ich die Eckpunkte verstanden.

Ich kann übrigens auch Fälle konstruieren in denen sich die Diagonalen nicht schneiden.
Da würde ich eher darauf setzen, dass sich die Diagonalen des einen mit einer beliebigen Seitenlinie das anderen schneiden.

Oder/und dass sich Seitenlinien schneiden

Da gibt es aber wieder den Fall das ganz kleinen innerhalb des Grossen ...

Es ist auf jeden Fall komplexer als mein Kleinhirn signalisierte ;-) - vor allem wenn die Rechtecke in beliebigen Winkeln liegen dürfen

EDIT: War der Hinweis so zu verstehen, dass es einen beliebigen Punkt gibt, der in beiden Rechtecken drin liegt? Das stimmt natürlich, nur ist der nicht so einfach zu finden.


----------



## SlaterB (25. Nov 2011)

> Ich kann übrigens auch Fälle konstruieren in denen sich die Diagonalen nicht schneiden.
stimmt, dann sind wohl wirklich viele Schnitte aller Seiten angesagt bzw. der je 2 Diagonalen untereinander?

oder die genannte einfache Lösung im anderen Forum


> ```
> Result:=((B.P1.X<A.P2.X) and(A.P1.X<B.P2.X)) //Überschneidung im X-Segment
> and ((B.P1.Y<A.P2.Y) and(A.P1.Y<B.P2.Y));//Überschneidung im Y-Segment
> ```


aber da bin ich noch skeptisch, na kann man ja genau testen/ prüfen
(edit: bestimmt nicht für schräge Rechtecke gedacht, sonst reichen zwei Punkte auch kaum zur vollständigen Beschreibung aus)

man sollte meinen dass es im Internet exaktere Definitionsseiten als solche Foren-Threads gibt..


----------



## tyr700 (25. Nov 2011)

danke schonmal für den hinweis!

so wie ich das jetzt verstanden habe , kann cih das so überprüfen:

```
public boolean intersect(Rectangle r){
double a= r.bottomLeftCorner.getX()+this.bottomLeftCorner.getX();
double b= r.bottomLeftCorner.getY()+this.bottomLeftCorner.getY();
if(a<= r.width+this.width && b<= r.height+this.heigth){
return true;
}
return false;
}
```


----------



## SlaterB (25. Nov 2011)

wo kommt dieser Vorschlag her? scheint mir nicht sinnvoll, die Koordinaten könnten doch im Bereich von Millionen liegen,
was nützt es wenn du 1 Mio. + 1 Mio. addierst und das mit Breiten 20 + 20 vergleichst?
Differenzen, also - statt + vielleicht..


----------



## tyr700 (25. Nov 2011)

Ich dachte, dass wäre so zu verstehen auf dem Delphi-Forum...
Aber mit der Differenz ist es schon sinnvoller!Aber damit komme ich auch nicht zum gewünschten Ergebnis....
ich verstehs irgendwie nicht...
ich habe ja nur den linken unteren punkt, die höhe und die breite...
könnte ich vielleicht sagen, dass die x-koordinate von einem rechteck innerhalb x-koordinate und x-koordinat + die breite liegen muss. und das gleiche dann auch für den y-wert. 
aber dann schau ich mir ja auch wieder nur einen punkt an...


----------



## SlaterB (25. Nov 2011)

wenn du die Breite hinzunimmst ist quasi auch der zweite Punkt eingebunden, also in etwa das was ich um 13:44 zitiert habe,
das mag schon funktionieren, wie gesagt vermutlich ohne schräge Rechtecke, einfach für verschiede Beispiele ausprobieren,
gerne wie immer zunächst auf Papier


----------



## tyr700 (25. Nov 2011)

Ich habe jetzt 2 Blätter voller Zeichnungen aber jetzt hab ichs gecheckt.
Danke für die Geduld!


----------

