两个矩形之间的差异（XOR），如矩形？ [英] Difference (XOR) between two rectangles, as rectangles?
问题描述
我正在寻找一种简单的方法来计算两个矩形之间的差异。我的意思是属于其中一个矩形的所有点，但不是两个（所以它就像异或）。
矩形在这种情况下是轴对齐的，所以在那里将只有正确的角度。我相信差异区域可以用0-4个矩形表示（如果两个矩形相同，则为0，如果只是一个边缘不同，则为1，一般情况下为4），我想将差异区域作为列表
您也可以将其视为在移动/调整大小的实心矩形时必须更新的屏幕区域。
示例：将矩形a的宽度加倍 - 我想要添加的区域（R）。
+ ---- + ---- +
| a | R |
| | |
+ ---- + ---- +
相交矩形（a和b ） - 我想要矩形中的T，L，R和B给出的区域（其他分区可能），但不包括X：
+ ------------ + a
| T |
|·····+ ------ + ----- + b
| L | X | R |
| | | |
+ ----- + ------ +·····| |
| B |
+ ------------ +
我会喜欢Python解决方案/库，但任何强大的算法会有帮助。
解决方案将问题分解到每个轴的基础上。您的矩形可以根据每个轴上的跨度来定义 - 在矩形开始或结束的每个轴上查找有趣的点，然后用这些术语定义结果。这将给你6个不同区域的矩形，你可以很容易地将它们组合到你已经说明的四个矩形区域，或者如果你需要的话，可以消除退化的零区域矩形。
这是一个Java实现：
public class Rect
{
private float minX，maxX，minY，美星;
public Rect（float minX，float maxX，float minY，float maxY）
{
this.minX = minX;
this.maxX = maxX;
this.minY = minY;
this.maxY = maxY;
}
/ **
*查找两个相交矩形之间的差异
*
* @param r
* @param s
* @return由r或s覆盖的矩形区域数组，但
*不是
* /
public static Rect [] diff（Rect r，Rect s ）
{
float a = Math.min（r.minX，s.minX）;
float b = Math.max（r.minX，s.minX）;
float c = Math.min（r.maxX，s.maxX）;
float d = Math.max（r.maxX，s.maxX）;
float e = Math.min（r.minY，s.minY）;
float f = Math.max（r.minY，s.minY）;
float g = Math.min（r.maxY，s.maxY）;
float h = Math.max（r.maxY，s.maxY）;
// X =十字路口，0-7 =可能的差异区域
// h + - + - + - +
//。 | 5 | 6 | 7 |
// g + - + - + - +
//。 | 3 | X | 4 |
// f + - + - + - +
//。 | 0 | 1 | 2 |
// e + - + - + - +
//。 a b c d
Rect [] result = new Rect [6];
//我们总是有矩形1,3,4和6
result [0] = new Rect（b，c，e，f）;
result [1] = new Rect（a，b，f，g）;
result [2] = new Rect（c，d，f，g）;
result [3] = new Rect（b，c，g，h）;
//决定哪个角落
if（r.minX == a&& r.minY == e || s.minX == a&& s.minY == e）
{//转角0和7
结果[4] =新的Rect（a，b，e，f）;
result [5] = new Rect（c，d，g，h）;
}
else
{//角点2和5
结果[4] = new Rect（c，d，e，f）;
结果[5] =新Rect（a，b，g，h）;
}
返回结果;
}
}
I'm looking for a simple way to calculate the difference between two rectangles. I mean all points which belong to one of the rectangles, but not to both (so it's like XOR).
The rectangles are axis-aligned in this case, so there will be only right angles. I believe the difference region can be expressed in 0-4 rectangles (0 if both rectangles are the same, 1 if just one edge is different, 4 in the general case), and I'd like to get the difference region as a list of rectangles.
You can also think of it as the areas of the screen that have to be updated when a solid rectangle is moved/resized.
Examples: Doubling the width of rectangle "a" - I want the added region (R).
+----+----+
| a | R |
| | |
+----+----+
Intersecting rectangles (a and b) - I want the area given by T, L, R and B in rectangles (other partitioning possible), but excluding X:
+------------+ a
| T |
|·····+------+-----+ b
| L | X | R |
| | | |
+-----+------+·····|
| B |
+------------+
I'd prefer a python solution/library, but any robust algorithm would be helpful.
Split the problem down onto a per-axis basis. Your rectangles can be defined in terms of their spans on each axis - find the interesting points on each axis where a rectangle starts or ends and then define your results in those terms. This'll give you 6 rectangles of difference areas, you can easily combine them down to the four you've illustrated or eliminate degenerate zero-area rectangles if you need to.
Here's a Java implementation:
public class Rect
{
private float minX, maxX, minY, maxY;
public Rect( float minX, float maxX, float minY, float maxY )
{
this.minX = minX;
this.maxX = maxX;
this.minY = minY;
this.maxY = maxY;
}
/**
* Finds the difference between two intersecting rectangles
*
* @param r
* @param s
* @return An array of rectangle areas that are covered by either r or s, but
* not both
*/
public static Rect[] diff( Rect r, Rect s )
{
float a = Math.min( r.minX, s.minX );
float b = Math.max( r.minX, s.minX );
float c = Math.min( r.maxX, s.maxX );
float d = Math.max( r.maxX, s.maxX );
float e = Math.min( r.minY, s.minY );
float f = Math.max( r.minY, s.minY );
float g = Math.min( r.maxY, s.maxY );
float h = Math.max( r.maxY, s.maxY );
// X = intersection, 0-7 = possible difference areas
// h +-+-+-+
// . |5|6|7|
// g +-+-+-+
// . |3|X|4|
// f +-+-+-+
// . |0|1|2|
// e +-+-+-+
// . a b c d
Rect[] result = new Rect[ 6 ];
// we'll always have rectangles 1, 3, 4 and 6
result[ 0 ] = new Rect( b, c, e, f );
result[ 1 ] = new Rect( a, b, f, g );
result[ 2 ] = new Rect( c, d, f, g );
result[ 3 ] = new Rect( b, c, g, h );
// decide which corners
if( r.minX == a && r.minY == e || s.minX == a && s.minY == e )
{ // corners 0 and 7
result[ 4 ] = new Rect( a, b, e, f );
result[ 5 ] = new Rect( c, d, g, h );
}
else
{ // corners 2 and 5
result[ 4 ] = new Rect( c, d, e, f );
result[ 5 ] = new Rect( a, b, g, h );
}
return result;
}
}
这篇关于两个矩形之间的差异（XOR），如矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
