0

我有 xy 网格，其中点具有整数正坐标。如果它们的 x 和 y 坐标相差小于 2，则这些点是“邻居”——它们只是彼此相邻。

在这个网格中，我找到了包含某个区域的路径。路径中的每个点都与前一个点和下一个点相邻，因此它的排序就像您在封闭区域中行走一样。它也是围绕该封闭区域的最短路径，因此没有来回步骤。封闭区域不需要是凸的，所以当你用一条线连接路径上的两个随机点时，这条线可以完全位于该区域之外。

问题是，我需要在封闭区域中找到至少一个点，即封闭路径中任何点的邻居。

这听起来很容易，但我还没有找到可靠的算法来确定它。

* 对不起，我解释得不够清楚。封闭区域内没有“空白部分”。如果封闭区域中有三个点，则周围的路径是捕获这三个点的最小路径。在这张图片中，红色的路径最短，黑色的路径太长，我不需要检测它们。

围绕点的最短路径显示为红色

4

1 回答 1

1

检查我是否理解问题的观察：

  • 可能没有这样的内部点。
  • 鉴于连续路径点是邻居，连接角将是 45° 的倍数。

基本思想是走路径并跟踪内部和外部邻居。

要确定哪一侧是内部，请沿着路径行走并跟踪累积的转弯角度。最终量将是 360° 或 -360°，这将指示内部在左侧或右侧，具体取决于您定义正角和负角的方式。

在第一次通过期间，还收集路径上点的哈希集，onPathPoints。

  1. 将另外两个哈希集初始化为空：exteriorPoints和possibleInteriorPoints。
  2. 走这条路，对于每个点：
    • 一个。根据路径上前一个点和下一个点的相对位置，将 8 个邻居分类为路径上、内侧或外侧。
    • 湾。对于 中的每个点onPathPoints，忽略它。
    • C。对于内侧和距离为 1 的任何点，返回该点作为结果。
    • d。对于距离 > 1（对角线邻居）的内侧的每个点，将其添加到possibleInteriorPoints.
    • e. 对于外侧和距离为 1 的每个点，将其添加到exteriorPoints.
  3. 在步行结束时，从（设置减法）possibleInteriorPoints中的任何点移除。exteriorPoints将剩余的任何点返回possibleInteriorPoints为内部点。
  4. 否则，没有内部点。

表示位于内部的possibleInteriorPoints对角相邻点，除非路径在原始点和它之间循环（在这种情况下，它将是新路径部分的外部点。

例如在下图中，当访问 (2,2) 并前往 (3,3) 时，内部位于右侧。(3,1) 是一个可能的内点，但稍后在访问 (4,1) 的过程中，(3,1) 被认为是一个外点，因此会从 中删除possibleInteriorPoints。

在此处输入图像描述

从技术上讲，在这个例子中，当访问 (4,3) 并注意到 (4,2) 作为距离 1 处的内部点时，算法会停止。

于 2014-02-02T01:37:19.440 回答