钻井布局

钻井布局问题

摘要:

问题一：

因为网格的平移可以等价为旧井的坐标的平移，因为网格式对称的且间距为

1个单位，所以只要考虑旧井坐标的向上向右平移，每次移动=0.05个单位，且，每经过一次平移都检验这n个旧井可否被利用，记下可以被利用的旧井数，完成整个平移后，取可以被利用的旧井数最大的一次即为所求。用C++语言编写程序实现上述要求，求得可被利用的旧井数最大为4，分别为2，4，5，10号旧井，此时网格向下平移了0.5个单位，向左平移了0.6个单位。

问题二：

本题中网格不仅可以平移而且可以旋转，先考虑旋转问题，先利用直角坐标系和极坐标系之间的转化关系求出旋转后的坐标，再利用问题一的方法经行平移，同样每经过一次平移都检验这n个旧井可否被利用，记下可以被利用的旧井数，完成整个平移后，再经行旋转，依次下去。当完成整个旋转和平移后取可以被利用的旧井数最大的一次即为所求。用C++语言编写程序实现上述要求，求得可被利用的旧井数最大为6，分别为1，6，7，8，9，11号旧井，此时网格先顺时针旋转44.9度，再向下平移0.25个单位，向左平移0.05个单位。

问题三：

本题中网格同样是可以平移和旋转的，先考虑只平移的问题。因为网格的间距为1个单位所以只要考虑这些旧井坐标的小数部分即可。先通过平移将落入有效域内，其他点只要满足-,-（i=1„n）(其中表示点与离他最近的的网格结点之差)。所以经过平移后只要使得满足-,-（i=1„n）时所有点均在有效区域内。

再加上旋转先求出旧井旋转后的点坐标，即可按照上述平移的思路判断能否均可被利用。综上所述，当使得满足-,-（i=1„n）时所有点均在有效区域内（其中是旋转角度，表示点经过旋转平移后与离他最近的的网格结点之差）

关键字：网格 平移与旋转变换 移动对象的转换 VC++

问题重述：

勘探部门在某地区找矿。初步勘探时期已零散地已在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用很高，如果新设计的井位与原有的井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。因此，应该尽量利用旧井，少打新井，以节约钻探费用。比如钻一口新井的费用为 500 万元，利用旧井资料的费用为 10 万元，则利用一口旧井就 节约 490 万元。

设平面上有 个点 ，其坐标为,=1„n,表示已有的个井位。新布置的井位是一个正方形网格 N 的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格；结点是指纵线和横线的交叉点）。假定每个格子的边长（井位的纵横间距）都是 1个单位（比如 100 米）。整个网格是可以在平面上任意移动的。若一个已知点与某个网格结点的距离不超过给定误差，则认为处的旧井资料可以利用，不必在结点处打新井。

为进行辅助决策，勘探部门要求我们研究如下问题：

1) 假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差的绝对值）及纵向距离（纵坐标之差的绝对值）的最大值。在平面上平行移动网格 N ，使可利用的旧井数尽可能大。是提供数值计算方法，并对下面的数值例子用计算机计算。

2) 在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计算结果。

3）如果有n 口旧井，给出判定这些井均可利用的条件和算法（你可以任意选定一种距离）

数值例子 n =12 个点的坐标如下表所示： i 1 2 3 4 5 6 7 8 9 10 11 12 0.05 1.41 3.00 3.37 3.40 4.72 4.72 5.43 7.57 8.38 8.98 9.50 2.00 3.50 1.50 3.51 5.50 6.42 6.42 4.01 2.01 4.50 3.41 0.80

模型假设：

1.新布置的井位是一个正方形网格 N 的所有结点，假定每个格子的边长（井位的纵横间距）都是 1个单位（比如100米）。

2．网格与坐标系完全的重合。网格的横向，纵向分别与轴轴重合。网格的移动就等同于坐标系的移动。

