تحديد ما إذا كان اثنين من المستطيلات تتداخل مع بعضها البعض ؟
https://stackoverflow.com/questions/306316
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أحاول كتابة C++ برنامج يأخذ التالية مدخلات من المستخدم إلى بناء مستطيلات (بين 2 و 5):الطول, العرض, x-نقاط البيع, y-نقاط البيع.كل هذه المستطيلات موجودة بالتوازي مع x و y محاور ، وهذا هو كل حوافها سوف يكون المنحدرات من 0 أو اللانهاية.
لقد حاولت تنفيذ ما ورد في هذا هذا السؤال ولكن أنا ليس لدي الكثير جدا من الحظ.
بلدي الحالي تنفيذ ما يلي:
// 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;
ومع ذلك أنا لست متأكدا تماما إذا كان (أ) لقد تنفيذ الخوارزمية أنا مرتبط بشكل صحيح ، أو إذا فعلت بالضبط كيفية تفسير هذا ؟
أي اقتراحات ؟
المحلول
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
أو باستخدام الإحداثيات الديكارتية
(مع X1 ترك coord, X2 يجري الحق coord ، مما يزيد من اليسار إلى اليمين و Y1 كونها أعلى coord و Y2 يجري أسفل coord ، مما يزيد من أسفل إلى أعلى) ...
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
ملاحظة:إلى كافة بحيث يمكن للمستخدمين مع تحرير السلطة.يرجى التوقف عن العبث مع هذا.
نقول لديك المستطيل ، Rect B.والدليل هو تناقض.أي واحد من أربعة شروط الضمانات التي أي تداخل يمكن أن توجد:
- Cond1.إذا ترك حافة هو حق ب صحيح الحافة ، - ثم هو تماما على حق ب
- Cond2.إذا الحافة اليمنى إلى اليسار من اليسار الحافة ، - ثم هو تماما إلى اليسار من ب
- Cond3.إذا كان أعلى حافة أقل ب أسفل الحافة ، - ثم هو تماما أدناه ب
- Cond4.إذا كان أسفل الحافة فوق ب أعلى الحافة ، - ثم هو تماما فوق ب
لذلك شرط عدم التداخل
Cond1 Or Cond2 Or Cond3 Or Cond4
ولذلك شرطا كافيا التداخل هو عكس ذلك.
Not (Cond1 Or Cond2 Or Cond3 Or Cond4)
دي مورغان القانون يقول
Not (A or B or C or D) هو نفس Not A And Not B And Not C And Not D
وذلك باستخدام مورغان دي علينا
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
هذا هو ما يعادل:
- أ الحافة اليسرى إلى اليسار من ب صحيح الحافة ، [
RectA.Left < RectB.Right] ، - على الحافة اليمنى إلى اليمين من ب الحافة اليسرى, [
RectA.Right > RectB.Left] ، - وهو أعلى فوق ب السفلي ، [
RectA.Top > RectB.Bottom] ، - أ أسفل أدناه ب أعلى [
RectA.Bottom < RectB.Top]
ملاحظة 1:فمن الواضح تماما هذا المبدأ نفسه يمكن أن تمتد إلى أي عدد من الأبعاد.
ملاحظة 2:وينبغي أيضا أن يكون واضحا إلى حد ما الاعتماد التداخل واحد فقط بكسل, تغيير < و/أو > على أن الحدود إلى <= أو >=.
ملاحظة 3:هذا الجواب ، عند استخدام الإحداثيات الديكارتية (X, Y) على أساس معيار جبري الإحداثيات الديكارتية (x يزيد من اليسار إلى اليمين ، و ذ يزيد من أسفل إلى أعلى).ومن الواضح حيث نظام الكمبيوتر قد مكننة إحداثيات الشاشة بشكل مختلف (على سبيل المثال ، زيادة Y من أعلى إلى أسفل ، أو س من اليمين إلى اليسار) ، جملة سوف تحتاج إلى تعديل وفقا لذلك/
نصائح أخرى
struct rect
{
int x;
int y;
int width;
int height;
};
bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }
bool rectOverlap(rect A, rect B)
{
bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width);
bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + A.height);
return xOverlap && yOverlap;
}struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
bool
overlap(const Rect &r1, const Rect &r2)
{
// The rectangles don't overlap if
// one rectangle's minimum in some dimension
// is greater than the other's maximum in
// that dimension.
bool noOverlap = r1.x1 > r2.x2 ||
r2.x1 > r1.x2 ||
r1.y1 > r2.y2 ||
r2.y1 > r1.y2;
return !noOverlap;
}
وانه من الاسهل لمعرفة ما إذا كان المستطيل كلي خارج الآخر، حتى إذا هو إما
وعلى اليسار ...
(r1.x + r1.width < r2.x)
وأو على حق ...
(r1.x > r2.x + r2.width)
وأو على أعلى ...
(r1.y + r1.height < r2.y)
وأو على الجزء السفلي ...
(r1.y > r2.y + r2.height)
والمستطيل الثاني، فإنه لا يمكن أن تصطدم معها. حتى أن يكون لها وظيفة وترجع قائلا الطقس منطقية المستطيلات تصطدم، ونحن ببساطة الجمع بين الشروط التي نسب الأرجحية منطقية وينفي النتيجة:
function checkOverlap(r1, r2) : Boolean
{
return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}
لتلقي بالفعل نتيجة إيجابية عندما لمس فقط، يمكننا تغيير "<" و ">" ب "<=" و "> =".
واسأل نفسك هذا السؤال المعاكس: كيف يمكنني تحديد ما إذا كان اثنين من المستطيلات لا تتقاطع في كل شيء؟ من الواضح، مستطيل A تماما على يسار المستطيل B لا تتقاطع. أيضا إذا كان (أ) هو تماما إلى اليمين. وبالمثل إذا A هو تماما فوق B أو كليا دون B. في أي حالة أخرى A و B تتقاطع.
وفيما يلي قد يكون الخلل، ولكن أنا واثق جدا حول الخوارزمية:
struct Rectangle { int x; int y; int width; int height; };
bool is_left_of(Rectangle const & a, Rectangle const & b) {
if (a.x + a.width <= b.x) return true;
return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
return is_left_of(b, a);
}
bool not_intersect( Rectangle const & a, Rectangle const & b) {
if (is_left_of(a, b)) return true;
if (is_right_of(a, b)) return true;
// Do the same for top/bottom...
}
bool intersect(Rectangle const & a, Rectangle const & b) {
return !not_intersect(a, b);
}
لنفترض أن قمت بتعريف مواقع وأحجام مختلفة من المستطيلات مثل هذا:
وبلدي تنفيذ C ++ مثل هذا:
class Vector2D
{
public:
Vector2D(int x, int y) : x(x), y(y) {}
~Vector2D(){}
int x, y;
};
bool DoRectanglesOverlap( const Vector2D & Pos1,
const Vector2D & Size1,
const Vector2D & Pos2,
const Vector2D & Size2)
{
if ((Pos1.x < Pos2.x + Size2.x) &&
(Pos1.y < Pos2.y + Size2.y) &&
(Pos2.x < Pos1.x + Size1.x) &&
(Pos2.y < Pos1.y + Size1.y))
{
return true;
}
return false;
}
ومكالمة سبيل المثال وظيفة وفقا لهذا الرقم المذكور أعلاه:
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
وسوف المقارنات داخل كتلة if تبدو مثل أدناه:
if ((Pos1.x < Pos2.x + Size2.x) &&
(Pos1.y < Pos2.y + Size2.y) &&
(Pos2.x < Pos1.x + Size1.x) &&
(Pos2.y < Pos1.y + Size1.y))
↓
if (( 3 < 6 + 9 ) &&
( 7 < 4 + 4 ) &&
( 6 < 3 + 8 ) &&
( 4 < 7 + 5 ))
إليك كيف يتم ذلك في API جافا:
public boolean intersects(Rectangle r) {
int tw = this.width;
int th = this.height;
int rw = r.width;
int rh = r.height;
if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
return false;
}
int tx = this.x;
int ty = this.y;
int rx = r.x;
int ry = r.y;
rw += rx;
rh += ry;
tw += tx;
th += ty;
// overflow || intersect
return ((rw < rx || rw > tx) &&
(rh < ry || rh > ty) &&
(tw < tx || tw > rx) &&
(th < ty || th > ry));
}
في هذه المسألة، التي تصل إلى الرياضيات لحين المستطيلات هي في زوايا التعسفي الدوران. إذا أنا أفهم قليلا عن الزوايا في السؤال إلا أنني تفسير أن جميع المستطيلات هي متعامدة مع بعضها البعض.
وA العامة معرفة مجال صيغة التداخل هي:
وباستخدام المثال:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) جمع كل إحداثيات س (كل من اليسار واليمين) في القائمة، ثم ترتيب هذا الأمر وإزالة التكرارات
1 3 4 5 6
2) جمع كل الإحداثيات ص (سواء أعلى وأسفل) في القائمة، ثم ترتيب هذا الأمر وإزالة التكرارات
1 2 3 4 6
و3) إنشاء مجموعة 2D من قبل عدد من الفجوات بين العاشر فريد إحداثيات * عدد من الفجوات بين إحداثيات ص فريدة من نوعها.
4 * 4
و4) طلاء جميع المستطيلات في هذه الشبكة، تزايد عدد كل خلية حدوثه على:
1 3 4 5 6
1 +---+
| 1 | 0 0 0
2 +---+---+---+
| 1 | 1 | 1 | 0
3 +---+---+---+---+
| 1 | 1 | 2 | 1 |
4 +---+---+---+---+
0 0 | 1 | 1 |
6 +---+---+
و5) كما يمكنك رسم المستطيلات، من السهل لاعتراض التداخل.
struct Rect
{
Rect(int x1, int x2, int y1, int y2)
: x1(x1), x2(x2), y1(y1), y2(y2)
{
assert(x1 < x2);
assert(y1 < y2);
}
int x1, x2, y1, y2;
};
//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
r1.y1 < r2.y2 && r2.x1 < r1.y2;
}
//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}
لا أعتقد الإحداثيات كما يشير إلى حيث هي وحدات بكسل. اعتقد منهم بأنها بين بكسل. وبهذه الطريقة، يجب أن تكون مساحة مستطيل 2X2 4، وليس 9.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
وأسهل طريقة هي
/**
* Check if two rectangles collide
* x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
* x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
*/
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}
وقبل كل شيء وضع في لعقلك أن في أجهزة الكمبيوتر نظام الإحداثيات رأسا على عقب. محور س هو نفسه كما في الرياضيات ولكن الزيادات محور y أسفل وانخفاض على الذهاب إلى أعلى .. إذا المستطيل يتم رسمها من المركز. إذا ينسق X1 أكبر من X2 بالإضافة إلى نصفه لها من widht. بعد ذلك يعني الذهاب نصف فإنها تلامس بعضها البعض. وبنفس الطريقة تسير نحو الانخفاض + نصف ذروته. سوف تصطدم ..
يتيح القول اثنين من المستطيلات هي المستطيل المستطيل B.دعونا هناك مراكز A1 و B1 (إحداثيات A1 و B1 يمكن العثور بسهولة) ، والسماح مرتفعات يكون هكتار Hb, العرض يكون وا و البنك الدولي ، والسماح dx يكون عرض(x) المسافة بين A1 و B1 و دى يكون ارتفاع(y) المسافة بين A1 و B1.
الآن نستطيع أن نقول أننا يمكن أن نقول أ و ب التداخل:عندما
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
ولقد نفذت C # نسخة، يتم تحويلها بسهولة إلى C ++.
public bool Intersects ( Rectangle rect )
{
float ulx = Math.Max ( x, rect.x );
float uly = Math.Max ( y, rect.y );
float lrx = Math.Min ( x + width, rect.x + rect.width );
float lry = Math.Min ( y + height, rect.y + rect.height );
return ulx <= lrx && uly <= lry;
}
ولدي حل سهل جدا
والسماح X1، X2 Y1، Y2، L1، B1، L2، يكون cordinates وأطوال وbreadths منهم على التوالي
والنظر في حالة ((X2
والآن الطريقة الوحيدة وهذه المستطيل تتداخل هو إذا كانت نقطة قطري لX1، Y1 سوف تكمن داخل المستطيل آخر أو على نحو مماثل نقطة قطري لX2، Y2 سوف تكمن داخل المستطيل الآخر. وهو بالضبط الشرط أعلاه تعني.
وألف وباء ان اثنين من المستطيل. C يكون المستطيل تغطي بهم.
four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom)
four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom)
A.width = abs(xAleft-xAright);
A.height = abs(yAleft-yAright);
B.width = abs(xBleft-xBright);
B.height = abs(yBleft-yBright);
C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright);
C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom);
A and B does not overlap if
(C.width >= A.width + B.width )
OR
(C.height >= A.height + B.height)
ويستغرق رعاية جميع الحالات الممكنة.
وهذا من ممارسة 3.28 من كتاب مقدمة جافا Programming- الشامل الطبعة. الاختبارات متاحة سواء المستطيلات هما indenticle، سواء كان المرء داخل الآخر، وسواء كان المرء خارج الآخر. إذا تم استيفاء أيا من هذه الحالة ثم تداخل بين الأمرين.
و** 3.28 (الهندسة: اثنان مستطيلات) كتابة البرنامج الذي يطالب المستخدم بإدخال X- المركز، الإحداثيات ذ، العرض، والارتفاع اثنين من المستطيلات ويحدد إذا كان المستطيل الثاني هو داخل لأول مرة أو تتداخل مع الأولى، كما هو مبين في الشكل 3.9. اختبار البرنامج لتغطية جميع الحالات. هنا الشوط عينة:
وأدخل X- مركز R1، على بعد إحداثيات ص، العرض، والارتفاع: 2.5 4 2.5 43 أدخل X- مركز R2، على بعد إحداثيات ص، العرض، والارتفاع: 1.5 5 0.5 3 R2 هو داخل R1
وأدخل X- مركز R1، على بعد إحداثيات ص، العرض، والارتفاع: 1 2 3 5.5 أدخل X- مركز R2، على بعد إحداثيات ص، العرض، والارتفاع: 3 4 4.5 5 R2 R1 تتداخل
وأدخل X- مركز R1، على بعد إحداثيات ص، العرض، والارتفاع: 1 2 3 3 أدخل X- مركز R2، على بعد إحداثيات ص، العرض، والارتفاع: 40 45 3 2 R2 لا تتداخل R1
import java.util.Scanner;
public class ProgrammingEx3_28 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out
.print("Enter r1's center x-, y-coordinates, width, and height:");
double x1 = input.nextDouble();
double y1 = input.nextDouble();
double w1 = input.nextDouble();
double h1 = input.nextDouble();
w1 = w1 / 2;
h1 = h1 / 2;
System.out
.print("Enter r2's center x-, y-coordinates, width, and height:");
double x2 = input.nextDouble();
double y2 = input.nextDouble();
double w2 = input.nextDouble();
double h2 = input.nextDouble();
w2 = w2 / 2;
h2 = h2 / 2;
// Calculating range of r1 and r2
double x1max = x1 + w1;
double y1max = y1 + h1;
double x1min = x1 - w1;
double y1min = y1 - h1;
double x2max = x2 + w2;
double y2max = y2 + h2;
double x2min = x2 - w2;
double y2min = y2 - h2;
if (x1max == x2max && x1min == x2min && y1max == y2max
&& y1min == y2min) {
// Check if the two are identicle
System.out.print("r1 and r2 are indentical");
} else if (x1max <= x2max && x1min >= x2min && y1max <= y2max
&& y1min >= y2min) {
// Check if r1 is in r2
System.out.print("r1 is inside r2");
} else if (x2max <= x1max && x2min >= x1min && y2max <= y1max
&& y2min >= y1min) {
// Check if r2 is in r1
System.out.print("r2 is inside r1");
} else if (x1max < x2min || x1min > x2max || y1max < y2min
|| y2min > y1max) {
// Check if the two overlap
System.out.print("r2 does not overlaps r1");
} else {
System.out.print("r2 overlaps r1");
}
}
}
bool Square::IsOverlappig(Square &other)
{
bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
return result1 | result2 | result3 | result4;
}
لأولئك منكم الذين يستخدمون نقاط المركز وأحجام نصف للبيانات المستطيل، بدلا من س نموذجية، ذ، ث، ح، أو X0، Y0، X1، X1، وهنا كيف يمكنك أن تفعل ذلك:
#include <cmath> // for fabsf(float)
struct Rectangle
{
float centerX, centerY, halfWidth, halfHeight;
};
bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b)
{
return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) &&
(fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight));
}
وينبغي أن يكون هذا الجواب أعلى الجواب:
إذا المستطيلات تتداخل ثم منطقة تداخل ستكون أكبر من الصفر. الآن دعونا العثور على منطقة التداخل:
إذا تداخلها ثم الحافة اليسرى من التداخل-المستطيل سيكون max(r1.x1, r2.x1) والحافة اليمنى سيتم min(r1.x2, r2.x2). لذلك سيتم min(r1.x2, r2.x2) - max(r1.x1, r2.x1) طول تداخل
وهكذا المنطقة سيكون:
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
إذا area = 0 ثم أنها لا تتداخل.
وبسيط أليس كذلك؟
نظرة على الموضوع من موقع مختلف.
حالة تبين أن تكون بسيطة جدا إذا نظرنا إلى المشكلة (الخوارزمية) من الجانب الآخر.
هذا يعني أنه بدلا من الإجابة على السؤال:"هي مستطيلات التداخل؟", ونحن سوف يجيب على السؤال:"هي مستطيلات لا لا هذا التداخل؟".
في النهاية كل الأسئلة حل نفس المشكلة ولكن الجواب على السؤال الثاني هو أبسط لتنفيذ لأن المستطيلات لا تتداخل إلا عند واحدة تحت الأخرى أو عندما يكون أحد أكثر إلى اليسار الأخرى (وهو ما يكفي للحصول على واحدة من هذه الحالات ، ولكن بالطبع قد يحدث أن كلا سوف يحدث في وقت واحد - هنا فهم جيد من المنطقي الشرط "أو" مهم).وهذا يقلل من العديد من الحالات التي تحتاج إلى النظر فيها على السؤال الأول.
المسألة برمتها هي أيضا تبسيط استخدام المتغير المناسب الأسماء:
#include<bits/stdc++.h>
struct Rectangle
{
// Coordinates of the top left corner of the rectangle and width and height
float x, y, width, height;
};
bool areRectanglesOverlap(Rectangle rect1, Rectangle rect2)
{
// Declaration and initialization of local variables
// if x and y are the top left corner of the rectangle
float left1, top1, right1, bottom1, left2, top2, right2, bottom2;
left1 = rect1.x;
top1 = rect1.y;
right1 = rect1.x + rect1.width;
bottom1 = rect1.y - rect1.height;
left2 = rect2.x;
top2 = rect2.y;
right2 = rect2.x + rect2.width;
bottom2 = rect2.y - rect2.height;
// The main part of the algorithm
// The first rectangle is under the second or vice versa
if (top1 < bottom2 || top2 < bottom1)
{
return false;
}
// The first rectangle is to the left of the second or vice versa
if (right1 < left2 || right2 < left1)
{
return false;
}
// Rectangles overlap
return true;
}
حتى إذا كان لدينا تمثيل مختلف من مستطيل ، فمن السهل على التكيف مع الدالة أعلاه إلى أنه قبل تعديل فقط القسم حيث المتغيرات تغييرات محددة. مزيد جزء من وظيفة لم يتغير (طبعا التعليقات ليس هنا ولكن أضفت عليها حيث أن الجميع يمكن أن نفهم بسرعة هذا خوارزمية بسيطة).
وهو أي ما يعادل ولكن ربما أقل قليلا للقراءة شكل الدالة أعلاه قد تبدو مثل هذا:
bool areRectanglesOverlap(Rectangle rect1, Rectangle rect2)
{
float left1, top1, right1, bottom1, left2, top2, right2, bottom2;
left1 = rect1.x;
top1 = rect1.y;
right1 = rect1.x + rect1.width;
bottom1 = rect1.y - rect1.height;
left2 = rect2.x;
top2 = rect2.y;
right2 = rect2.x + rect2.width;
bottom2 = rect2.y - rect2.height;
return !(top1 < bottom2 || top2 < bottom1 || right1 < left2 || right2 < left1);
}
و"إذا قمت بإجراء الطرح x أو إحداثيات ص الموافق القمم من اثنين تواجه كل مستطيل، وإذا كانت النتائج هي نفس علامة، المستطيل هما لا تتداخل محاور أن" (أنا آسف، أنا لست متأكدا من بلدي الترجمة الصحيحة)
المصدر: HTTP : //www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
كود جافا لمعرفة إذا مستطيلات يتم الاتصال أو متداخلة بعضها البعض
...
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < n; j++ ) {
if ( i != j ) {
Rectangle rectangle1 = rectangles.get(i);
Rectangle rectangle2 = rectangles.get(j);
int l1 = rectangle1.l; //left
int r1 = rectangle1.r; //right
int b1 = rectangle1.b; //bottom
int t1 = rectangle1.t; //top
int l2 = rectangle2.l;
int r2 = rectangle2.r;
int b2 = rectangle2.b;
int t2 = rectangle2.t;
boolean topOnBottom = t2 == b1;
boolean bottomOnTop = b2 == t1;
boolean topOrBottomContact = topOnBottom || bottomOnTop;
boolean rightOnLeft = r2 == l1;
boolean leftOnRight = l2 == r1;
boolean rightOrLeftContact = leftOnRight || rightOnLeft;
boolean leftPoll = l2 <= l1 && r2 >= l1;
boolean rightPoll = l2 <= r1 && r2 >= r1;
boolean leftRightInside = l2 >= l1 && r2 <= r1;
boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside;
boolean bottomPoll = t2 >= b1 && b2 <= b1;
boolean topPoll = b2 <= b1 && t2 >= b1;
boolean topBottomInside = b2 >= b1 && t2 <= t1;
boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside;
boolean topInBetween = t2 > b1 && t2 < t1;
boolean bottomInBetween = b2 > b1 && b2 < t1;
boolean topBottomInBetween = topInBetween || bottomInBetween;
boolean leftInBetween = l2 > l1 && l2 < r1;
boolean rightInBetween = r2 > l1 && r2 < r1;
boolean leftRightInBetween = leftInBetween || rightInBetween;
if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) {
path[i][j] = true;
}
}
}
}
...
