地图区域的边界点按不同方向走一圈,带符号面积会改变正负,但实际覆盖面积不会因此变成负数。用一个矩形挖去上边凹口的例子,可以同时核对边界公式和直观分块。
本篇使用一组可以手算或逐行复查的虚构游戏记录。先读清操作顺序与边界,再看完整过程;它不是某一款现有游戏的隐藏公式,也不要求读者安装工具。
规则与输入
坐标横向右、纵向上,八个顶点组成没有自交的凹多边形。按给定顺序将相邻点的横纵交叉乘积作差并求和,最后除二得到带符号面积;最后一点必须接回第一点。另比较倒序顶点。
八组外框上边带矩形凹口的独立边界,均包含闭合的最后一条边。
逐步计算与结果
第1组外框6×7,凹口宽3、深2,平移[9, -4],顶点[[9, -4], [15, -4], [15, 3], [14, 3], [14, 1], [11, 1], [11, 3], [9, 3]]。逐边交叉差[24, 105, 3, -28, 3, 22, 6, -63],合计72,带符号面积36,倒序为-36,实际面积36。
第2组外框12×10,凹口宽6、深6,平移[0, -2],顶点[[0, 8], [3, 8], [3, 2], [9, 2], [9, 8], [12, 8], [12, -2], [0, -2]]。逐边交叉差[-24, -18, -12, 54, -24, -120, -24, 0],合计-168,带符号面积-84,倒序为84,实际面积84。
第3组外框10×9,凹口宽3、深2,平移[-9, 5],顶点[[-9, 5], [1, 5], [1, 14], [0, 14], [0, 12], [-3, 12], [-3, 14], [-9, 14]]。逐边交叉差[-50, 9, 14, 0, 36, -6, 84, 81],合计168,带符号面积84,倒序为-84,实际面积84。
第4组外框14×5,凹口宽6、深3,平移[4, -5],顶点[[4, 0], [7, 0], [7, -3], [13, -3], [13, 0], [18, 0], [18, -5], [4, -5]]。逐边交叉差[0, -21, 18, 39, 0, -90, -70, 20],合计-104,带符号面积-52,倒序为52,实际面积52。
第5组外框11×8,凹口宽3、深1,平移[-8, -6],顶点[[-8, 2], [-6, 2], [-6, 1], [-3, 1], [-3, 2], [3, 2], [3, -6], [-8, -6]]。逐边交叉差[-4, 6, -3, -3, -12, -24, -66, -64],合计-170,带符号面积-85,倒序为85,实际面积85。
第6组外框13×9,凹口宽3、深4,平移[-1, 3],顶点[[-1, 3], [12, 3], [12, 12], [3, 12], [3, 8], [0, 8], [0, 12], [-1, 12]]。逐边交叉差[-39, 108, 108, -12, 24, 0, 12, 9],合计210,带符号面积105,倒序为-105,实际面积105。
第7组外框11×11,凹口宽2、深5,平移[-5, 6],顶点[[-5, 6], [6, 6], [6, 17], [4, 17], [4, 12], [2, 12], [2, 17], [-5, 17]]。逐边交叉差[-66, 66, 34, -20, 24, 10, 119, 55],合计222,带符号面积111,倒序为-111,实际面积111。
第8组外框10×5,凹口宽4、深2,平移[5, 6],顶点[[5, 6], [15, 6], [15, 11], [12, 11], [12, 9], [8, 9], [8, 11], [5, 11]]。逐边交叉差[-60, 75, 33, -24, 36, 16, 33, -25],合计84,带符号面积42,倒序为-42,实际面积42。
逐组用外框减凹口核验绝对面积,正负只随绕行方向变化,平移不增加或减少覆盖。
怎样独立复核
不使用边界求和,直接用外矩形面积减去凹口矩形面积,应该等于带符号面积绝对值。倒序只改变符号,平移全部点不改变面积;这些是本例的独立交叉检查。
很多图像坐标的纵轴向下,视觉顺逆时针的解释会反过来,应先说明坐标约定。自交边界需要额外定义填充规则,不能直接拿这里的绝对值当作任何复杂路径的覆盖面积。
练习时可以只改变一个输入,再预测哪一步会最先改变。保留中间记录,检查空状态、相等数值和刚好落在边界的情况。最终结果碰巧相同,并不能证明两个过程等价;反过来,采用不同规则得出不同结果,也不应立即视作程序故障。
