欧拉公式 V+F-E=2, 对于空间网格,我们很容易验证,比如一个盒子,有 前后左右上下6个面,8个顶点,12条棱,所以8+6-12 = 2
但是平面上的地图式的网格,貌似不符合,例如下面的
这里点有5个,边有6个,面有2个,5+2-6 = 1,不是2啊?
其实看过一些书可以知道,一般把这个面外面的空白区域也算一个面,这样面就有3个
这个网格一般叫planar graph, 一种用途就是子区域划分,就是说只有边和连接信息,就是地图界线,计算
各个省的子区域,由哪些边围起来的,这里还有个机械方面的加工模拟方面的应用,例如车一个圆柱,灰色
的是圆柱的回转截面,蓝色的多边形是车刀走过的区域
最后加工后的回转面就是下面灰色的区域
可能不了解的同学会说,你在画图软件里面画一下不就知道了吗?你上面
不就是在画图软件里面画的,我要是听到这样的问题我基本上没法回答。只能自己去
了解。
我们一般是把这两个轮廓顶点和边编上号
注意两个多边形的顶点要逆时针排序
然后线段和线段求交得到两个多边形的交点,每个交点把相交的线段分割成两个线段
这样就得到一个平面图如下
下面就是每个边变成双向连接边,太密了,画大点,边的编号也不加了
这样,一个点连2条边的现在拓扑上连4条有向边,比如v0,连4条边的拓扑上连8条有向边,比如v9
其实v0意味着是两个环的拐角,v3->v0->v8, v8->v0->v3, v8意味着四个环的拐角
但是怎么判断呢?其实我们上面求v8是有向边 v0->v1 和 v7->v4相交
| v7
v0---v8------->v1
|
\/ v4
必然得到 v0->v8->v7, v7->v8->v1,v1->v8->v4,v4->v8->v0, 反正中间是交点,
前后不在原来的一条直线上的排列组合
同理找v9的四个拐弯,这样我们遍历每个有向边,由于有找到的拐角的指引,就能找出
环,这些环就是子区域,例如从有向边v2-v3开始,到了
v3,拐弯 v2->v3->v0, 下一个是有向边v3->v0, v0,下一个v0->v8, 到了v8,拐弯是
v0->v8->v7, 下一个边是v8->v7, ... v7->v9, ...v9->v2, 最后找回去到v2->v3, 就
得到环 [v2,v3,v0,v8,v7,v9]
遍历过的有向边标记一下,不要再遍历,同样的方法,最后我们找到了所有的环
[v2,v3,v0,v8,v7,v9]
[v9,v7,v8,v1]
[v6,v9,v1,v8,v4,v5]
[v9,v6,v5,v4,v8,v0,v3,v2]
其中最后一个环是逆时针旋转的,通过判断找到的这个环上最右边的拐角v9->v6->v5是个顺时针的,
这个不是错的其实是空白区域的界线,所以实际的子区域是前面三个
v3是卡盘夹的点,刀具扫不到,所以查到只有[v2,v3,v0,v8,v7,v9]包含这个点,也就
求到了最终的圆柱工件被车后的回转面的轮廓,这个轮廓可以用来做动画,计算体积重量,转动惯量
等等后续的模拟。