blocks|key|1533964|text|如果您使用的是Java语言，那么Shape接口的所有实现都有一个接受矩形的intersects方法。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1533965|entityMap|0|LINK|mutability|MUTABLE|url|http://java.sun.com/javase/6/docs/api/java/awt/Shape.html#intersects(double,%2520double,%2520double,%2520double)^0|11|A|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

If you're using Java, all implementations of the Shape interface have an <a href="http://java.sun.com/javase/6/docs/api/java/awt/Shape.html#intersects(double,%20double,%20double,%20double)" rel="nofollow noreferrer">intersects</a> method that take a rectangle.

blocks|key|1534039|text|嗯，暴力方法是走在水平矩形的边缘，并检查沿边缘的每个点，看看它是落在另一个矩形上还是在另一个矩形中。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1534040|数学上的答案是形成描述两个矩形的每一条边的方程。现在，您可以简单地找出矩形A的四条直线中的任何一条是否与矩形B的任何直线相交，这应该是一个简单(快速)的线性方程求解器。|1534041|-Adam|1534042|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Well, the brute force method is to walk the edges of the horizontal rectangle and check each point along the edge to see if it falls on or in the other rectangle.

The mathematical answer is to form equations describing each edge of both rectangles. Now you can simply find if any of the four lines from rectangle A intersect any of the lines of rectangle B, which should be a simple (fast) linear equation solver.

-Adam

blocks|key|1749006|text|检查一个矩形的任何直线是否与另一个矩形的任何直线相交。简单的线段相交很容易编码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1749007|如果您需要更快的速度，有用于直线段相交(扫描线)的高级算法。请参阅http://en.wikipedia.org/wiki/Line_segment_intersection|offset|length|1749008|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Line_segment_intersection^0|0|X|1I|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

Check to see if any of the lines from one rectangle intersect any of the lines from the other. Naive line segment intersection is easy to code up.

If you need more speed, there are advanced algorithms for line segment intersection (sweep-line). See <a href="http://en.wikipedia.org/wiki/Line_segment_intersection" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Line_segment_intersection</a>

blocks|key|1534241|text|您可以找到有角度矩形的每一条边与轴对齐矩形的每一条边的交点。要做到这一点，可以找到每一条边所在的无限直线的方程(即v1+%2B+t(v2-v1)和v'1+%2B+t'(v'2-v'+1+)+)，当这两个方程相等时，通过求解t来找到直线相交的点(如果它们是平行的，您可以对此进行测试)，然后测试该点是否位于两个顶点之间的线段上，即0+<=+t+<=+1和0+<=+t‘<=+1是否真的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1534242|然而，这并不涵盖当一个矩形完全覆盖另一个矩形的情况。您可以通过测试其中一个矩形的所有四个点是否都位于另一个矩形内来进行覆盖。|1534243|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

You could find the intersection of each side of the angled rectangle with each side of the axis-aligned one. Do this by finding the equation of the infinite line on which each side lies (i.e. v1 + t(v2-v1) and v'1 + t'(v'2-v'1) basically), finding the point at which the lines meet by solving for t when those two equations are equal (if they're parallel, you can test for that) and then testing whether that point lies on the line segment between the two vertices, i.e. is it true that 0 &lt;= t &lt;= 1 and 0 &lt;= t' &lt;= 1.

However, this doesn't cover the case when one rectangle completely covers the other. That you can cover by testing whether all four points of either rectangle lie inside the other rectangle.

blocks|key|1534305|text|一种解决方案是使用称为非拟合多边形的东西。这个多边形是从两个多边形计算出来的(概念上是通过围绕另一个多边形滑动)，它定义了在给定多边形相对偏移的情况下，多边形重叠的区域。一旦你有了这个NFP，那么你只需要用两个多边形的相对偏移量给出一个点来做一个包含测试。此包含测试既快速又简单，但您必须首先创建NFP。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1534306|在web上搜索No+Fit+Polygon，看看是否可以找到凸面多边形的算法(如果有凹面多边形，就会变得更加复杂)。如果你找不到任何东西，那就发邮件给我:+howard+dot+J+dot+may+gmail+dot+com|1534307|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

One solution is to use something called a No Fit Polygon. This polygon is calculated from the two polygons (conceptually by sliding one around the other) and it defines the area for which the polygons overlap given their relative offset. Once you have this NFP then you simply have to do an inclusion test with a point given by the relative offset of the two polygons. This inclusion test is quick and easy but you do have to create the NFP first.

Have a search for No Fit Polygon on the web and see if you can find an algorithm for convex polygons (it gets MUCH more complex if you have concave polygons). If you can't find anything then email me at howard dot J dot may gmail dot com

blocks|key|1749323|text|在Cocoa中，您可以很容易地检测selectedArea矩形是否与您旋转的NSView的框架矩形相交。你甚至不需要计算多边形，法线等等。只需将这些方法添加到NSView子类中即可。例如，用户在NSView的superview上选择一个区域，然后调用传递selectedArea+rect的DoesThisRectSelectMe方法。convertRect:接口将完成这项工作。当您单击NSView以将其选中时，也可以使用相同的技巧。在这种情况下，只需覆盖hitTest方法，如下所示。接口convertPoint:将完成这项工作;-)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1749324|-+(BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
++++NSRect+localArea+=+[self+convertRect:selectedArea+fromView:self.superview];

++++return+NSIntersectsRect(localArea,+self.bounds);
}


