earcut 是一个极小且极快的三角剖分库,它可以剖分二维图形、三维图形、无孔图形、有孔图形。
本项目使用 three.js
来可视化了 earcut
的剖分效果,你可以通过依次执行下述命令来启动一个开发服务器,并查看到上述的剖分结果:
npm install
npm run start
你可以在
source/index.js
中找到所有源代码。
剖分二维无孔图形:
const positions = [ 0,0, 1,0, 1,1, 0,1 ];
earcut( positions, undefined, 2 ); // return [ 2, 3, 0, 0, 1, 2 ]
剖分三维无孔图形:
const positions = [ 0,0,0, 1,0,0, 1,1,0, 0,1,0 ];
earcut( positions, undefined, 3 ); // return [ 2, 3, 0, 0, 1, 2 ]
剖分二维有孔图形:
const positions = [
0,0, 6,0, 6,3, 0,3, // 轮廓的顶点,建议按逆时针顺序来提供
1,1, 1,2, 2,2, 2,1, // 孔1的顶点,建议按顺时针顺序来提供
4,1, 4,2, 5,2, 5,1, // 孔2的顶点,建议按顺时针顺序来提供
];
const holes = [ 4, 8 ]; // 表示4~7号顶点为孔1,8~11号顶点为孔2
earcut( positions, holes, 2 ); // return [ 7, 8, 9, 11, 4, 0, 3, 0, 4, 6, 7, 9, 11, 0, 1, 3, 4, 5, 10, 11, 1, 2, 3, 5, 10, 1, 2, 2, 5, 6, 9, 10, 2, 2, 6, 9 ]
剖分三维有孔图形:
const positions = [
0,0,0, 6,0,0, 6,3,0, 0,3,0, // 轮廓的顶点,建议按逆时针顺序来提供
1,1,0, 1,2,0, 2,2,0, 2,1,0, // 孔1的顶点,建议按顺时针顺序来提供
4,1,0, 4,2,0, 5,2,0, 5,1,0, // 孔2的顶点,建议按顺时针顺序来提供
];
const holes = [ 4, 8 ]; // 表示4~7号顶点为孔1,8~11号顶点为孔2
earcut( positions, holes, 3 ); // return [ 7, 8, 9, 11, 4, 0, 3, 0, 4, 6, 7, 9, 11, 0, 1, 3, 4, 5, 10, 11, 1, 2, 3, 5, 10, 1, 2, 2, 5, 6, 9, 10, 2, 2, 6, 9 ]
关于轮廓和孔的顶点的顺序:我推荐你按逆时针顺序来提供轮廓的顶点,按顺时针的顺序来提供孔的顶点,因为这符合 GeoJSON 规范 对
Polygon
的定义。不过,哪怕你不遵循这种做法,earcut
也能正确的剖分多边形。
有时候,earcut
的剖分结果是一个空数组 []
,我把这种情况称之为剖分失灵。而我们只会在剖分三维图形时,才会遇到剖分失灵的情况。
要明白剖分失灵的原因,就必须先阐述清楚 earcut
剖分三维图形的原理,其原理为:将三维图形的 XYZ 坐标投影至 XY 平面,然后就可以把三维图形当成二维图形来进行剖分。
如果三维图形的所有顶点都刚好投影在 XY 平面上的一条直线上,那么就会触发剖分失灵。比如下例中的 positions_2
的顶点就都被投影到了 X 轴上,然后就出发了剖分失灵。
const positions_1 = [ 0,0,0, 1,2,0, 2,0,0 ];
const positions_2 = [ 0,0,0, 1,0,2, 2,0,0 ];
earcut( positions_1, undefined, 3 ); // return [ 1, 0, 2 ]
earcut( positions_2, undefined, 3 ); // return []
你可以通过阅读这个 issue#151 来获得更多信息。
我推荐你阅读 GeoJSON 规范,因为它详细阐述了带孔多边形的数据结构,下面总结一些你可能需要的关于 GeoJSON 规范的知识:
Polygon
的coordinates
是一个数组,它拥有零至多个linear ring
。其中第一个linear ring
代表多边形的轮廓,其内的顶点以逆时针方向进行排序,剩余的linear ring
都代表多边形的孔,其内的顶点以顺时针方向进行排序。linear ring
是一个数组,它拥有至少四个position
。其中首position
和尾position
必须相同,因为linear ring
是一个封闭的图形。position
是一个数组,用于存储坐标,比如[103, 20]
。
本项目遵循 MIT 协议。