山寨机中的战斗机！	程序优化工程师到底对IT界有没有贡献

求：面积分割算法

楼主fyje（云中仙）2002-11-12 11:58:56 在专题开发/技术/项目 / 数据结构与算法提问

给定一个由曲线组成的平面S，这个曲面S里面可能包含有小的曲面A，给定一个面积范围C，要将这个曲面S或者曲面之间(S和A之间的区域)的区域分割成数个面积在这个面积范围C内的小区面，请问有什么好的分割算法。
现在有个不太好的算法是这样的，在曲面S和A的内部选一点，向曲面S和A引条直线进行分割。问题点数：100、回复次数：19Top

1 楼zzwu（未名）回复于 2002-11-12 12:40:41 得分 5

实在难懂,先问问:

1. S是曲面还是平面?

2. 曲线如何组成平面S?
Top

2 楼Wugifer（）回复于 2002-11-12 13:03:46 得分 5

有限元法？Top

3 楼fyje（云中仙）回复于 2002-11-12 14:24:56 得分 0

是平面，边界是弯曲的，比如月亮的形状Top

4 楼crazy_lazy_pig（疯狂懒猪）回复于 2002-11-12 23:58:15 得分 5

还是很难懂的，
不过我认为先求出交集，再把交集分割就行了嘛，不管你怎么分，肯定不会超出范围的Top

5 楼fyje（云中仙）回复于 2002-11-13 09:51:11 得分 0

是的，就是想找出一个比较好的分法，如果一个个填充，肯定非常笨的Top

6 楼fyje（云中仙）回复于 2002-11-13 09:53:31 得分 0

是的，就是想找出一个比较好的分法，如果一个个填充，肯定非常笨的Top

7 楼zzwu（未名）回复于 2002-11-13 12:13:16 得分 0

题目意思是否如下:
1.已知平面上由曲线包围的一个区域S, 内部可以有空洞A;
2.要求将区域S(或S-A,当有空洞时)进行划分, 每一块的面积<指定值 C;
Top

8 楼zzwu（未名）回复于 2002-11-13 13:19:44 得分 30

1. 要进行有限元法分析,是要做这一步的.
2. 你所说的用一组射线来划分S或S-A是一种可行方案.但明显的缺点是:
* S形状特殊时较难处理,因为面积难算;
* 如果空洞不只一个,而有几个,射线就难作.
3. 我提供一种可行方案:
a.求出S的最小包围矩形R;
b.将R划分成N*M个同样大小的方格,使它们面积均<C;
c.再求S与各小方格的面积的交,即得.
4. 求交操作有些繁,但不难,不过只是工作量大些而已.
5. 这样的工作我以前为一日本公司做过,它们就是为了进行有限元分析.
6. 上述方法有时也有缺点,如有的块可能很小,所以最好是能加入人工干预划分功能.
Top

9 楼fyje（云中仙）回复于 2002-11-14 10:25:45 得分 0

