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