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