我正在建立一个游戏，玩家每次移动1个点，并在他们身后留下一条路径他们不能跨越自己的路径，当路径完成时，我需要捕获所有封闭的点。我没有太多的数学经验来确定我需要看的算法，但我想我需要将形状分解成子矩形，然后在每个子矩形中找到包含的点。
我被指向凸壳算法，经过一段时间的观察，它似乎只找到了一组给定点的凸周长。所以这行不通。
我还没有找到任何算法来解决任何问题，所以如果我在寻找算法的方向来探索，或者可能是一个可以直接解决问题的方向。
由于播放器只能向上/向下/向左/向右移动，并且没有对角线，因此多边形的所有顶点（？）总是直角的。
示例平面：
0 1 2 3 4
0 [x] [x] [x] [ ] [ ]
1 [x] [o] [x] [ ] [ ]
2 [x] [o] [x] [x] [x]
3 [x] [o] [o] [o] [x]
4 [x] [x] [x] [x] [x]
存储点：（在示例平面上标记为“x”）
[
[0,0],
[0,1],
[0,2],
[1,2],
[2,2],
[2,3],
[2,4],
[3,4],
[4,4],
[4,3],
[4,2],
[4,1],
[4,0],
[3,0],
[2,0],
[1,0]
]
目标点：（在示例平面上标记为“o”）
[
[1,1],
[2,1],
[3,1],
[3,2],
[3,3],
]
其他示例平面：
0 1 2 3 4
0 [ ] [x] [x] [x] [ ]
1 [ ] [x] [o] [x] [ ]
2 [x] [x] [o] [x] [x]
3 [x] [o] [o] [o] [x]
4 [x] [x] [x] [x] [x]
0 1 2 3 4
0 [x] [x] [x] [ ] [ ]
1 [x] [o] [x] [ ] [ ]
2 [x] [x] [x] [x] [x]
3 [ ] [x] [o] [o] [x]
4 [ ] [x] [x] [x] [x]
最佳答案
我建议Even-Odd ray casting algorithm.
首先确定用户点的最高和最低x&y。
对于每一个Y，开始从Mimulx-1到Max Muxx + 1的扫描。
计算您遇到用户点的次数。
注意：这有一些问题，如果用户画水平线，阅读照明更多的信息。