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