1

我有一张带有许多直线的 2D 绘图。所有这些线在数学上都是已知的。他们独立于其他人。

您可以考虑我知道每条线的起点和终点，我可以使它们相交以找到所有交点。（详细地说，它们在 Autocad 中，但我只能通过代码工作。所以，我想要一个算法而不是 Autocad 解决方案，尽管也欢迎 Autocad 解决方案）。

问题是：给定一个点（任何地方），我想找到包含它的较小多边形。该多边形将由最近的线形成。

细节：

我没有声明的多边形。只是线条。任意数量的行，任意大小，任意位置。和一个给定的点。

这些线可能形成一个多边形，多或无。因此，多边形的外观没有规则。任意数量的边，没有规律性。（形成多边形的点是通过与线相交来找到的。线是有限的，如果它们不相交，它们就不会形成多边形。）

我的答案是包含给定点的最小多边形。

4

2 回答 2

2

好的，我一直在思考这个问题，我制定了一个回溯算法，我相信它会起作用。这个想法是您将尝试以逆时针方式构建多边形。我们将设置问题，使我们找到的第一个多边形是最小的。这样，我们就不必找到所有这些。

算法：

  1. 按照线段与目标点的接近程度对线段进行排序。
    • 从今以后，每当您需要遍历这些行时，请按此排序顺序遍历它们
    • 在计算与目标点的距离时，将线段视为无限线。 点/线距离
  2. 使用最近的线段执行步骤 3，使用沿“逆时针”方向的线 的第二个交点
    • 以“逆时针”表示将目标点置于直线左侧的方向。
    • 注意：第一个交叉点希望是我们在目标点周围工作后最终到达的地方

  3. 在新发现的线路上...

    A. 遍历所有其他不属于您正在构建的形状的线，找到它们与这条线
    的交点 B. 相对于目标点逆时针排序交点。
    逆时针排序

  4. 在当前行逆时针找到下一个交点。如果这是我们在这条线上检查的第一个点，那么“下一个”点就是将我们带到这条线的交点之后的那个点。

    A. 如果没有这样的点（这可能意味着我们已经检查了当前行上的所有点），那么当前的候选解决方案是不可行的......

    • 回到上一行并对该行的下一个点重复步骤 4 。
    • 如果没有上一行（即，您在开始形状的行上），则回溯并使用下一个最近的行执行第 2 步，开始一个新形状。

    B. 如果形成交点的线的左侧没有目标点（逆时针方向），那么它将形成的多边形不会包围目标点。 对当前行及其下一个点重复步骤 4 。
    C. 如果形成交点的线是你开始的那条线，那么我们找到了解决方案
    D. 如果以上都不成立，对形成交点的线执行步骤 3 。

优化：

  1. 如果少于 3 行，则没有解决方案。不要做任何工作。
  2. 您可能希望在找到交叉点时缓存它们，这样您就不必重新计算它们
    • 如果您选择这样做，我建议使用 2D 数组
  3. 当您知道它们不是解决方案的一部分时，我建议丢弃它们。
    • 示例：如果您已经尝试了最接近目标点的线，但它没有导致解决方案，那么在其他线上查找交点时包含该线是没有意义的。

评论：

  • 该算法将最容易递归实现。
  • 如果目标点位于其中一条线上，您将必须决定该怎么做
于 2013-05-22T15:31:42.597 回答
1

我相信以下算法会起作用：

  1. 如果少于 3 行，则退出。没有解决办法。
  2. 确定离目标点最近的线。这条线保证是解决方案的一部分。
  3. 令 P1 为目标点在 L1 上的垂直投影。
  4. 找到与 L1 最接近且位于 P1 相对两侧的其他线的两个交点。这两点保证是解决方案的一部分。
    • 让我们将这些点称为 P2 和 P3，并将线称为 L2 和 L3
    • 如果没有这些点，就没有解决方案。
  5. 在 L2 和 L3 上分别找到最接近 P2 和 P3 并且与目标点位于 L1 同一侧的最近点。
  6. 重复步骤 4 和 5，直到：
    • 从两个方向找到的线是同一条线
    • 从两个方向找到的交点是同一个点
    • 找不到符合条件的点。这意味着没有解决方案。
于 2013-05-10T22:05:38.207 回答