[问题]一矩形重叠／切割算法题，望高手给出解答,期待中......

[vincent_zh]

矩形用两个坐标点表示，左下角坐标和右上角坐标。现有两个矩形A和B，分别输入两个矩形的左下角和右上角坐标，求出矩形A被矩形B切割后的所形成的若干个矩形区域，也分别用左下角和右上角表示。

如下输入：
0,0 //A的左下角坐标
2,2 //A的右上角坐标
1,1 //B的左下角坐标
3,3 //B的右上角坐标

输出为：
(0,0)-(1,2)
(1,0)-(2,1)

或另一种表达方式也可，如下
(0,0)-(2,1)
(0,1)-(1,2)

请问这样的题目，应该怎么做？？
我已经用google和baidu搜索了很多，但就是找不到相类似的题目和解答，请高手给出解答，给出用什么数据结构表示，算法的大概思路即可，不用源代码（有的话更好 ：）。 不胜感激，谢谢。期待解答中.....

[vincent_zh]

期待中。。。。。。

[BigSnake.NET]

只有两个矩形?

不过思路都是差不多

1. 按所有矩形的数据对平面离散化
2. 标记
3. 扫描平面, 找所有矩形

[tipfoo]

1. 按所有矩形的数据对平面离散化
2. 标记
3. 扫描平面, 找所有矩形

实在太精练了！差点没明白

[vincent_zh]

最困难的就是扫描算法了，请问可否有扫描算法的详细步骤

[tipfoo]

google "凸多边形 扫描算法"

http://www.geomodel.com.cn/html/College ... 6/281.html

[tipfoo]

这个可能更适合你：

代码： 全选

摘　　要:
提出了一个面向快速成型扫描路径规划的凹多边形凸分解算法。首先应用所提出的基于正负法搜索凹点对应的可见点的新算法来找出凹点的可见点串，然后结合所提出的适用于快速制造中扫描分区的剖分准则，利用权函数选择最佳剖分点，并合理使用辅助点，保证了剖分所得凸多边形的形态质量。该算法作为快速成形选区环形扫描路径规划软件的底层算法，在对待扫描的层面轮廓进行分区时得到了应用。[著者文摘]

关 键 词:
凹多边形 凸分解 正负法 可见点 快速成型 分区扫描

文章出处: 《计算机应用》-2005年25卷9期 -2143-2145页
journal of Computer Applications

栏目信息: 图形图像处理
分 类 号: TP391.72
文献标识码: A
文章编号: 1001-9081（2005）09-2143-03

[laborer]

两个正交矩形处理起来不需要那么复杂吧，手工把几个情况枚举一下就可以。下面的程序是python写的

代码： 全选

x=[0,2,1,3]
y=[0,2,1,3]
print [(a,c,b,d) for (a,b,c,d) in [(x[0],min(x[1],x[2]),y[0],y[1]), (max(x[0],x[3]),x[1],y[0],y[1]), (max(x[0],x[2]),min(x[1],x[3]),y[0],min(y[1],y[2])), (max(x[0],x[2]),min(x[1],x[3]),max(y[0],y[3]),y[1])] if b>a and d>c]

输出

代码： 全选

[(0, 0, 1, 2), (1, 0, 2, 1)]

[vincent_zh]

解决方案：
#include <iostream>
using namespace std;

int main()
{
int m1_l, m1_r, m1_b, m1_t;
int m2_l, m2_r, m2_b, m2_t;

cin >> m1_l >> m1_b >> m1_r >> m1_t;
cin >> m2_l >> m2_b >> m2_r >> m2_t;

if (m1_l < m2_l && m1_b < m1_t)
cout << m1_l << " " << m1_b << " - " << m2_l << " " << m1_t << endl;
if (m2_l < m1_r && m1_b < m2_b)
cout << m2_l << " " << m1_b << " - " << m1_r << " " << m2_b << endl;
if (m2_l < m2_r && m2_t < m1_t)
cout << m2_l << " " << m2_t << " - " << m2_r << " " << m1_t << endl;
if (m2_r < m1_r && m2_b < m1_t)
cout << m2_r << " " << m2_b << " - " << m1_r << " " << m1_t << endl;

return 0;
}

[vincent_zh]

代码： 全选

#include <iostream>
using namespace std;

