多重区域Link数量计算公式推导
2015-08-21 本文已影响73人
codemarker
我们知道多重区域内的Field计算公式如下：
假设n为外围顶点数，m为内部点数，则有：
F = 3m + n - 2
那么如何计算多重区域的link数量呢？是否也有公式可循？
下面尝试推导一下。
我们先考虑n=3时的情况，
m=0,l = 3
m=1,l = 6
m=2,l = 9
...
即每增加一个内部点就增加3条link，这个也很容易理解，因为每增加一个内点，其实是在原区域外增加一个顶点，就需要增加3条link。
这时，可以用如下公式计算：
l = 3m + n
因为n=3，则
l = 3m + 3 = 3(m + 1)
我们再考虑外顶点增加的情况：
当n=4时，我们可以把它分解为2个n=3时的情况，然后减1.
当n=5时，我们可以分解为3个n=3时的情况，然后减2.
...
发现n每加1，需要减去的数也加1；同时n与需要减去的数之差为3，也就是说总数需要减去(n-3)个，而这个数正是增加的link数，也就是说要多出n-3个link。
实际上，由任意多个顶点围成的n边形，总能分割成n-2个三角形，而它们共享的边数为(n-2) - 1 = (n - 3)个！
我们将上面两个公式相加，得出：
l = 3m + n + (n - 3) = 3m + 2n - 3
下面我们来验证一下：
n=4,m=0,l = 3
n=4,m=1,l = 8
n=4,m=2,l = 11
n=5,m=0,l = 7
n=5,m=1,l = 10
n=5,m=2,l = 13
...
实际上，n导致的l数变化与m数导致的l数变化是无关的。
看来这个公式是正确的。
这样我们就可以很方便地根据顶点数和内点数计算出多重区域的link数了。