-+(NSView+*)hitTest:(NSPoint)aPoint
{
++++NSPoint+localPoint+=+[self+convertPoint:aPoint+fromView:self.superview];
++++return+NSPointInRect(localPoint,+self.bounds)+?+self+:+nil;
}|code-block|syntax|javascript|1749325|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

In Cocoa you could easily detect whether the selectedArea rect intersects your rotated NSView's frame rect.
You don't even need to calculate polygons, normals an such. Just add these methods to your NSView subclass.
For instance, the user selects an area on the NSView's superview, then you call the method DoesThisRectSelectMe passing the selectedArea rect. The API convertRect: will do that job. The same trick works when you click on the NSView to select it. In that case simply override the hitTest method as below. The API convertPoint: will do that job ;-)

<pre><code>- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
 NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

 return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
 NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
 return NSPointInRect(localPoint, self.bounds) ? self : nil;
}
</code></pre>

blocks|key|1749401|text|要不是我漏掉了什么，为什么要把事情搞得这么复杂？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1749402|如果(x1，y1)和(X1，Y1)是矩形的角点，则要查找交点，请执行以下操作：|1749403|++++xIntersect+=+false;
++++yIntersect+=+false;
++++if+(!(Math.min(x1,+x2,+x3,+x4)+>+Math.max(X1,+X2,+X3,+X4)+%7C%7C+Math.max(x1,+x2,+x3,+x4)+<+Math.min(X1,+X2,+X3,+X4)))+xIntersect+=+true;
++++if+(!(Math.min(y1,+y2,+y3,+y4)+>+Math.max(Y1,+Y2,+Y3,+Y4)+%7C%7C+Math.max(y1,+y2,+y3,+y4)+<+Math.min(Y1,+Y2,+Y3,+Y4)))+yIntersect+=+true;
++++if+(xIntersect+&&+yIntersect)+{alert("Intersect");}|code-block|syntax|javascript|1749404|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Either I am missing something else why make this so complicated?

if (x1,y1) and (X1,Y1) are corners of the rectangles, then to find intersection do:

