0

示例图

图形

  • 点A : { x : x A ; y : y一个; 邻居：{ B, J } }
  • 点B : { x : x B ; 是：是乙；邻居：{A，C}}
  • 点C : { x : x C ; y : y C ; 邻居：{ B, D, G, H } }
  • 等等

输入

一组顶点（点，笛卡尔坐标系）。

  • 一些顶点与其他顶点相连。
  • 输入上没有边的交点。

问题

如何找到给定点的最近边界（例如绿点 1、2、3 之一）？我只能使用连接的顶点。

  • 第1点的解是 { A, B, C, D, E, F, G, I, J }。
    • （不是{ A, B, D } – { B and D } 和 { D and A } 之间没有边）。
  • 第2点的解是 { C, D, E, F, G }。
  • 第3点的解是 { C, G, H }。

我的想法

找到垂直线（这条线穿过问题点）和边缘（2个顶点之间）的交点。我现在知道2个顶点。怎么继续？？

对于这种情况，我可以使用图论中的任何算法吗？

4

1 回答 1

1

首先，您的想法中存在三个必须处理的极端情况：

  • 垂直线上下相交，必须选其一
  • 垂直线可以与顶点而不是边相交
  • 垂直线可以与同样垂直的边缘相交（因此存在无限个公共点）

这说，

假设您在该点下方找到一条边。所以你找到了 1 个边和 2 个顶点。您可以选择左侧顶点，计算找到的边相对于源自该顶点的每个线段的角度，然后选择角度最小的线段。然后你沿着这条新边找到一个新的顶点，然后迭代。

于 2014-03-20T13:33:48.890 回答