|
曾经遇到过一个项目，研发一种高端家具设备：家具设计师给出坐标点，设备按照家具设计师给定的坐标轨迹避开树疤切割出任意多边形的木板并计算出多边形的面积。 例如按照如图所示的轨迹切割板材用于拼接：
这里的要点有两个：1是避开树疤，2是计算多边形的面积。
讲到这里大家是不是认为很easy，只要通过视觉避开树疤利用齐次变换矩阵仿射变换成实际坐标发给PLC就可以了，面积计算通过视觉将像素面积转成实际面积也没有难点。 然而通过多边形顶点坐标计算出多边形面积这个需求是客户在项目接近完结时提出的，当时自己又刚入门不久，开发视觉软件时做的很简单，就单纯识别树疤比对图形后将多边形像素坐标转成实际坐标发送给PLC，没有加入计算面积的功能，重新开发、测试工期无法满足不说，自己心里也没底。 实际工况时，家具设计师脑洞大开拼接多边形图案更有可能是这样的：
那么有没有办法通过PLC来计算任意多边形的面积呢？这里大家可以停下来仔细思考一下。
答案是有的，那就是“鞋带算法”。例如要计算下图坐标系中多边形的面积：
我们先将多边形顶点坐标逆时针依次从上向下排列，最后回到起点，然后将蓝色线连接的坐标相乘减去橙色线连接坐标的乘积，最后做和除2就成功得到了多边形的面积。“鞋带算法”是不是很形象。 算法原理 鞋带算法原理我们可以由三角形面积公式推导出来，一个三角形的面积我们可以看作是一个平行四边形面积的一半，这里的推导并不复杂，大家可自行脑补，这里不再赘述。
第一步：创建两个不定长数组，并将多边形顶点XY坐标分别存入两个不定长数组中。 第二步：获取不定长数组具体长度。 第三步：for循环中获取鞋带乘积并计算多边形面积。
中国古代人们用 “推步聚顶法” 来计算 “妖田（不规则农田）”的面积，其方法是用步长测量出不规则多边形农田的顶点坐标进而计算出面积，这种“推步聚顶法”其实就是高斯“鞋带算法”。 另外鞋带算法可以进一步扩展用来推导三维多面体的体积。 现在“鞋带算法“在计算机视觉、地图测绘、3D建模也有广泛应用。
五、公众号总结：应用与算法的结合，古与今的融通！一个字“牛”！ 作者语：写在最后 随着各类可编程控制器的应用普及，数学算法在工程中的应用越来越重要，小到冒泡排序、二分查找，大到强化学习、深度学习，都离不开各类算法。大家沉浸其中，方知妙用无穷。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ | 