<pre><code> xIntersect = false;
 yIntersect = false;
 if (!(Math.min(x1, x2, x3, x4) &gt; Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) &lt; Math.min(X1, X2, X3, X4))) xIntersect = true;
 if (!(Math.min(y1, y2, y3, y4) &gt; Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) &lt; Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
 if (xIntersect &amp;&amp; yIntersect) {alert("Intersect");}
</code></pre>

blocks|key|1749446|text|我是这样实现的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1749447|bool+rectCollision(const+CGRect+&boundsA,+const+Matrix3x3+&mB,+const+CGRect+&boundsB)
{
++++float+Axmin+=+boundsA.origin.x;
++++float+Axmax+=+Axmin+%2B+boundsA.size.width;
++++float+Aymin+=+boundsA.origin.y;
++++float+Aymax+=+Aymin+%2B+boundsA.size.height;

++++float+Bxmin+=+boundsB.origin.x;
++++float+Bxmax+=+Bxmin+%2B+boundsB.size.width;
++++float+Bymin+=+boundsB.origin.y;
++++float+Bymax+=+Bymin+%2B+boundsB.size.height;

++++//+find+location+of+B+corners+in+A+space
++++float+B0x+=+mB(0,0)+*+Bxmin+%2B+mB(0,1)+*+Bymin+%2B+mB(0,2);
++++float+B0y+=+mB(1,0)+*+Bxmin+%2B+mB(1,1)+*+Bymin+%2B+mB(1,2);

++++float+B1x+=+mB(0,0)+*+Bxmax+%2B+mB(0,1)+*+Bymin+%2B+mB(0,2);
++++float+B1y+=+mB(1,0)+*+Bxmax+%2B+mB(1,1)+*+Bymin+%2B+mB(1,2);

++++float+B2x+=+mB(0,0)+*+Bxmin+%2B+mB(0,1)+*+Bymax+%2B+mB(0,2);
++++float+B2y+=+mB(1,0)+*+Bxmin+%2B+mB(1,1)+*+Bymax+%2B+mB(1,2);

++++float+B3x+=+mB(0,0)+*+Bxmax+%2B+mB(0,1)+*+Bymax+%2B+mB(0,2);
++++float+B3y+=+mB(1,0)+*+Bxmax+%2B+mB(1,1)+*+Bymax+%2B+mB(1,2);

++++if(B0x<Axmin+&&+B1x<Axmin+&&+B2x<Axmin+&&+B3x<Axmin)
++++++++return+false;
++++if(B0x>Axmax+&&+B1x>Axmax+&&+B2x>Axmax+&&+B3x>Axmax)
++++++++return+false;
++++if(B0y<Aymin+&&+B1y<Aymin+&&+B2y<Aymin+&&+B3y<Aymin)
++++++++return+false;
++++if(B0y>Aymax+&&+B1y>Aymax+&&+B2y>Aymax+&&+B3y>Aymax)
++++++++return+false;

++++float+det+=+mB(0,0)*mB(1,1)+-+mB(0,1)*mB(1,0);
++++float+dx+=+mB(1,2)*mB(0,1)+-+mB(0,2)*mB(1,1);
++++float+dy+=+mB(0,2)*mB(1,0)+-+mB(1,2)*mB(0,0);

++++//+find+location+of+A+corners+in+B+space
++++float+A0x+=+(mB(1,1)+*+Axmin+-+mB(0,1)+*+Aymin+%2B+dx)/det;
++++float+A0y+=+(-mB(1,0)+*+Axmin+%2B+mB(0,0)+*+Aymin+%2B+dy)/det;

++++float+A1x+=+(mB(1,1)+*+Axmax+-+mB(0,1)+*+Aymin+%2B+dx)/det;
++++float+A1y+=+(-mB(1,0)+*+Axmax+%2B+mB(0,0)+*+Aymin+%2B+dy)/det;

++++float+A2x+=+(mB(1,1)+*+Axmin+-+mB(0,1)+*+Aymax+%2B+dx)/det;
++++float+A2y+=+(-mB(1,0)+*+Axmin+%2B+mB(0,0)+*+Aymax+%2B+dy)/det;

++++float+A3x+=+(mB(1,1)+*+Axmax+-+mB(0,1)+*+Aymax+%2B+dx)/det;
++++float+A3y+=+(-mB(1,0)+*+Axmax+%2B+mB(0,0)+*+Aymax+%2B+dy)/det;

++++if(A0x<Bxmin+&&+A1x<Bxmin+&&+A2x<Bxmin+&&+A3x<Bxmin)
++++++++return+false;
++++if(A0x>Bxmax+&&+A1x>Bxmax+&&+A2x>Bxmax+&&+A3x>Bxmax)
++++++++return+false;
++++if(A0y<Bymin+&&+A1y<Bymin+&&+A2y<Bymin+&&+A3y<Bymin)
++++++++return+false;
++++if(A0y>Bymax+&&+A1y>Bymax+&&+A2y>Bymax+&&+A3y>Bymax)
++++++++return+false;

++++return+true;
}|code-block|syntax|javascript|1749448|矩阵mB是将B空间中的点转换为A空间中的点的任何仿射变换矩阵。这包括简单的旋转和平移、旋转加缩放和完全仿射扭曲，但不包括透视扭曲。|1749449|它可能不是最优的。速度并不是一个大问题。然而，它看起来对我来说还行。|1749450|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

I implemented it like this:

<pre><code>bool rectCollision(const CGRect &amp;boundsA, const Matrix3x3 &amp;mB, const CGRect &amp;boundsB)
{
 float Axmin = boundsA.origin.x;
 float Axmax = Axmin + boundsA.size.width;
 float Aymin = boundsA.origin.y;
 float Aymax = Aymin + boundsA.size.height;

 float Bxmin = boundsB.origin.x;
 float Bxmax = Bxmin + boundsB.size.width;
 float Bymin = boundsB.origin.y;
 float Bymax = Bymin + boundsB.size.height;

 // find location of B corners in A space
 float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
 float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);

 float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
 float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);

 float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
 float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);

 float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
 float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);

 if(B0x&lt;Axmin &amp;&amp; B1x&lt;Axmin &amp;&amp; B2x&lt;Axmin &amp;&amp; B3x&lt;Axmin)
 return false;
 if(B0x&gt;Axmax &amp;&amp; B1x&gt;Axmax &amp;&amp; B2x&gt;Axmax &amp;&amp; B3x&gt;Axmax)
 return false;
 if(B0y&lt;Aymin &amp;&amp; B1y&lt;Aymin &amp;&amp; B2y&lt;Aymin &amp;&amp; B3y&lt;Aymin)
 return false;
 if(B0y&gt;Aymax &amp;&amp; B1y&gt;Aymax &amp;&amp; B2y&gt;Aymax &amp;&amp; B3y&gt;Aymax)
 return false;

 float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
 float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
 float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);

 // find location of A corners in B space
 float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
 float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;

 float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
 float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;

 float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
 float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;

 float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
 float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;

 if(A0x&lt;Bxmin &amp;&amp; A1x&lt;Bxmin &amp;&amp; A2x&lt;Bxmin &amp;&amp; A3x&lt;Bxmin)
 return false;
 if(A0x&gt;Bxmax &amp;&amp; A1x&gt;Bxmax &amp;&amp; A2x&gt;Bxmax &amp;&amp; A3x&gt;Bxmax)
 return false;
 if(A0y&lt;Bymin &amp;&amp; A1y&lt;Bymin &amp;&amp; A2y&lt;Bymin &amp;&amp; A3y&lt;Bymin)
 return false;
 if(A0y&gt;Bymax &amp;&amp; A1y&gt;Bymax &amp;&amp; A2y&gt;Bymax &amp;&amp; A3y&gt;Bymax)
 return false;

 return true;
}
</code></pre>

