回 帖 发 新 帖 刷新版面

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

矩形用两个坐标点表示,左下角坐标和右上角坐标。现有两个矩形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搜索了很多,但就是找不到相类似的题目和解答,请高手给出解答,给出用什么数据结构表示,算法的大概思路即可,不用源代码(有的话更好 :)。 不胜感激,谢谢。期待解答中.....
_________________

回复列表 (共5个回复)

沙发

如果数据都是整数且数据规模较小(一般小于2000*2000)可以直接用数组模拟

板凳

请高手给出算法的详细点的算法步骤,特别是关键部分的详细点,谢谢

3 楼

不考虑二维 ,先考虑线段的情况,应该不难?

那么再推广到二维...

4 楼

可否明示一下,谢谢

5 楼

高手在哪呢??
难道此地无高手吗??

我来回复

您尚未登录,请登录后再回复。点此登录或注册