3. 每个网格结点的两个坐标都是整数。假设网格平面足够大，坐标系的移动可以控制在一个单位网格中，即控制在 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 内, 且只朝坐标轴的正向移动。

4.假定网格的横向和纵向不固定(可以旋转) 的情况视为网格N 的整体旋转。

符号说明

旧井的原始坐标

第i个旧井的原始横坐标 第i个旧井的原始纵坐标 第i个旧井的平移后的横坐标 第i个旧井的平移后的纵坐标

第i个旧井的旋转移动后的横坐标 第i个旧井的旋转移动后的纵坐标

m 坐标系向右移动的0.05个单位的步数

n 坐标系向上移动的0.05个单位的步数 点 与某个网络结点的距离的给定误差

[ ]是对取整，即最接近的整数,举例：[1.01]=1；[-1.99]=-2

模型的分析与建立

对于问题(1)，网格横向纵向是固定的，只在向右和向上的方向上做平移变换向，右移动0到m步，分别被认为是m个状态。每个状态都将旧井坐标进行向上移动0到n步，每移动一步对旧井坐标是否落入有效域中的判断。（共移动步及次判断）

对于问题(2) , 由于网格既可平移, 又可旋转, 故采取分两步走的策略:先旋转再平移。每旋转，作一次完整的单位网格平移，作平移时的设计思想跟问题(1)一样; 作旋转时, 由网格的对称性和无限性, 旋转角满足, 这样可提高计算速度. 由问题(2) 的分析知, 采用欧氏距离, 网格点的有效域为圆域, 但判断旧井是否可用的方法与问题(1) 类似。 当旧井的坐标落入下图所示的有效域中，此旧井为有效的，即可以再次被利用的。判断旧井是否能被利用，就是判断旧井能否落入有效域中。 有效域的解释：

根据旧井坐标的移动模式，对有效域的形状大小作出正确的判断。因为坐标每次的移动为将坐标的移动视为离散的，在离散中寻求连续。大大提高了解决问题的效率。

问题一：网格只做上方右方的平移。有效域为正方形域。如下左图。 问题二：网格做平移和旋转。则有效域为圆域。如下右图

上图中网格间距为1个单位，正方形的边长为2（左右各个单位），圆形区域的半径为个单位。

问题求解

问题一：由题意，网格的移动来检查旧井的可否被利用情况，因为运动是相对的。

即可将网格的移动问题转化为相当于旧井的点的移动。

因为给定的误差为。所以我们可以让

旧井以为单位横向，纵向分别平移。旧井坐标平移前后的关系式为：

网格边长为一个单位长度，由于网格的对称性。我们可以只研究旧井坐标向上或者向右的移动，且范围是0到1个单位长度，每步移动0.05个单位长度。旧井坐标向右移动0到20步，视为20个状态。每个状态中，都将旧井坐标进行向上移动0到20步，每移动一步对旧井坐标是否落入有效域中的判断。（总共移动步数=）

因为规定了两点间的距离为其横向距离（横坐标之差的绝对值）及纵向距离（纵坐标差的绝对值）的最大值。所以旧井坐标是否落入有效域中的检验方法： 且

满足上述条件即可以人为旧井落入有效域内，及认为旧井可以被利用。 综上所述用c语言编写程序算法如下（源代码见附录）:

先将12个旧井点的横坐标存入数组a中，把纵坐标存入数组 b中。建立m为1到20，n为1到20的双重循环进行旧井的平移，每移动一次按照上面的坐标平移公式将新的坐标存入数组aa,bb中。再按照上述检验方法检验该井是否落入有效区域内。若落入则计数变量count+1。将所有的点都比较完后进行判断count是否大于max，若大于则令max=count。最后等到循环完毕后变量max里面的值就是可利用的最大旧井数。 结果及分析：

程序结果为max=4，此时m,n有2组解分别为：

和

当时,说明旧井向右平移了0.6个单位，向上平移了0.45个单位。平移后12个旧井的坐标为：

