地图区域的边界点按不同方向走一圈,带符号面积会改变正负,但实际覆盖面积不会因此变成负数。用一个矩形挖去上边凹口的例子,可以同时核对边界公式和直观分块。

本篇使用一组可以手算或逐行复查的虚构游戏记录。先读清操作顺序与边界,再看完整过程;它不是某一款现有游戏的隐藏公式,也不要求读者安装工具。

规则与输入

坐标横向右、纵向上,八个顶点组成没有自交的凹多边形。按给定顺序将相邻点的横纵交叉乘积作差并求和,最后除二得到带符号面积;最后一点必须接回第一点。另比较倒序顶点。

八组外框上边带矩形凹口的独立边界,均包含闭合的最后一条边。

逐步计算与结果

第1组外框9×10,凹口宽3、深8,平移[1, -2],顶点[[1, -2], [10, -2], [10, 8], [8, 8], [8, 0], [5, 0], [5, 8], [1, 8]]。逐边交叉差[18, 100, 16, -64, 0, 40, 32, -10],合计132,带符号面积66,倒序为-66,实际面积66。

第2组外框14×11,凹口宽1、深9,平移[4, 5],顶点[[4, 16], [11, 16], [11, 7], [12, 7], [12, 16], [18, 16], [18, 5], [4, 5]]。逐边交叉差[-112, -99, -7, 108, -96, -198, 70, 44],合计-290,带符号面积-145,倒序为145,实际面积145。

第3组外框6×11,凹口宽1、深2,平移[-3, -1],顶点[[-3, -1], [3, -1], [3, 10], [1, 10], [1, 8], [0, 8], [0, 10], [-3, 10]]。逐边交叉差[6, 33, 20, -2, 8, 0, 30, 33],合计128,带符号面积64,倒序为-64,实际面积64。

第4组外框13×12,凹口宽3、深5,平移[-8, 6],顶点[[-8, 18], [1, 18], [1, 13], [4, 13], [4, 18], [5, 18], [5, 6], [-8, 6]]。逐边交叉差[-162, -5, -39, 20, -18, -60, 78, -96],合计-282,带符号面积-141,倒序为141,实际面积141。

第5组外框7×7,凹口宽3、深3,平移[-9, 9],顶点[[-9, 9], [-2, 9], [-2, 16], [-4, 16], [-4, 13], [-7, 13], [-7, 16], [-9, 16]]。逐边交叉差[-63, -14, 32, 12, 39, -21, 32, 63],合计80,带符号面积40,倒序为-40,实际面积40。

第6组外框8×8,凹口宽1、深6,平移[-9, 2],顶点[[-9, 10], [-7, 10], [-7, 4], [-6, 4], [-6, 10], [-1, 10], [-1, 2], [-9, 2]]。逐边交叉差[-20, 42, -4, -36, -50, 8, 16, -72],合计-116,带符号面积-58,倒序为58,实际面积58。

第7组外框7×11,凹口宽1、深6,平移[5, 8],顶点[[5, 19], [8, 19], [8, 13], [9, 13], [9, 19], [12, 19], [12, 8], [5, 8]]。逐边交叉差[-57, -48, -13, 54, -57, -132, 56, 55],合计-142,带符号面积-71,倒序为71,实际面积71。

第8组外框13×7,凹口宽3、深3,平移[3, -9],顶点[[3, -9], [16, -9], [16, -2], [14, -2], [14, -5], [11, -5], [11, -2], [3, -2]]。逐边交叉差[117, 112, -4, -42, -15, 33, -16, -21],合计164,带符号面积82,倒序为-82,实际面积82。

逐组用外框减凹口核验绝对面积,正负只随绕行方向变化,平移不增加或减少覆盖。

怎样独立复核

不使用边界求和,直接用外矩形面积减去凹口矩形面积,应该等于带符号面积绝对值。倒序只改变符号,平移全部点不改变面积;这些是本例的独立交叉检查。

很多图像坐标的纵轴向下,视觉顺逆时针的解释会反过来,应先说明坐标约定。自交边界需要额外定义填充规则,不能直接拿这里的绝对值当作任何复杂路径的覆盖面积。

练习时可以只改变一个输入,再预测哪一步会最先改变。保留中间记录,检查空状态、相等数值和刚好落在边界的情况。最终结果碰巧相同,并不能证明两个过程等价;反过来,采用不同规则得出不同结果,也不应立即视作程序故障。