The matrix mB is any affine transform matrix that converts points in the B space to points in the A space. This includes simple rotation and translation, rotation plus scaling, and full affine warps, but not perspective warps.

It may not be as optimal as possible. Speed was not a huge concern. However it seems to work ok for me.

blocks|key|1749470|text|以下是公认答案的matlab实现：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1749471|function+olap_flag+=+ol(A,B,sub)

%25A+and+B+should+be+4+x+2+matrices+containing+the+xy+coordinates+of+the+corners+in+clockwise+order

if+nargin+==+2
++olap_flag+=+ol(A,B,1)+&&+ol(B,A,1);
++return;
end

urdl+=+diff(A([1:4+1],:));
s+=+sum(urdl+.*+A,+2);
sdiff+=+B+*+urdl'+-+repmat(s,[1+4]);

olap_flag+=+~any(max(sdiff)<0);|code-block|syntax|javascript|1749472|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is a matlab implementation of the accepted answer:

<pre><code>function olap_flag = ol(A,B,sub)

%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order

if nargin == 2
 olap_flag = ol(A,B,1) &amp;&amp; ol(B,A,1);
 return;
end

urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);

olap_flag = ~any(max(sdiff)&lt;0);
</code></pre>

blocks|key|1534591|text|这是传统的方法，逐行检查这些线是否相交。这是MATLAB中的代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1534592|C1+=+[0,+0];++++%25+Centre+of+rectangle+1+(x,y)
C2+=+[1,+1];++++%25+Centre+of+rectangle+2+(x,y)
W1+=+5;+W2+=+3;+%25+Widths+of+rectangles+1+and+2
H1+=+2;+H2+=+3;+%25+Heights+of+rectangles+1+and+2
%25+Define+the+corner+points+of+the+rectangles+using+the+above
R1+=+[C1(1)+%2B+[W1;+W1;+-W1;+-W1]/2,+C1(2)+%2B+[H1;+-H1;+-H1;+H1]/2];
R2+=+[C2(1)+%2B+[W2;+W2;+-W2;+-W2]/2,+C2(2)+%2B+[H2;+-H2;+-H2;+H2]/2];

R1+=+[R1+;+R1(1,:)]+;
R2+=+[R2+;+R2(1,:)]+;

plot(R1(:,1),R1(:,2),'r')
hold+on
plot(R2(:,1),R2(:,2),'b')