表一 i 1 2 3 4 5 6 7 8 9 10 11 12 1.10 2.01 3.60 3.97 4.00 5.32 5.32 6.03 8.17 8.98 9.58 10.10 2.45 3.95 1.95 3.96 5.95 6.69 6.69 4.54 2.46 4.95 3.86 1.25 其中黑体字表示该井可以被利用。

当时,说明旧井向右平移了0.6个单位，向上平移了0.5个单位。平移后12个旧井的坐标为：

表二 i 1 2 3 4 5 6 7 8 9 10 11 12 1.10 2.01 3.60 3.97 4.00 5.32 5.32 6.03 8.17 8.98 9.58 10.10 2.50 4.00 2.00 4.01 6.00 6.74 6.74 4.59 2.51 5.00 3.91 1.30 其中黑体字表示该井可以被利用。 因为表格二中的旧井坐标更加接近网格结点，所以取第二组数据。 综上所述：

因为网格的平移与坐标系中旧井坐标的平移是相对的。最终结果为旧井坐标向右平移0.6个单位，向上平移0.5个单位。相当于，网格向左平移0.6个单位，向下平移0.5个单位后，此可以利用的旧井数最大。

问题二：本题中由于网格的横向纵向不固定，所以不仅要考虑平移还要考虑旋转的问题。同样因为运动是相对的，可将网格的平移和旋转问题转化为旧井坐标的平移和旋转。

先考虑旋转问题，对于旋转可以把旧井的直角坐标转化为极坐标来考虑比较简单，转换关系如下：

旋转后该点到原点距离不变，角度增加一定的角度d即可。计算完成后再把极坐标转化为直角坐标经行后续操作。转换关系如下：

对于旋转后的坐标，由问题一的方法做一次完整的平移变换，每经行一次平移计算出落入有效区域内的旧井数，然后再将坐标旋转d,平移计算出落入有效区域内的旧井数，以此类推。由网格的对称性和无限性, 旋转角满足，求出落入有效区域的旧井最大数即为所求。

因为此题是在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，所谓欧式距离就是两点和间的距离h满足,对于此题判定点是否落入有效区域内的检验方法为：

只要满足上面一个当中的一个即可以认为改点落入有效区域内，即可以被利用。

综上所述用c语言编写程序算法如下（源代码见附录）:

先将12个旧井点的横坐标存入数组a中，把纵坐标存入数组 b中。建立为1到90度的循环d取0.1度，把旋转后的点的横纵坐标分别地存入数组aaa和bbb中，再建立m为1到20，n为1到20的双重循环对旋转后的旧井坐标的经行平移，每移动一次将新的坐标存入数组aa,bb中。在欧式距离误差意义下检验该井是否落入有效区域内。若落入则计数变量count+1。将所有的点都比较完后进行

判断count是否大于max，若大于则令max=count。最后等到循环完毕后变量max里面的值就是可利用的最大旧井数。 结果及结果分析：

程序结果为max=6，此时m,n,有3组解分别为：

当时，说明旧井的坐标先旋转44.9度再向上平移0.25个单位。向右平移0.05个单位。变换后的12个点坐标为

表三 i 1 2 3 4 5 6 7 8 9 10 -1.01 -1.42 1.12 -0.04 -1.42 -1.01 -1.01 1.00 3.99 2.81 2.02 3.72 3.43 5.12 6.55 8.00 8.00 6.99 7.02 9.35 其中黑体字表示该井可以被利用。 当时，说明旧井的坐标先旋转45度再向上平移0.25个单位。向右平移0.05个单位。变换后的12个点坐标为

表四 i 1 2 3 4 5 6 7 8 9 10 -1.01 -1.43 1.11 -0.05 -1.43 -1.02 -1.02 0.99 3.98 2.79 2.02 3.72 3.43 5.11 6.54 7.99 7.99 6.99 7.02 9.36 其中黑体字表示该井可以被利用。 当时，说明旧井的坐标先旋转45.1度再向上平移0.25个单位。向右平移0.05个单位。变换后的12个点坐标为

