algorithm - 查找二维多边形的封闭点

Question

我正在构建一个游戏，玩家每次移动 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]

Answer 1

我建议 Even-Odd ray casting algorithm.

1. 首先确定用户积分中最高和最低的X&Y。
2. 对于每个 Y，从 minimumX-1 开始扫描到 maximumX+1。
3. 计算您遇到用户点的次数。

注意:如果用户绘制水平线，这会出现一些问题，请阅读 lit 以获取更多信息。