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