表五 i 1 2 3 4 5 6 7 8 9 10 -1.01 -1.43 1.11 -0.06 -1.45 -1.04 -1.04 0.98 3.97 2.78 2.02 3.72 3.43 5.11 6.54 7.99 7.99 6.99 7.03 9.36 其中黑体字表示该井可以被利用。 将表三，表四，表五中的数据代入下面的等式中

11 12 4.00 6.21 9.00 7.52 11 12 3.99 6.20 9.01 7.53 11 12 3.97 6.19 9.02 7.54 计算，比较三个表格中的计算结果。 表三：=0.036055512 表四：=0.051961524 表五：=0.08660254

由上述数据可以看出表格三中的旧井坐标更加接近网格结点，所以取第三组数据。

综上所述：

因为网格的平移与坐标系中旧井坐标的平移是相对的。最终结果为旧井的坐标先逆时针旋转44.9度，再向上平移0.25个单位，向右平移0.05个单位。

。相当于，网格先顺时针旋转44.9度，再向下平移0.25个单位，向左平移0.05个单位。此变换后可以利用的旧井数最大。

问题三：对于问题三网格同样是可以平移和旋转的，同样，我们可以把网格的平

移和旋转转化为这些旧井坐标的平移和旋转。

先考虑只平移不旋转的方式。假设这n个点的坐标分别为（i=1„n），因为网格间距为1，所以我们可以只考虑这n个点坐标与离他最近的的网格结点之差（当=1.96，=2.03时=-0.04,=0.03），采用有效区域为矩形的方法，我们先用平移的方法让一个点落入有效域内，在求出其余点都落入有效域内的所要满足的条件即可。 假设在有效域内则,则剩下的点只要满足-,-（i=1„n），即说明均落入有效区域内。 即通过平移后只要使得满足-,-（i=1„n）

时所有点均在有效区域内

下面来讨论平移和旋转同时存在的情况。可根据问题二的思想，先旋转再平移看看能否使所有点都落入有效区域内，设旋转角为，则旋转后的坐标为(其中) 同样我们可以只考虑这n个点坐标与离他最近的的网格结点之差，通过平移的方法使在有效域内，即，则剩下的点只要满足-,-（i=1„n），即说明均落入有效区域内。

综上所述，当使得满足-,-（i=1„n）时所有点均在有效区域内

附录： 问题一：

#include #include void main() { double aa[12]={0.50,1.41,3.00,3.37,3.40,4.72,4.72,5.43,7.57,8.38,8.98,9.50}; double bb[12]={2.00,3.50,1.50,3.51,5.50,6.24,6.24,4.10,2.01,4.50,3.41,0.08}; double b[12],a[12]; int m=0; int jj=0; int ii=0; for(int i=0;i<=19;i++) { int n; for(int k=0;k<=11;k++) { a[k]=aa[k]+0.05*i; } for(int j=0;j<=19;j++) { n=0; for(int k=0;k<=11;k++) { b[k]=bb[k]+0.05*j; if(fabs((int) a[k]-a[k])<=0.05&&fabs((int) b[k]-b[k])<=0.05) n++; if(fabs((int) a[k]+1-a[k])<=0.05&&fabs((int) b[k]-b[k])<=0.05) n++; if(fabs((int) a[k]-a[k])<=0.05&&fabs((int) b[k]+1-b[k])<=0.05) n++; if(fabs((int) a[k]+1-a[k])<=0.05&&fabs((int) b[k]+1-b[k])<=0.05)n++; } if(m}

