algorithm - 多边形填充 |扫描线算法

Question

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

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 填充所有其他以构成新的基础。