%25%25+lines+of+Rectangles+
L1+=+[R1(1:end-1,:)+R1(2:end,:)]+;
L2+=+[R2(1:end-1,:)+R2(2:end,:)]+;
%25%25+GEt+intersection+points
P+=+zeros(2,[])+;
count+=+0+;
for+i+=+1:4
++++line1+=+reshape(L1(i,:),2,2)+;
++++for+j+=+1:4
++++++++line2+=+reshape(L2(j,:),2,2)+;
++++++++point+=+InterX(line1,line2)+;
++++++++if+~isempty(point)
++++++++++++count+=+count%2B1+;
++++++++++++P(:,count)+=+point+;
++++++++end
++++end
end
%25%25
if+~isempty(P)
++++fprintf('Given+rectangles+intersect+at+%25d+points:\n',size(P,2))
++++plot(P(1,:),P(2,:),'*k')
end|code-block|syntax|javascript|1534593|可以从https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function下载函数InterX|offset|length|1534594|entityMap|0|LINK|mutability|MUTABLE|url|https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function^0|0|0|3|2Y|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@$I|V|J|W|1|X]]|A|$]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

This is the conventional method, go line by line and check whether the lines are intersecting. This is the code in MATLAB. 

<pre><code>C1 = [0, 0]; % Centre of rectangle 1 (x,y)
C2 = [1, 1]; % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];

R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;

plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')


%% lines of Rectangles 
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
 line1 = reshape(L1(i,:),2,2) ;
 for j = 1:4
 line2 = reshape(L2(j,:),2,2) ;
 point = InterX(line1,line2) ;
 if ~isempty(point)
 count = count+1 ;
 P(:,count) = point ;
 end
 end
end
%%
if ~isempty(P)
 fprintf('Given rectangles intersect at %d points:\n',size(P,2))
 plot(P(1,:),P(2,:),'*k')
end
</code></pre>

the function InterX can be downloaded from: <a href="https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&amp;tab=function" rel="nofollow noreferrer">https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&amp;tab=function</a>

blocks|key|1749591|text|我自己有一个更简单的方法，如果我们有两个矩形：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1749592|R1+=+(min_x1，max_x1，min_y1，max_y1)|1749593|R2+=+(min_x2，max_x2，min_y2，max_y2)|1749594|当且仅在以下情况下，它们会重叠：|1749595|重叠=+(max_x1+>+min_x2)和(max_x2+>+min_x1)和(max_y1+>+min_y2)和(max_y2+>+min_y1)|1749596|你也可以对3D盒子这样做，实际上它适用于任何数量的尺寸。|1749597|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|S|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

I have a simplier method of my own, if we have 2 rectangles:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

They overlap if and only if:

Overlap = (max_x1 > min_x2) and (max_x2 > min_x1) and (max_y1 > min_y2) and (max_y2 > min_y1)

You can do it for 3D boxes too, actually it works for any number of dimensions.

blocks|key|1749639|text|在其他答案中已经说得够多了，所以我只添加伪代码一行：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1749640|!(a.left+>+b.right+%7C%7C+b.left+>+a.right+%7C%7C+a.top+>+b.bottom+%7C%7C+b.top+>+a.bottom);|code-block|syntax|javascript|1749641|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Enough has been said in other answers, so I'll just add pseudocode one-liner:

<pre class="lang-js prettyprint-override"><code>!(a.left &gt; b.right || b.left &gt; a.right || a.top &gt; b.bottom || b.top &gt; a.bottom);
</code></pre>

blocks|key|1534761|text|检查两个矩形的所有顶点的质心是否位于其中一个矩形内。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1534762|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Check if the center of mass of all the vertices of both rectangles lies within one of the rectangles.

I'm looking for an algorithm to detect if two rectangles intersect (one at an arbitrary angle, the other with only vertical/horizontal lines).

Testing if a corner of one is in the other ALMOST works. It fails if the rectangles form a cross-like shape.

It seems like a good idea to avoid using slopes of the lines, which would require special cases for vertical lines.

Algorithm to detect intersection of two rectangles?

Java

我正在寻找一种算法来检测两个矩形是否相交(一个以任意角度，另一个只有垂直线/水平线)。测试其中一个的一角是否在另一个中几乎是有效的。如果矩形形成类似十字的形状，它将失败。这似乎是一个好主意，避免使用线的斜率，这将需要垂直线的特殊情况。

问检测两个矩形相交的算法？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问检测两个矩形相交的算法？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问检测两个矩形相交的算法？
EN