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