a[k]=aa[k]+ii*0.05; b[k]=bb[k]+jj*0.05; if(fabs((int) a[k]-a[k])<=0.05&&fabs((int) b[k]-b[k])<=0.05) printf(\"%f\\n %f\\n\ if(fabs((int) a[k]+1-a[k])<=0.05&&fabs((int) b[k]-b[k])<=0.05) printf(\"%f\\n %f\\n\ if(fabs((int) a[k]-a[k])<=0.05&&fabs((int) b[k]+1-b[k])<=0.05) printf(\"%f\\n %f\\n\ if(fabs((int) a[k]+1-a[k])<=0.05&&fabs((int) b[k]+1-b[k])<=0.05) printf(\"%f\\n %f\\n\}

printf(\"m= %d\\n\printf(\"jj= %d\\n\printf(\"ii= %d\\n\

运行结果：

续问题一：

#include #include void main() { double aa[12]={0.50,1.41,3.00,3.37,3.40,4.72,4.72,5.43,7.57,8.38,8.98,9.50}; double bb[12]={2.00,3.50,1.50,3.51,5.50,6.24,6.24,4.10,2.01,4.50,3.41,0.08}; double b[12],a[12]; int jj=0; int ii=0;

}

for(int i=0;i<=19;i++) { int n; for(int k=0;k<=11;k++) { a[k]=aa[k]+0.05*i; } for(int j=0;j<=19;j++) { n=0; for(int k=0;k<=11;k++) { b[k]=bb[k]+0.05*j; if(fabs((int) a[k]-a[k])<=0.05&&fabs((int) b[k]-b[k])<=0.05) n++; if(fabs((int) a[k]+1-a[k])<=0.05&&fabs((int) b[k]-b[k])<=0.05) n++; if(fabs((int) a[k]-a[k])<=0.05&&fabs((int) b[k]+1-b[k])<=0.05) n++; if(fabs((int) a[k]+1-a[k])<=0.05&&fabs((int) b[k]+1-b[k])<=0.05)n++; } if(n==4) { jj=j; ii=i; printf(\"jj= %d\\n\ printf(\"ii= %d\\n\ } } }

for(int k=0;k<=11;k++) { a[k]=aa[k]+ii*0.05; b[k]=bb[k]+jj*0.05; if(fabs((int) a[k]-a[k])<=0.05&&fabs((int) b[k]-b[k])<=0.05) printf(\"%f\\n %f\\n\ if(fabs((int) a[k]+1-a[k])<=0.05&&fabs((int) b[k]-b[k])<=0.05) printf(\"%f\\n %f\\n\ if(fabs((int) a[k]-a[k])<=0.05&&fabs((int) b[k]+1-b[k])<=0.05) printf(\"%f\\n %f\\n\ if(fabs((int) a[k]+1-a[k])<=0.05&&fabs((int) b[k]+1-b[k])<=0.05) printf(\"%f\\n %f\\n\}

运行结果：

问题二：

#include #include void main() { double aaa[12]={0.50,1.41,3.00,3.37,3.40,4.72,4.72,5.43,7.57,8.38,8.98,9.50}; double bbb[12]={2.00,3.50,1.50,3.51,5.50,6.24,6.24,4.10,2.01,4.50,3.41,0.80}; double b[12],a[12],aa[12],bb[12]; int m=0; int jj=0; int ii=0; int vv=0; double p,q; for(int v=1;v<=900;v++) { int n; for(int k=0;k<=11;k++) { p=sqrt(aaa[k]*aaa[k]+bbb[k]*bbb[k]); q=atan(bbb[k]/aaa[k])+3.1415926/1800*v; aa[k]=p*cos(q); bb[k]=p*sin(q); } for(int i=0;i<=19;i++) { for(int k=0;k<=11;k++) {

a[k]=aa[k]+0.05*i; } for(int j=0;j<=19;j++) { n=0; for(int k=0;k<=11;k++) { b[k]=bb[k]+0.05*j; if(sqrt(((int) a[k]-a[k])*((int) a[k]-a[k])+((int) b[k]-b[k])*((int) b[k]-b[k]))<=0.05) n++; if(sqrt(((int) b[k]-b[k]))<=0.05) n++; if(sqrt(((int) b[k]+1-b[k]))<=0.05) n++; if(sqrt(((int) b[k]+1-b[k]))<=0.05) n++; } if(n>m) { m=n; jj=j; ii=i; vv=v; } } } } printf(\"m= %d\\n\ printf(\"jj= %d\\n\ printf(\"ii= %d\\n\ printf(\"vv= %d\\n\}

运行结果：

a[k]+1-a[k])*((int) a[k]-a[k])*((int) a[k]+1-a[k])*((int) a[k]+1-a[k])+((int) a[k]-a[k])+((int) a[k]+1-a[k])+((int) b[k]-b[k])*((int) b[k]+1-b[k])*((int) b[k]+1-b[k])*((int)

续问题二：

#include #include void main() { double aaa[12]={0.50,1.41,3.00,3.37,3.40,4.72,4.72,5.43,7.57,8.38,8.98,9.50}; double bbb[12]={2.00,3.50,1.50,3.51,5.50,6.24,6.24,4.10,2.01,4.50,3.41,0.80}; double b[12],a[12],aa[12],bb[12]; int m=0; int jj=0; int ii=0; int vv=0; double p,q; for(int v=1;v<=900;v++) { int n; for(int k=0;k<=11;k++) { p=sqrt(aaa[k]*aaa[k]+bbb[k]*bbb[k]); q=atan(bbb[k]/aaa[k])+3.1415926/1800*v; aa[k]=p*cos(q); bb[k]=p*sin(q); } for(int i=0;i<=19;i++) { for(int k=0;k<=11;k++) { a[k]=aa[k]+0.05*i; } for(int j=0;j<=19;j++) { n=0; for(int k=0;k<=11;k++)

{ b[k]=bb[k]+0.05*j; if(sqrt(((int) a[k]-a[k])*((int) a[k]-a[k])+((int) b[k]-b[k])*((int) b[k]-b[k]))<=0.05) n++; if(sqrt(((int) a[k]+1-a[k])*((int) a[k]+1-a[k])+((int) b[k]-b[k])*((int) b[k]-b[k]))<=0.05) n++; if(sqrt(((int) a[k]-a[k])*((int) a[k]-a[k])+((int) b[k]+1-b[k])*((int) b[k]+1-b[k]))<=0.05) n++; if(sqrt(((int) a[k]+1-a[k])*((int) a[k]+1-a[k])+((int) b[k]+1-b[k])*((int) b[k]+1-b[k]))<=0.05) n++; } if(n==6) { m=n; jj=j; ii=i; vv=v; printf(\"ii= %d\\n\ printf(\"jj= %d\\n\ printf(\"vv= %d\\n\ for(int k=0;k<=11;k++) { if(sqrt(((int) a[k]-a[k])*((int) a[k]-a[k])+((int) b[k]-b[k])*((int) b[k]-b[k]))<=0.05) { printf(\"旋转移动前坐标=%f %f\\n\ printf(\"旋转移动后坐标=%f %f\\n\ } if(sqrt(((int) a[k]+1-a[k])*((int) a[k]+1-a[k])+((int) b[k]-b[k]))<=0.05)

{ printf(\"旋转移动前坐标=%f %f\\n\ printf(\"旋转移动后坐标=%f %f\\n\ } if(sqrt(((int) a[k]-a[k])*((int) a[k]-a[k])+((int) b[k]+1-b[k]))<=0.05)

b[k]-b[k])*((int)

b[k]+1-b[k])*((int)

{printf(\"旋转移动前坐标=%f %f\\n\ printf(\"旋转移动后坐标=%f %f\\n\ if(sqrt(((int) a[k]+1-a[k])*((int) a[k]+1-a[k])+((int) b[k]+1-b[k])*((int) b[k]+1-b[k]))<=0.05) { printf(\"旋转移动前坐标=%f %f\\n\ printf(\"旋转移动后坐标=%f %f\\n\ } }

}

} }

}

}