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