多边形填充 |扫描线算法

Question

我正在用 C++ 和 Win32 API 开发类似 paper.io 的游戏。我的游戏数据存储在如下数组中：

1 = 玩家头像

2 = 玩家基地

3 = 玩家的尾巴

---

1. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,


2. 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 3, 3、3、3、 0、0、0、0、


3. 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0 , 0, 3, 0, 0, 3, 0, 0, 0, 0,


4. 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0、0、3、 0、0、0、0、


5. 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0,


6. 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 0,


7. 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 3, 0,


8. 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0,


9. 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0,


10. 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0,


11. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,

---

现在我想用数字 2（玩家的底座）填充多边形（玩家的尾巴）。

Scan Line Algorithm:

What works:

1. If I scan the 5. line The first 3 trigger the algorithm and toggle the painting function. The next 3 toggles it again it stops the painting function again

问题：

1. If I scan the 2. line After Every 3 the painting function will be toggled and after the line, it will paint further, because it's an odd amount of numbers.

解决方案：

1. Toggle on the transition from zero to non-zero (and non-zero to zero)

Boundary Fill Algorithm:

Problems:

1. I need to find the middle/spot to begin, that's in the polygon

Answer 1

有很多特殊情况使得确定新基地内部和外部区域变得棘手，但这个简单可靠：

1. 从外边缘开始进行填充以找到底部不的区域。此填充可以覆盖除 1、2、3 以外的任何颜色
2. 用颜色 2 填充 其他所有内容 以构成新的基础。