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