to zzwu(未名）
分割部分，不但有面积最大值，还有面积最小值的限定，麻烦你帮助想象还有什么好的算法

Top

10 楼Wugifer（）回复于 2002-11-14 13:05:54 得分 10

用 max 表示要求的最大面积，min 表示要求的最小面积。
按 zzwu 的方法，取方格的大小为 max - min 和 min 中较小的一个。
只要选中的方格不足 min，则合并一个相邻的方格，知道超过 min 为止Top

11 楼zhoukun666（我喜欢==〉{ 。}{ 。}）回复于 2002-11-14 18:47:13 得分 10

可以用一种逐步累加的方法，即先确定第一块玻璃，然后在此基础上不断的增加其他块，（这里可搜索算法），直到所有的小玻璃块都得到满足，在这里应该用广度搜索算法求最优解（注意搜索过程中要判断解是否重复）
Top

12 楼zhoukun666（我喜欢==〉{ 。}{ 。}）回复于 2002-11-14 18:47:42 得分 10

也可用动态规划

参考下面这本书P486,元件折叠问题

书名: 数据结构算法与应用-C++语言描述
原书名: Data Structures, Algorithms, and Applications in C++
原出版社 Mcgraw-Hill
作者: Sartej Sahni
译者: 汪诗林等
书号: 7-111-07645-1
页码: 536
定价: ￥49.00
丛书名计算机科学丛书
出版社: 机械工业出版社
出版日期: 2000-1-1

原文如下

15.2.6 元件折叠
在设计电路的过程中，工程师们会采取多种不同的设计风格。其中的两种为位－片设计（bit-slice design）和标准单元设计（standard-cell design）。在前一种方法中，电路首先被设计为
一个元件栈。每个元件Ci 宽为wi ，高为hi ，而元件宽度用片数来表示。线路是按片来连接各元件的，即连线可能连接元件Ci 的第j片到
元件Ci+1 的第j 片。如果某些元件的宽度不足j 片，则这些元件之间不存在片j 的连线。当图1 5 -
10a 的位－片设计作为某一大系统的一部分时，则在V L SI ( Very Large Scale Integrated) 芯片上为
它分配一定数量的空间单元。分配是按空间宽度或高度的限制来完成的。现在的问题便是如何
将元件栈折叠到分配空间中去，以便尽量减小未受限制的尺度（如，若高度限制为H时，必须
折叠栈以尽量减小宽度W）。由于其他尺度不变，因此缩小一个尺度（如W）等价于缩小面积。
可用折线方式来折叠元件栈，在每一折叠点，元件旋转1 8 0°。在图15-10b 的例子中，一
个1 2元件的栈折叠成四个垂直栈，折叠点为C6 , C9 和C1 0。折叠栈的宽度是宽度最大的元件所需
的片数。在图15-10b 中，栈宽各为4，3，2和4。折叠栈的高度等于各栈所有元件高度之和的
最大值。在图15-10b 中栈1的元件高度之和最大，该栈的高度决定了包围所有栈的矩形高度。
实际上，在元件折叠问题中，还需考虑连接两个栈的线路所需的附加空间。如，在图1 5 -
10b 中C5 和C6 间的线路因C6 为折叠点而弯曲。这些线路要求在C5 和C6 之下留有垂直空间，以便
能从栈1连到栈2。令ri 为Ci 是折叠点时所需的高度。栈1所需的高度为
h1+h2+h3++h4+h5+r6，栈2所需高度为h6+h7+h8+r6+r9
在标准单元设计中，电路首先被设计成为具有相同高度的符合线性顺序的元件排列。假设
此线性顺序中的元件为C1，⋯，Cn，下一步元件被折叠成如图1 5 - 11所示的相同宽度的行。在
此图中， 1 2个标准单元折叠成四个等宽行。折叠点是C4，C6 和C11。在相邻标准单元行之间，
使用布线通道来连接不同的行。折叠点决定了所需布线通道的高度。设li 表示当Ci 为折叠点时
所需的通道高度。在图1 5 - 11的例子中，布线通道1的高度为l4，通道2的高度为l6，通道3的高
度为l11。
位－片栈折叠和标准单元折叠都会引出一系列的问题，这些问题可用动态规划方法来解决。
1. 等宽位－片元件折叠
定义r1 = r(n+1) =0。由元件Ci 至Cj 构成的栈的高度要求为
li+l(i+1)+....+ ri+r(j+1) + 1。设一个位－片设计中
所有元件有相同宽度W。首先考察在折叠矩形的高度H给定的情况下，如何缩小其宽度。设Wi
为将元件Ci 到Cn 折叠到高为H的矩形时的最小宽度。若折叠不能实现（如当ri +hi＞H时），取
Wi =∞。注意到W1 可能是所有n 个元件的最佳折叠宽度。
当折叠Ci 到Cn 时，需要确定折叠点。现假定折叠点是按栈左到栈右的顺序来取定的。若
第一点定为Ck+ 1，则Ci 到Ck 在第一个栈中。为了得到最小宽度，从Ck+1 到Cn 的折叠必须用最优
化方法，因此又将用到最优原理，可用动态规划方法来解决此问题。当第一个折叠点k+ 1已知
时，可得到以下公式：
Wi =w+ Wk + 1 （1 5 - 9）
由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足（ 1 5 - 9）式的折
叠点。令h s u m(i,k)=hi+h(i+1)+...+hj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。
根据上述分析，可得到以下动态规划递归式：
Wi=w+min{W(k+1)|hsum(i,k)+ri+r(k+1)<=H,i<=k<=n} (15-10)

这里Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。利用递归式（1 5 - 1 0），可通过递归计算Wn , Wn- 1
⋯, W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的
时间为O (n2 )。通过保留式（1 5 - 1 0）每次所得的k 值，可回溯地计算出各个最优的折叠点，其
时间耗费为O (n)。
现在来考察另外一个有关等宽元件的折叠问题：折叠后矩形的宽度W已知，需要尽量减小
其高度。因每个折叠矩形宽为w，因此折叠后栈的最大数量为s=W / w。令Hi, j 为Ci , ⋯, Cn 折叠成
一宽度为jw 的矩形后的最小高度， H1, s 则是所有元件折叠后的最小高度。当j= 1时，不允许任
何折叠，因此：
Hi,1 =h s u m(i,n) +ri , 1≤i≤n
另外，当i=n 时，仅有一个元件，也不可能折叠，因此：
Hn ,j=hn+rn , 1≤j≤s
在其他情况下，都可以进行元件折叠。如果第一个折叠点为k+ 1，则第一个栈的高度为
h s u m(i,k) +ri +rk+ 1。其他元件必须以至多(j- 1 ) *w 的宽度折叠。为保证该折叠的最优性，其他元件
也需以最小高度进行折叠，即：
Hi,j=max{hsum(i,k)+ri+r(k+1),Hk+1,j-1}

因为第一个折叠点未知，因此必须尝试所有可能的折叠点，然后从中找出一个使式（1 5 - 11）
的右侧取最小值的点，该点成为第一个折叠点。所得递归式为：

Hi,j=min[max{hsum(i,k)+ri+r(k+1),Hk+1,j-1}] i<=k<n

Wi =w+ Wk + 1 （1 5 - 9）
由于不知道第一个折叠点，因此需要尝试所有可行的折叠点，并选择满足（ 1 5 - 9）式的折
叠点。令h s u m(i,k)=
k å
j = i
hj。因k+ 1是一个可行的折叠点，因此h s u m(i, k) +ri +rk+1 一定不会超过H。
根据上述分析，可得到以下动态规划递归式：
这里Wn+1 =0，且在无最优折叠点k+ 1时Wi 为∞。利用递归式（1 5 - 1 0），可通过递归计算Wn , Wn- 1
⋯, W2 , W1 来计算Wi。Wi 的计算需要至多检查n-i+ 1个Wk+ 1，耗时为O (n-k)。因此计算所有Wi 的
时间为O (n2 )。通过保留式（1 5 - 1 0）每次所得的k 值，可回溯地计算出各个最优的折叠点，其
时间耗费为O (n)。
现在来考察另外一个有关等宽元件的折叠问题：折叠后矩形的宽度W已知，需要尽量减小
其高度。因每个折叠矩形宽为w，因此折叠后栈的最大数量为s=W / w。令Hi, j 为Ci , ⋯, Cn 折叠成
一宽度为jw 的矩形后的最小高度， H1, s 则是所有元件折叠后的最小高度。当j= 1时，不允许任
何折叠，因此：
Hi,1 =h s u m(i,n) +ri , 1≤i≤n
另外，当i=n 时，仅有一个元件，也不可能折叠，因此：
Hn ,j=hn+rn , 1≤j≤s
在其他情况下，都可以进行元件折叠。如果第一个折叠点为k+ 1，则第一个栈的高度为
h s u m(i,k) +ri +rk+ 1。其他元件必须以至多(j- 1 ) *w 的宽度折叠。为保证该折叠的最优性，其他元件
也需以最小高度进行折叠，即：
因为第一个折叠点未知，因此必须尝试所有可能的折叠点，然后从中找出一个使式（1 5 - 11）
的右侧取最小值的点，该点成为第一个折叠点。所得递归式为：
可用迭代法来求解Hi, j ( 1≤i≤n, 1≤j≤s)，求解的顺序为：先计算j=2 时的H i, j，再算j= 3，
⋯，以此类推。对应每个j 的Hi, j 的计算时间为O (n2 )，所以计算所有H i, j 的时间为O(s n2 )。通过
保存由（ 1 5 - 1 2）式计算出的每个k 值，可以采用复杂性为O (n) 的回溯过程来确定各个最优的
折叠点。
2. 变宽位－片元件的折叠
首先考察折叠矩形的高度H已定，欲求最小的折叠宽度的情况。令Wi 如式（1 5 - 1 0）所示，
按照与（1 5 - 1 0）式相同的推导过程，可得：
Wi = m i n {w m i n(i, k) +Wk+1 | h s u m(i,k)+ ri +rk+ 1≤H, i≤k≤n} （1 5 - 1 3）
其中Wn+1=0且w m i n(i,k)= m in
i≤j≤k
{wj }。可用与（1 5 - 1 0）式一样的方法求解（1 5 - 1 3）式，所需时间
为O(n2 )。

当折叠宽度W给定时，最小高度折叠可用折半搜索方法对超过O(n2 )个可能值进行搜索来
实现，可能的高度值为h(i,j)+ri +rj + 1。在检测每个高度时，也可用（ 1 5 - 1 3）式来确定该折叠的
宽度是否小于等于W。这种情况下总的时间消耗为O (n2 l o gn)。

3. 标准单元折叠
用wi 定义单元Ci 的宽度。每个单元的高度为h。当标准单元行的宽度W 固定不变时，通过
减少折叠高度，可以相应地减少折叠面积。考察Ci 到Cn 的最小高度折叠。设第一个折叠点是
Cs+ 1。从元件Cs+1 到Cn 的折叠必须使用最小高度，否则，可使用更小的高度来折叠Cs+1 到Cn，从
而得到更小的折叠高度。所以这里仍可使用最优原理和动态规划方法。
令Hi , s 为Ci 到Cn 折叠成宽为W的矩形时的最小高度，其中第一个折叠点为Cs+ 1。令
w s u m(i, s)=w1+w2+...+ws
可假定没有宽度超过W的元件，否则不可能进行折叠。对于Hn,n 因为只有一
个元件，不存在连线问题，因此Hn, n =h。对于H i, s（1≤i＜s≤n）注意到如果w s u m(i, s )＞W，不
可能实现折叠。若w s u m(i,s)≤W，元件Ci 和C j + 1 在相同的标准单元行中，该行下方布线通道的
高度为ls+ 1（定义ln+1 = 0）。因而：
Hi, s = Hi+1, k （1 5 - 1 4）
当i=s＜n 时，第一个标准单元行只包含Ci 。该行的高度为h 且该行下方布线通道的高度为
li+ 1。因Ci+ 1 到Cn 单元的折叠是最优的，可得：
Hi,i=min{Hi+1,k}+l(i+1)+h
i<k<=n

为了寻找最小高度折叠，首先使用式（ 1 5 - 1 4）和（1 5 - 1 5）来确定Hi, s （1≤i≤s≤n）。最
小高度折叠的高度为m in｛H1 , s｝。可以使用回溯过程来确定最小高度折叠中的折叠点。

Top

13 楼zzwu（未名）回复于 2002-11-14 20:12:02 得分 0

最好的办法是人工干预来,即交互式进行划分.
划分后,再自动把所有小块,一块一块地找出其边界,用封闭多边形来表示.
这一工作正是我以前为诶日本人做的.划分小块的工作是日本人自己用AutoCad来完成的,接下来,他们不会做了,由我来解决的.Top

14 楼crazy_lazy_pig（疯狂懒猪）回复于 2002-11-15 23:24:08 得分 5

具体要求到底是什么。我到现在还不知道，是用直线划分还是用曲线，是理论上的还是实际操作上的（或者说，你要划分的平面区域是如何表示的）？
不解答上述问题，我只能告诉你以下结论：
设面积范围c 是区间(a,b) ，待划分区域面积为S ,则：
分割区域数n 满足：
S/b <= n <= S/aTop

15 楼crazy_lazy_pig（疯狂懒猪）回复于 2002-11-15 23:26:51 得分 5

还有一个问题，面积范围c 是怎样的，是否简单如上面的区间，
还是几个区间的并，还是其他更复杂的形式Top

16 楼ny64（海岛）回复于 2002-11-18 17:29:13 得分 5

Good!Top

17 楼fyje（云中仙）回复于 2002-11-18 17:34:39 得分 0

To:lazy_pig:
题目意思如下：
1.已知平面上由曲线包围的一个区域S, 内部可以有空洞A;
2.要求将区域S(或S-A,当有空洞时)进行划分, 每一块的面积<指定值 C，并且大于指定值D;

明白了吗？Top

18 楼fyje（云中仙）回复于 2002-11-18 17:36:23 得分 0

面积范围就是让用户指定一个最大值，一个最小值，把这个面积块分割成形状任意的面积在这个区域的部分Top

19 楼crazy_lazy_pig（疯狂懒猪）回复于 2002-11-19 01:09:50 得分 10

好了，这样回答就清楚多了
再总结一下：
1、面积范围是如我假设的一个区间的形式——最简单的一种。
2、划分面积可以用曲线（因为你有“形状任意的”说法）。

但仍然是很麻烦的，具体表现为两点：
1、若存在一个自然数 n ,使得：S/(n+1) < c < d < S/n ，则无解（不证明了）；
若存在一个自然数 n ，使得：S/c <= n <= S/d ，则有解；
在有解的情况下若c 、d 很接近则很难做到每块面积都符合要求，这种情况下平分最安全。
2、若你是知道边界曲线的方程，要得到划分曲线的具体方程，这就要用到拓扑学的技巧性知识了，说实在的，现在很容易证明这样的划分曲线族是存在的，但是真正找出来恐怕世界上没几个人能做到，尤其边界是不规则曲线。

其实做软件的话，想必你也没要求这么高，能把内存（或磁盘）存贮的图形划分出来就行了，而这样的图形要么是较简单的曲线表示边界，要么是直接像素表示的图形块（如BMP格式图象），这两种都很容易进行平均分化面积，而分化面积数想必你也能很快算出来。对于简单曲线（直线、圆等）你可以容易的找出起均分点，连接这些点就可以了；对于像素表示的图形块你只要按照一定的规则连续的寻找图形中的像素，当所找像素达到均分面积（每个像素可看作面积为1的小块）的要求时即做为一个划分块，继续操作，直到所有的像素找完为止。Top