int main()
{
	int m1_l, m1_r, m1_b, m1_t;
	int m2_l, m2_r, m2_b, m2_t;

	cin >> m1_l >> m1_b >> m1_r >> m1_t;
	cin >> m2_l >> m2_b >> m2_r >> m2_t;

	if (m1_l < m2_l && m1_b < m1_t)
		cout << m1_l << " " << m1_b << " - " << m2_l << " " << m1_t << endl;
	if (m2_l < m1_r && m1_b < m2_b)
		cout << m2_l << " " << m1_b << " - " << m1_r << " " << m2_b << endl;
	if (m2_l < m2_r && m2_t < m1_t)
		cout << m2_l << " " << m2_t << " - " << m2_r << " " << m1_t << endl;
	if (m2_r < m1_r && m2_b < m1_t)
		cout << m2_r << " " << m2_b << " - " << m1_r << " " << m1_t << endl;

	return 0;
}

[/code]

[vincent_zh]

我还想出了一个解决方案，就是比较繁锁了点

代码： 全选

#include <iostream>
#include <vector>

using namespace std;

struct Point
{
	int left;
	int right;
};


void overlap(Point a, Point b, vector<Point> & over_vector, vector<Point> & n_over_vector)
{
	Point temp_point;
	if (b.right <= a.left)
	{
		n_over_vector.push_back(a);	
	}for (int i = 0; i < h_n_over_vector.size(); i++)
	{
		cout << h_n_over_vector[i].left << " ";
		cout << v_1.left;
		cout << " , ";
		cout << h_n_over_vector[i].right << " ";
		cout << v_1.right;
	}
	else if (b.right > a.left && b.right < a.right)
	{
		if (b.left <= a.left)
		{
			temp_point.left = a.left, temp_point.right = b.right;	
			over_vector.push_back(temp_point);
			temp_point.left = b.right, temp_point.right = a.right;
			n_over_vector.push_back(temp_point);
		}
		else //b.left > a.left
		{
			temp_point.left = a.left, temp_point.right = b.left;
			n_over_vector.push_back(temp_point);
			temp_point.left = b.left, temp_point.right = b.right;
			over_vector.push_back(temp_point);
			temp_point.left = b.right, temp_point.right = a.right;
			n_over_vector.push_back(temp_point);
		}
	}
	else if (b.right == a.right)
	{
		if (b.left <= a.left)
		{
			over_vector.push_back(a);
		for (int i = 0; i < h_n_over_vector.size(); i++)
	{
		cout << h_n_over_vector[i].left << " ";
		cout << v_1.left;
		cout << " , ";
		cout << h_n_over_vector[i].right << " ";
		cout << v_1.right;
	}}
		else //b.left > a.left
		{
			temp_point.left = a.left, temp_point.right = b.left;
			n_over_vector.push_back(temp_point);
			temp_point.left = b.left, temp_point.right = a.right;
			over_vector.push_back(temp_point);
		}
	}
	else //b.right > a.right
	{
		if (b.left <= a.left)
		{
			over_vector.push_back(temp_point);
		}
		else if (b.left > a.left && b.left < a.right)
		{
			temp_point.left = a.left, temp_point.right = b.left;
			n_over_vector.push_back(temp_point);
		for (int i = 0; i < h_n_over_vector.size(); i++)
	{
		cout << h_n_over_vector[i].left << " ";
		cout << v_1.left;
		cout << " , ";
		cout << h_n_over_vector[i].right << " ";
		cout << v_1.right;
	}	temp_point.left = b.left, temp_point.right = a.right;
			over_vector.push_back(temp_point);
		}
		else //b.left >= a.right
		{
			n_over_vector.push_back(a);
		}
	}
}

int main()
{
	vector<Point> h_over_vector, v_over_vector;
	vector<Point> h_n_over_vector, v_n_over_vector; 
	int left, bottom, right, top;
	Point h_1, h_2;
	Point v_1, v_2;
	
	cout << "第一个矩形的左下角坐标:"; cin >> h_1.left >> v_1.left;
	cout << "第一个矩形的右上角坐标:"; cin >> h_1.right >> v_1.right;
       	cout << "第二个矩形的左下角坐标:"; cin >> h_2.left >> v_2.left;
	cout << "第二个矩形的右上角坐标:"; cin >> h_2.right >> v_2.right;

	overlap(h_1, h_2, h_over_vector, h_n_over_vector);
	overlap(v_1, v_2, v_over_vector, v_n_over_vector);

	for (int i = 0; i < h_n_over_vector.size(); i++)
	{
		cout << h_n_over_vector[i].left << " ";
		cout << v_1.left;
		cout << " , ";
		cout << h_n_over_vector[i].right << " ";
		cout << v_1.right << endl;
	}

	for (int i = 0; i < h_over_vector.size(); i++)
	{
		for (int j = 0; j < v_n_over_vector.size(); j++)
		{
			cout << h_over_vector[i].left << " ";
			cout << v_n_over_vector[j].left;
			cout << " , ";
			cout << h_over_vector[i].right << " ";
			cout << v_n_over_vector[i].right << endl;
		}
	}

	

	return 0;
}