在几何有向图中寻找面 [英] Finding Faces in a Geometric Directed Graph

问题描述

我遇到了一个处理定向几何图形的相当不寻常的问题。想象一下这个图形是国家的边界​​。我正在寻找一种方法来找到脸。我的图由可能形成循环（但不一定）的有向边组成。

我是什么寻找左右脸，以及每个边的左右脸的前辈和后继者。

每张脸都应该是逆时针构造的，意思是一个边的左边总是在里面，右边是在特定的面外。

在一天结束时，面的节点是地理坐标（经纬度）。

这是我正在寻找的信息（从LeftFace开始..）

  + ------ + ------- ------- + + ---------- + ----------- + --------------------- + -------------------- + 
 |边缘| NodeA | NodeB | LeftFace | RightFace | PredecessorLeftFace | SuccessorRightFace | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
 | E1 | P1 | P2 | A | C | E5 | E2 | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
 | E2 | P2 | P3 | A | C | E1 | E6 | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
 | E3 | P3 | P4 | A | B | E2 | E8 | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
 | E4 | P4 | P5 | A | C | E3 | E5 | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
 | E5 | P5 | P1 | A | C | E4 | E1 | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
 | E6 | P3 | P6 | B | C | E3 | E7 | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
 | E7 | P6 | P7 | B | C | E6 | E8 | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
 | E8 | P7 | P4 | B | C | E7 | E4 | 
 + ------ + ------- + ------- + ---------- + ----------- + --------------------- + -------------------- + 
  

解决方案

对于每个有向边添加相对边的图形。对于每个（有向）边缘，在该方向上找到脸部。这意味着，遍历面的边，以便在每个顶点选择最左边的相邻边，直到路径返回到起始顶点。要选择最左边，需要顶点的2D位置。

选择最左边的示例：从P3到P4（与E3相反） 。在P4中，有两种可能性来继续路径P5和P7。现在检查边缘左侧的角度。 P3-P4-P5是〜90deg，P3-P4-P7是〜270deg。角度P3-P4-P5小于P3-P4-P7，所以路径中的下一个边缘是E4，路径中的下一个点是P5。

算法： p>

 对于每个有向边添加相反边
虽然图中有边
选择一个有向边
从边上开始寻找包含面的边（在左边）
将面添加到面的列表
从图中删除面的边
  

I'm confronted with a rather unusual problem dealing with an directed geometric graph. Imagine the graph being borders of countries. I'm looking for a way to find the faces. My graph consists of directed edges which may form cycles (but not necessarily).

What I am looking for are the left and right faces as well as the predecessors and successors of the left and right faces for each edge.

Each face should be constructed anti-clockwise, meaning that the left face of an edge is always inside and the right face is outside of the specific face.

At the end of the day the nodes of the faces are geographic coordinates (lat and lon).

This is the information I am looking for (beginning from LeftFace..)

+------+-------+-------+----------+-----------+---------------------+--------------------+
| Edge | NodeA | NodeB | LeftFace | RightFace | PredecessorLeftFace | SuccessorRightFace | 
+------+-------+-------+----------+-----------+---------------------+--------------------+
| E1   | P1    | P2    | A        | C         | E5                  | E2                 | 
+------+-------+-------+----------+-----------+---------------------+--------------------+
| E2   | P2    | P3    | A        | C         | E1                  | E6                 | 
+------+-------+-------+----------+-----------+---------------------+--------------------+
| E3   | P3    | P4    | A        | B         | E2                  | E8                 | 
+------+-------+-------+----------+-----------+---------------------+--------------------+
| E4   | P4    | P5    | A        | C         | E3                  | E5                 | 
+------+-------+-------+----------+-----------+---------------------+--------------------+
| E5   | P5    | P1    | A        | C         | E4                  | E1                 | 
+------+-------+-------+----------+-----------+---------------------+--------------------+
| E6   | P3    | P6    | B        | C         | E3                  | E7                 | 
+------+-------+-------+----------+-----------+---------------------+--------------------+
| E7   | P6    | P7    | B        | C         | E6                  | E8                 | 
+------+-------+-------+----------+-----------+---------------------+--------------------+
| E8   | P7    | P4    | B        | C         | E7                  | E4                 | 
+------+-------+-------+----------+-----------+---------------------+--------------------+

解决方案

For each directed edge add also opposite edge in a graph. Than, for each (directed) edge find face in that direction. That means, traverse face edges so that in every vertex choose leftmost neighboring edge, until path returns to starting vertex. To choose leftmost edge, 2D positions of vertices are needed.

Example of choosing leftmost edge: going from P3 to P4 (opposite of E3). In P4 there are two possibilities to continue path, P5 and P7. Now check angles on the left side of edges. P3-P4-P5 is ~90deg, and P3-P4-P7 is ~270deg. Angle P3-P4-P5 is smaller than P3-P4-P7, so next edge in path is E4, and next point in path is P5.

Algorithm:

For each directed edge add opposite edge
While there are edges in graph
  Choose one directed edge
  Find edges that enclose face (on left side) starting from that edge
  Add face to list of faces
  Remove face edges from graph

这篇关于在几何有向图中寻找面的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！