大家有没有比较好的算法解决这个有关问题
大家有没有比较好的算法解决这个问题。
现在有个数组，数组里面有N个矩形RECT（x1,y1,x2,y2），每一层的矩形都是一样高的，现在要根据这N个矩形得到一个数组，数组是POINT(x,y)的集合。比如下面有5个矩形，其实就是要得到一个外接N边形。各位有什么号的想法没。
------解决思路----------------------
参考这段代码中的扫描线填充算法：
------解决思路----------------------
一个数组保存了N个CRect,即4N个点
够建新数组保存4N个点 (left,top) (left,bottom) (right,top) (right,bottom)
扫描新数组,重复的点删掉(功力够就直接边扫描边加
对新数组按x排序,或按y值排序
------解决思路----------------------
1. 首先把矩形分解成边,遍历所有矩形,把每个矩形的四条边都放到一个边的集合里面. 假设这个边的集合为 A.
2. 遍历 A 里面所有的边, 两两之间进行比较, 如果:
(1) 两条边完全相同, 这把这两条边都从集合 A 中删除.
(2) 如果一条边完全包含了另外一条边, 则把较长的边分解成 左 中 右 三段, 中间那段和较短的那条相同. 从 A 中删除原来的那两条边, 并把 左段和右段 两条新的边加入集合 A 中.
(3) 两条边应该不会出现交叉的.
3. 经过第 2 步处理后, A 中剩下的边已经是一个多边形的外轮廓了, 我们只需要把结果取出来就行:
(1) 取任意一条边, 选任意一个点作为起点, 放入结果数组中. 边另外一个点就是起点的下一个点, 假设为当前点 p.
(2) 从 A 中搜索经过点 p 的边, 把 p 放入结果数组中, 边的另外一个点作为 p 重复该步骤即可.
------解决思路----------------------
1.首先选择一点开始，从该点按照下，右，上，左的方向走
2.从起点向下走，一直走到底，然后以到达的点为起点，以来的时候的方向为参考方向，还是按照逆时针的方向顺次选择前进的方向。
比如第一个图，选择起点，然后向下走到底，到达第二个点，
以这个点为起点，以向上为参考方向，选择向左右，向下走，因为这两个方向都没有路径，所以只能向右走了，
向右一直走到第三个点，以这个点为起点，以向左为参考方向，选择向下走，向右走，都没有路径，于是向上走有路径，走到第四个点。。。一直走下去就会有一个N边形
现在有个数组，数组里面有N个矩形RECT（x1,y1,x2,y2），每一层的矩形都是一样高的，现在要根据这N个矩形得到一个数组，数组是POINT(x,y)的集合。比如下面有5个矩形，其实就是要得到一个外接N边形。各位有什么号的想法没。
------解决思路----------------------
参考这段代码中的扫描线填充算法：
//试题编号：0186
//海龟圈地
//难度级别：D； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B
//试题描述
// 海龟小蛮在沙滩上趾高气扬地走来走去，并且蛮横地宣布：“凡我足迹所到之处均为本海龟的领地。”
// 海龟的任何行动均可分解为下面三个基本动作：
// f 向前爬一格
// l 原地左转90度
// r 原地右转90度
// 由于小蛮不允许别的海龟经过它的领地，所以，由它足迹围成的封闭区域也就都成了它的领地。
// 你的任务是编程序根据文件输入的小蛮的一系列基本动作，计算出小蛮共霸占了多少格的领地。
// 程序文件主名为turtle。
// 为加深对题意的理解，我们观察下面的基本动作序列：
// flffflfffrfrrffflf
// 小蛮在出发点当然会留下足迹#，如果把它开始的方向设为向下，可以把它的足迹（用*标出的位置）画成下面的示意图：
// ****
// * *
// # *
// ****
// 显然，小蛮的领地总数为15格。
//输入
// 其中只有一个长度不超过1000的字符串，且该字符串不包含'f'、'l'、'r'之外的字符。
//输出
// 其中只有一个正整数，即领地总格数。
//输入示例
// flffflfffrfrrffflf
//输出示例
// 15
//其他说明
// 2011年北京市海淀区中学组赛题
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000
static char n[2*MAXN+2][2*MAXN+2];//记录某处被爬过信息:0未爬过
------解决思路----------------------
1爬过
char f;//当前方向'N'
------解决思路----------------------
'S'
------解决思路----------------------
'W'
------解决思路----------------------
'E'
int x,y;//当前位置
char p[MAXN+1];
int i,L;
int a,b,h,t;
int sp=0;
int x1[MAXN];
int x2[MAXN];
int y1[MAXN];
int yy1,xx1,xx2;
void push(int ay1,int ax1,int ax2) {
y1[sp]=ay1;
x1[sp]=ax1;
x2[sp]=ax2;
if (sp<MAXN-1) {
sp=sp+1;
} else {
printf("stack overflow!\n");
exit(1);
}
}
void pop(void) {
sp=sp-1;
yy1=y1[sp];
xx1=x1[sp];
xx2=x2[sp];
}
//void show() {
// int zy,zx;
//
// for (zy=0;zy<2*MAXN+2;zy++) {
// for (zx=0;zx<2*MAXN+2;zx++) {
// printf("%d",n[zy][zx]);
// }
// printf("\n");
// }
// printf("\n");
//}
void scanlinefill() {
int xx,ax1,ax2;
while (1) {
if (sp<=0) break;//
pop();
// printf("O yy1,xx1,xx2=%d,%d,%d\n",yy1,xx1,xx2);
for (xx=xx1;xx<=xx2;xx++) n[yy1][xx]=2;//填充本条线
yy1++;
if (yy1<=2*MAXN)
for (xx=xx1;xx<=xx2;xx++) {//从左往右考查紧挨下面一条线各点
if (n[yy1][xx ]==0) {
ax1=xx-1;
while (1) {//向左找非0点
if (n[yy1][ax1]!=0) break;
ax1--;
}
ax1++;//非0点右边为新扫描线左点
}
if (n[yy1][xx ]==0) {
ax2=xx+1;
while (1) {//向右找非0点
if (n[yy1][ax2]!=0) break;
ax2++;
}
ax2--;//非0点左边为新扫描线右点
// printf("I yy1,ax1,ax2=%d,%d,%d\n",yy1,ax1,ax2);
push(yy1,ax1,ax2);//记录新扫描线到堆栈中
xx=ax2+1;//下次循环从该新扫描线右点的右边开始考查
}
}
}
}
int main() {
scanf("%s",p);
f='S';
y=MAXN;
x=MAXN;
n[y][x]=1;
L=strlen(p);
for (i=0;i<L;i++) {
switch (p[i]) {
case 'f':
switch (f) {
case 'N':y--;n[y][x]=1;break;
case 'S':y++;n[y][x]=1;break;
case 'W':x--;n[y][x]=1;break;
case 'E':x++;n[y][x]=1;break;
}
break;
case 'l':
switch (f) {
case 'N':f='W';break;
case 'S':f='E';break;
case 'W':f='S';break;
case 'E':f='N';break;
}
break;
case 'r':
switch (f) {
case 'N':f='E';break;
case 'S':f='W';break;
case 'W':f='N';break;
case 'E':f='S';break;
}
break;
}
}
// show();
for (y=0;y<2*MAXN+2;y++) {n[y][0]=2;n[y ][2*MAXN+1]=2;}
for (x=0;x<2*MAXN+2;x++) {n[0][x]=2;n[2*MAXN+1][x ]=2;}
// show();
push(1,1,2*MAXN);//从(y1==1,x1==1,x2==2*MAXN)开始
scanlinefill();//往下使用扫描线种子填充算法填充2
// show();
a=0;
for (y=0;y<2*MAXN+1;y++) {
for (x=0;x<2*MAXN+1;x++) {
if (n[y][x]!=2) a++;
}
}
printf("%d\n",a);
return 0;
}
------解决思路----------------------
一个数组保存了N个CRect,即4N个点
够建新数组保存4N个点 (left,top) (left,bottom) (right,top) (right,bottom)
扫描新数组,重复的点删掉(功力够就直接边扫描边加
对新数组按x排序,或按y值排序
------解决思路----------------------
1. 首先把矩形分解成边,遍历所有矩形,把每个矩形的四条边都放到一个边的集合里面. 假设这个边的集合为 A.
2. 遍历 A 里面所有的边, 两两之间进行比较, 如果:
(1) 两条边完全相同, 这把这两条边都从集合 A 中删除.
(2) 如果一条边完全包含了另外一条边, 则把较长的边分解成 左 中 右 三段, 中间那段和较短的那条相同. 从 A 中删除原来的那两条边, 并把 左段和右段 两条新的边加入集合 A 中.
(3) 两条边应该不会出现交叉的.
3. 经过第 2 步处理后, A 中剩下的边已经是一个多边形的外轮廓了, 我们只需要把结果取出来就行:
(1) 取任意一条边, 选任意一个点作为起点, 放入结果数组中. 边另外一个点就是起点的下一个点, 假设为当前点 p.
(2) 从 A 中搜索经过点 p 的边, 把 p 放入结果数组中, 边的另外一个点作为 p 重复该步骤即可.
------解决思路----------------------
1.首先选择一点开始，从该点按照下，右，上，左的方向走
2.从起点向下走，一直走到底，然后以到达的点为起点，以来的时候的方向为参考方向，还是按照逆时针的方向顺次选择前进的方向。
比如第一个图，选择起点，然后向下走到底，到达第二个点，
以这个点为起点，以向上为参考方向，选择向左右，向下走，因为这两个方向都没有路径，所以只能向右走了，
向右一直走到第三个点，以这个点为起点，以向左为参考方向，选择向下走，向右走，都没有路径，于是向上走有路径，走到第四个点。。。一直走下去就会有一个N边形