二维坐标离散化

 

离散化的思想就是将分布大却数量少(即稀疏)的数据进行集中化的处理，这样可以有利于程序的空间与时间，能减少遍历次数与空间储存。

然而虽然我会了思想今天问了翔神半天才知道怎么实现。。

其实实现的方式与口述的角度还是有所不同。

思想理解起来其实道理很简单，如坐标(3，2000)，(10005，31)，(10006，5)离散至新图，先看x坐标，3个点有3，10005，10006，离散后即1，3，4； 3 -> 1，由于10005与3不是连续的两个数故10005 -> 3，又10006与10005是连续的两个数(即相邻)故10006 -> 4，同理看y坐标，3个点有2000，31，5，按上面的思想离散的结果即5 -> 1，31 -> 3，2000 -> 5。离散后三个点坐标为(1，5)，(3，3)，(4，1)

代码实现的方式并不是很简单。先用 结构体or两个数组(这里我用的结构体 node )存下需要离散的点(x,y)，再用一个数组 x[ ]存所有点的x坐标，用数组 y[ ]存所有点的y坐标，为了能按顺序离散以及提高效率，将在数组 x[ ]，y[ ]中加入原图的最小最大值来表示图的边界，然后排序并去重。得到处理后数组长度len1，len2。

设一个tot用来表示新图的下标，然后就for i in len一遍判断前后两个数如果只相差1说明连续，则tot++就可以用一个数组 nx[ ]，ny[ ]存 下一个点，否则可以存一个中间值。这样就得到了一个原坐标与离散坐标的一个映射关系，这种映射关系即nx[ ]，ny[ ]里每个下标与相应值。

在按照这个映射关系将一开始存在node里的x，y用lower_bound(nx，nx+tot，node[ i ].x) - nx得到对应下标，y同理省略，存入新图。

综上离散完毕。

 

附上离散板子

注意最后存的数组ma[][]中的maxn应该是2*点数+5。

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 点数;//这个就是离散完的图的大小
 5 const int maximum = 离散前图的最大边界;
 6 struct Node
 7 {
 8     int x,y;
 9 }node[maxn];
10 int x[maxn], y[maxn];
11 int  nx[maxn], ny[maxn];
12 int m[maxn*2+5][maxn*2+5];
13 void discrete(int n)
14 {
15     int tot1 = 0,tot2 = 0;
16     //x y数组下标从1开始
17     //一般1是图的最小边界，最大边界maximum看题意自己定吧。
18     x[0]=1,x[n+1]=maximum;
19     y[0]=1,y[n+1]=maximum;
20     sort(x,x+n+2);//数组长n+2
21     sort(y,y+n+2);
22     int len1 = unique(x,x+n+2) - x;
23     int len2 = unique(y,y+n+2) - y;
24     //离散x轴
25     for(int i = 0; i < len1;i++)
26     {
27         if(i&&x[i]!=x[i-1]+1)nx[tot1++]=x[i]-1,nx[tot1++]=x[i];
28         else nx[tot1++]=x[i];
29     }
30     //离散y轴
31     for(int i = 0; i < len2;i++)
32     {
33         if(i&&y[i]!=y[i-1]+1)ny[tot2++]=y[i]-1,ny[tot2++]=y[i];
34         else ny[tot2++]=y[i];
35     }
36     //用映射关系将需离散的点放入离散图中
37     for(int i = 0;i < n;i++)
38     {
39         int newx=lower_bound(nx, nx+tot1,node[i].x)-nx;
40         int newy=lower_bound(ny, ny+tot2,node[i].y)-ny;
41         m[newx][newy]=1;
42     }
43 }

View Code