Ich versuche, ein C ++ - Programm zu schreiben, das die folgenden Eingaben vom Benutzer verwendet, um Rechtecke (zwischen 2 und 5) zu erstellen: Höhe, Breite, x-pos, y-pos. Alle diese Rechtecke existieren parallel zur x- und zur y-Achse, dh alle ihre Kanten haben Steigungen von 0 oder unendlich.
Ich habe versucht, das umzusetzen, was in dieser Frage erwähnt wird, aber ich habe nicht viel Glück.
Meine aktuelle Implementierung führt Folgendes aus:
// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2
// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];
int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;
Ich bin mir jedoch nicht ganz sicher, ob (a) ich den Algorithmus, mit dem ich verknüpft habe, korrekt implementiert habe oder ob ich genau weiß, wie ich das interpretieren soll?
Irgendwelche Vorschläge?
Antworten:
oder unter Verwendung kartesischer Koordinaten
(Wenn X1 die linke Koordinate ist, X2 die rechte Koordinate ist und von links nach rechts zunimmt und Y1 die obere Koordinate ist und Y2 die untere Koordinate ist , die von unten nach oben zunimmt - wenn dies nicht Ihr Koordinatensystem ist [z. B. haben die meisten Computer das Y-Richtung umgekehrt], tauschen Sie die Vergleiche unten aus ) ...
Angenommen, Sie haben Rect A und Rect B. Der Beweis ist ein Widerspruch. Eine der vier Bedingungen garantiert, dass keine Überlappung bestehen kann :
Bedingung für Nichtüberlappung ist also
Daher ist eine ausreichende Bedingung für Überlappung das Gegenteil.
De Morgans Gesetz besagt, dass
Not (A or B or C or D)
es dasselbe ist, wieNot A And Not B And Not C And Not D
wir es mit De Morgan getan haben
Dies entspricht:
RectA.Left < RectB.Right
] undRectA.Right > RectB.Left
] undRectA.Top > RectB.Bottom
] undRectA.Bottom < RectB.Top
]Anmerkung 1 : Es ist ziemlich offensichtlich, dass dasselbe Prinzip auf eine beliebige Anzahl von Dimensionen erweitert werden kann.
Anmerkung 2 : Es sollte auch ziemlich offensichtlich sein, Überlappungen von nur einem Pixel zu zählen
<
und das und / oder das>
an dieser Grenze in a<=
oder a zu ändern>=
.Anmerkung 3 : Diese Antwort basiert bei Verwendung kartesischer Koordinaten (X, Y) auf algebraischen kartesischen Standardkoordinaten (x erhöht sich von links nach rechts und Y erhöht sich von unten nach oben). Wenn ein Computersystem die Bildschirmkoordinaten möglicherweise anders mechanisiert (z. B. Y von oben nach unten oder X von rechts nach links erhöhen), muss die Syntax natürlich entsprechend angepasst werden.
quelle
quelle
B.height
sollte seinA.height
#undef min
und#undef max
oder verschiedene Parameternamen verwenden.#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
xOverlap
eindimensional.rectOverlap
ist zweidimensional. Sie kann mit einer Schleife auf N Dimensionen erweitert werden.quelle
Es ist einfacher zu überprüfen, ob sich ein Rechteck vollständig außerhalb des anderen befindet
links...
oder rechts ...
oder oben ...
oder unten ...
des zweiten Rechtecks kann es unmöglich damit kollidieren. Um eine Funktion zu haben, die ein boolesches Sprichwort zurückgibt, wenn die Rechtecke kollidieren, kombinieren wir die Bedingungen einfach durch logische ODERs und negieren das Ergebnis:
Um bereits beim Berühren ein positives Ergebnis zu erhalten, können wir "<" und ">" durch "<=" und "> =" ändern.
quelle
Stellen Sie sich die entgegengesetzte Frage: Wie kann ich feststellen, ob sich zwei Rechtecke überhaupt nicht schneiden? Offensichtlich schneidet sich ein Rechteck A vollständig links von Rechteck B nicht. Auch wenn A ganz rechts ist. Und ähnlich, wenn A vollständig über B oder vollständig unter B liegt. In jedem anderen Fall schneiden sich A und B.
Was folgt, kann Fehler haben, aber ich bin ziemlich sicher über den Algorithmus:
quelle
Angenommen, Sie haben die Positionen und Größen der Rechtecke wie folgt definiert:
Meine C ++ - Implementierung sieht folgendermaßen aus:
Ein Beispiel für einen Funktionsaufruf gemäß der obigen Abbildung:
Die Vergleiche innerhalb des
if
Blocks sehen wie folgt aus:quelle
So geht's in der Java-API:
quelle
In der Frage verknüpfen Sie die Mathematik, wenn sich Rechtecke in beliebigen Drehwinkeln befinden. Wenn ich jedoch das Bit über Winkel in der Frage verstehe, interpretiere ich, dass alle Rechtecke senkrecht zueinander stehen.
Ein allgemeines Wissen über den Bereich der Überlappungsformel lautet:
Am Beispiel:
1) Sammeln Sie alle x-Koordinaten (links und rechts) in einer Liste, sortieren Sie sie und entfernen Sie Duplikate
2) Sammeln Sie alle y-Koordinaten (oben und unten) in einer Liste, sortieren Sie sie und entfernen Sie Duplikate
3) Erstellen Sie ein 2D-Array nach Anzahl der Lücken zwischen den eindeutigen x-Koordinaten * Anzahl der Lücken zwischen den eindeutigen y-Koordinaten.
4) Malen Sie alle Rechtecke in dieses Raster und erhöhen Sie die Anzahl der Zellen, über die es auftritt:
5) Wenn Sie die Rechtecke malen, können Sie die Überlappungen leicht abfangen.
quelle
quelle
Stellen Sie sich Koordinaten nicht als Hinweis darauf vor, wo sich Pixel befinden. Stellen Sie sich diese zwischen den Pixeln vor. Auf diese Weise sollte die Fläche eines 2x2-Rechtecks 4 und nicht 9 sein.
quelle
Der einfachste Weg ist
Denken Sie zunächst daran, dass das Koordinatensystem in Computern auf dem Kopf steht. Die x-Achse ist dieselbe wie in der Mathematik, aber die y-Achse nimmt nach unten zu und ab, wenn sie nach oben geht. Wenn Rechtecke von der Mitte gezeichnet werden. Wenn x1-Koordinaten größer als x2 plus die Hälfte der Breite sind. dann bedeutet es, dass sie sich zur Hälfte berühren. und auf die gleiche Weise nach unten + die Hälfte seiner Höhe. es wird kollidieren ..
quelle
Nehmen wir an, die beiden Rechtecke sind Rechteck A und Rechteck B. Ihre Zentren seien A1 und B1 (die Koordinaten von A1 und B1 können leicht ermittelt werden), die Höhen seien Ha und Hb, die Breite sei Wa und Wb, sei dx die Breite (x) Abstand zwischen A1 und B1 und dy ist der Abstand Höhe (y) zwischen A1 und B1.
Jetzt können wir sagen, wir können sagen, A und B überlappen sich: wann
quelle
Ich habe eine C # -Version implementiert, die leicht in C ++ konvertiert werden kann.
quelle
Ich habe eine sehr einfache Lösung
x1, y1 x2, y2, l1, b1, l2 seien Koordinaten und Längen bzw. Breiten von ihnen
Betrachten Sie die Bedingung ((x2
Jetzt überlappen sich diese Rechtecke nur noch, wenn die Punktdiagonale zu x1, y1 innerhalb des anderen Rechtecks oder ähnlich die Punktdiagonale zu x2, y2 innerhalb des anderen Rechtecks liegt. was genau die obige Bedingung impliziert.
quelle
A und B sind zwei Rechtecke. C ist ihr Deckrechteck.
Es kümmert sich um alle möglichen Fälle.
quelle
Dies stammt aus Übung 3.28 aus dem Buch Einführung in die Java-Programmierung - Umfassende Ausgabe. Der Code prüft, ob die beiden Rechtecke ein Einzug sind, ob sich eines innerhalb des anderen befindet und ob sich eines außerhalb des anderen befindet. Wenn keine dieser Bedingungen erfüllt ist, überlappen sich die beiden.
** 3.28 (Geometrie: zwei Rechtecke) Schreiben Sie ein Programm, das den Benutzer auffordert, die mittleren x-, y-Koordinaten, die Breite und die Höhe von zwei Rechtecken einzugeben, und bestimmt, ob sich das zweite Rechteck innerhalb des ersten befindet oder sich mit dem ersten überlappt. wie in Abbildung 3.9 gezeigt. Testen Sie Ihr Programm, um alle Fälle abzudecken. Hier sind die Probeläufe:
Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r1 ein: 2,5 4 2,5 43 Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r2 ein: 1,5 5 0,5 3 r2 befindet sich innerhalb von r1
Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r1 ein: 1 2 3 5.5 Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r2 ein: 3 4 4.5 5 r2 überlappt r1
Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r1 ein: 1 2 3 3 Geben Sie die x-, y-Koordinaten, die Breite und die Höhe von r2 ein: 40 45 3 2 r2 überlappt r1 nicht
quelle
quelle
Für diejenigen unter Ihnen, die Mittelpunkte und halbe Größen für ihre Rechteckdaten anstelle der typischen x, y, w, h oder x0, y0, x1, x1 verwenden, gehen Sie wie folgt vor:
quelle
quelle
Wenn sich die Rechtecke überlappen, ist der Überlappungsbereich größer als Null. Lassen Sie uns nun den Überlappungsbereich finden:
Wenn sie sich überlappen, ist die linke Kante von Overlap-Rect die
max(r1.x1, r2.x1)
rechte Kante und die rechte Kantemin(r1.x2, r2.x2)
. Die Länge der Überlappung wird also seinmin(r1.x2, r2.x2) - max(r1.x1, r2.x1)
Das Gebiet wird also sein:
Wenn
area = 0
dann, überlappen sie sich nicht.Einfach, nicht wahr?
quelle
"Wenn Sie x- oder y-Koordinaten subtrahieren, die den Eckpunkten der beiden Rechtecke entsprechen, überlappen sich die beiden Rechtecke nicht, wenn die Ergebnisse das gleiche Vorzeichen haben." (Es tut mir leid, ich bin nicht sicher, ob meine Übersetzung korrekt ist )
Quelle: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
quelle
Java-Code, um herauszufinden, ob sich Rechtecke berühren oder überlappen
...
...
quelle