在一个图中寻找面的Java算法

Question

在一个图中寻找面的Java算法

javaalgorithmpolygongraph-theoryplanar-graph

3

我有一个平面图，是我自己创建的。我想找到这个图的面，但我找不到可行的算法来完成这个任务。到目前为止，我使用了一种算法来找到图中的所有循环，但这只给了我所有可能的循环，我尝试过但没有找到一种方法来仅仅将面排序出来。我的一个想法是使用Path2D的contains方法来查看是否有另一个形状重叠，但由于面共享节点，这种方法行不通。下面的图片展示了我想要的内容，代码则展示了我的可重现示例。

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class PolygonFinder {

    //  Graph modeled as list of edges
    static int[][] graph
            = {
                {1, 2}, {1, 6}, {1, 5}, {2, 6},
                {2, 3}, {3, 7}, {7, 4}, {3, 4},
                {5, 4}, {6, 5}
            };

    static List<int[]> cycles = new ArrayList<>();

    /**
     * @param args
     */
    public static void main(String[] args) {

        for (int[] graph1 : graph) {
            for (int j = 0; j < graph1.length; j++) {
                findNewCycles(new int[]{graph1[j]});
            }
        }

        cycles.stream().map(cy -> {
            String s = "" + cy[0];
            for (int i = 1; i < cy.length; i++) {
                s += "," + cy[i];
            }
            return s;
        }).forEachOrdered(s -> {
            System.out.println(s);
        });
    }

    static void findNewCycles(int[] path) {
        int n = path[0];
        int x;
        int[] sub = new int[path.length + 1];

        for (int[] graph1 : graph) {
            for (int y = 0; y <= 1; y++) {
                if (graph1[y] == n) {
                    x = graph1[(y + 1) % 2];
                    if (!visited(x, path)) //  neighbor node not on path yet
                    {
                        sub[0] = x;
                        System.arraycopy(path, 0, sub, 1, path.length);
                        //  explore extended path
                        findNewCycles(sub);
                    } else if ((path.length > 2) && (x == path[path.length - 1])) //  cycle found
                    {
                        int[] p = normalize(path);
                        int[] inv = invert(p);
                        if (isNew(p) && isNew(inv)) {
                            cycles.add(p);
                        }
                    }
                }
            }
        }
    }

    //  check of both arrays have same lengths and contents
    static Boolean equals(int[] a, int[] b) {
        Boolean ret = (a[0] == b[0]) && (a.length == b.length);

        for (int i = 1; ret && (i < a.length); i++) {
            if (a[i] != b[i]) {
                ret = false;
            }
        }

        return ret;
    }

    //  create a path array with reversed order
    static int[] invert(int[] path) {
        int[] p = new int[path.length];

        for (int i = 0; i < path.length; i++) {
            p[i] = path[path.length - 1 - i];
        }

        return normalize(p);
    }

    //  rotate cycle path such that it begins with the smallest node
    static int[] normalize(int[] path) {
        int[] p = new int[path.length];
        int x = smallest(path);
        int n;

        System.arraycopy(path, 0, p, 0, path.length);

        while (p[0] != x) {
            n = p[0];
            System.arraycopy(p, 1, p, 0, p.length - 1);
            p[p.length - 1] = n;
        }

        return p;
    }

    //  compare path against known cycles
    //  return true, iff path is not a known cycle
    static Boolean isNew(int[] path) {
        Boolean ret = true;

        for (int[] p : cycles) {
            if (equals(p, path)) {
                ret = false;
                break;
            }
        }

        return ret;
    }

    //  return the int of the array which is the smallest
    static int smallest(int[] path) {
        int min = path[0];

        for (int p : path) {
            if (p < min) {
                min = p;
            }
        }

        return min;
    }

    //  check if vertex n is contained in path
    static Boolean visited(int n, int[] path) {
        Boolean ret = false;

        for (int p : path) {
            if (p == n) {
                ret = true;
                break;
            }
        }

        return ret;
    }
}

运行上述代码后的结果是：

1,6,2
1,5,6,2
1,5,4,7,3,2
1,6,5,4,7,3,2
1,5,4,3,2
1,6,5,4,3,2
1,5,4,7,3,2,6
1,5,4,3,2,6
1,5,6
2,3,7,4,5,6
2,3,4,5,6
3,4,7

我最好的解决方法之一是使用以下代码。坐标来自顶部的图片。

    List<Polygon> polys = new LinkedList<>();
    Polygon p1 = new Polygon();
    p1.addPoint(new Point2D.Double(-4, 4));
    p1.addPoint(new Point2D.Double(-1, 3));
    p1.addPoint(new Point2D.Double(-1, 5));
    Polygon p2 = new Polygon();
    p2.addPoint(new Point2D.Double(-4, 4));
    p2.addPoint(new Point2D.Double(0, -2));
    p2.addPoint(new Point2D.Double(-1, 3));
    p2.addPoint(new Point2D.Double(-1, 5));
    Polygon p3 = new Polygon();
    p3.addPoint(new Point2D.Double(-4, 4));
    p3.addPoint(new Point2D.Double(0, -2));
    p3.addPoint(new Point2D.Double(4, 1));
    p3.addPoint(new Point2D.Double(2, 2));
    p3.addPoint(new Point2D.Double(3, 4));
    p3.addPoint(new Point2D.Double(-1, 5));
    Polygon p4 = new Polygon();
    p4.addPoint(new Point2D.Double(-4, 4));
    p4.addPoint(new Point2D.Double(-1, 3));
    p4.addPoint(new Point2D.Double(0, -2));
    p4.addPoint(new Point2D.Double(4, 1));
    p4.addPoint(new Point2D.Double(2, 2));
    p4.addPoint(new Point2D.Double(3, 4));
    p4.addPoint(new Point2D.Double(-1, 5));
    Polygon p5 = new Polygon();
    p5.addPoint(new Point2D.Double(-4, 4));
    p5.addPoint(new Point2D.Double(0, -2));
    p5.addPoint(new Point2D.Double(4, 1));
    p5.addPoint(new Point2D.Double(3, 4));
    p5.addPoint(new Point2D.Double(-1, 5));
    Polygon p6 = new Polygon();
    p6.addPoint(new Point2D.Double(-4, 4));
    p6.addPoint(new Point2D.Double(-1, 3));
    p6.addPoint(new Point2D.Double(0, -2));
    p6.addPoint(new Point2D.Double(4, 1));
    p6.addPoint(new Point2D.Double(3, 4));
    p6.addPoint(new Point2D.Double(-1, 5));
    Polygon p7 = new Polygon();
    p7.addPoint(new Point2D.Double(-4, 4));
    p7.addPoint(new Point2D.Double(0, -2));
    p7.addPoint(new Point2D.Double(4, 1));
    p7.addPoint(new Point2D.Double(2, 2));
    p7.addPoint(new Point2D.Double(3, 4));
    p7.addPoint(new Point2D.Double(-1, 5));
    p7.addPoint(new Point2D.Double(-1, 3));
    Polygon p8 = new Polygon();
    p8.addPoint(new Point2D.Double(-4, 4));
    p8.addPoint(new Point2D.Double(0, -2));
    p8.addPoint(new Point2D.Double(4, 1));
    p8.addPoint(new Point2D.Double(3, 4));
    p8.addPoint(new Point2D.Double(-1, 5));
    p8.addPoint(new Point2D.Double(-1, 3));
    Polygon p9 = new Polygon();
    p9.addPoint(new Point2D.Double(-4, 4));
    p9.addPoint(new Point2D.Double(0, -2));
    p9.addPoint(new Point2D.Double(-1, 3));
    Polygon p10 = new Polygon();
    p10.addPoint(new Point2D.Double(-1, 5));
    p10.addPoint(new Point2D.Double(3, 4));
    p10.addPoint(new Point2D.Double(2, 2));
    p10.addPoint(new Point2D.Double(4, 1));
    p10.addPoint(new Point2D.Double(0, -2));
    p10.addPoint(new Point2D.Double(-1, 3));
    Polygon p11 = new Polygon();
    p11.addPoint(new Point2D.Double(-1, 5));
    p11.addPoint(new Point2D.Double(3, 4));
    p11.addPoint(new Point2D.Double(4, 1));
    p11.addPoint(new Point2D.Double(0, -2));
    p11.addPoint(new Point2D.Double(-1, 3));
    Polygon p12 = new Polygon();
    p12.addPoint(new Point2D.Double(3, 4));
    p12.addPoint(new Point2D.Double(4, 1));
    p12.addPoint(new Point2D.Double(2, 2));
    polys.add(p1);
    polys.add(p2);
    polys.add(p3);
    polys.add(p4);
    polys.add(p5);
    polys.add(p6);
    polys.add(p7);
    polys.add(p8);
    polys.add(p9);
    polys.add(p10);
    polys.add(p11);
    polys.add(p12);
    Set<Integer> toRemove = new HashSet<>();
    for (Polygon polyI : polys) {
        for (Polygon polyJ : polys) {
            if (polyI.equals(polyJ)) {
                continue;
            }
            if (polyI.contains(polyJ)) {
                toRemove.add(polys.indexOf(polyI));
            }
        }
    }
    List<Integer> list = new LinkedList<>(toRemove);
    Collections.sort(list);
    Collections.reverse(list);
    list.forEach((t) -> {
        polys.remove(t.intValue());
    });

    System.out.println("");
    polys.forEach((t) -> {
        System.out.println(t.getPoints());
    });

多边形方法使用如下所示。

@Override
public boolean contains(Point2D point) {
    return getPath().contains(point);
}

@Override
public boolean contains(IPolygon polygon) {
    List<Point2D> p2Points = polygon.getPoints();
    for (Point2D point : p2Points) {
        if (getPath().contains(point)) {
            if (!points.contains(point)) {
                return true;
            }
        }
    }
    return false;
}

private Path2D getPath() {
    Path2D path = new Path2D.Double();
    path.moveTo(points.get(0).getX(), points.get(0).getY());
    for (int i = 1; i < points.size(); i++) {
        path.lineTo(points.get(i).getX(), points.get(i).getY());
    }
    path.closePath();
    return path;
}

这段代码给出了以下结果，但是不需要第二到第四个。

[Point2D.Double[-4.0, 4.0], Point2D.Double[-1.0, 3.0], Point2D.Double[-1.0, 5.0]]
[Point2D.Double[-4.0, 4.0], Point2D.Double[0.0, -2.0], Point2D.Double[-1.0, 3.0], Point2D.Double[-1.0, 5.0]]
[Point2D.Double[-4.0, 4.0], Point2D.Double[-1.0, 3.0], Point2D.Double[0.0, -2.0], Point2D.Double[4.0, 1.0], Point2D.Double[2.0, 2.0], Point2D.Double[3.0, 4.0], Point2D.Double[-1.0, 5.0]]
[Point2D.Double[-4.0, 4.0], Point2D.Double[0.0, -2.0], Point2D.Double[4.0, 1.0], Point2D.Double[2.0, 2.0], Point2D.Double[3.0, 4.0], Point2D.Double[-1.0, 5.0], Point2D.Double[-1.0, 3.0]]
[Point2D.Double[-4.0, 4.0], Point2D.Double[0.0, -2.0], Point2D.Double[-1.0, 3.0]]
[Point2D.Double[-1.0, 5.0], Point2D.Double[3.0, 4.0], Point2D.Double[2.0, 2.0], Point2D.Double[4.0, 1.0], Point2D.Double[0.0, -2.0], Point2D.Double[-1.0, 3.0]]
[Point2D.Double[3.0, 4.0], Point2D.Double[4.0, 1.0], Point2D.Double[2.0, 2.0]]

- Teh Swish

2

你的问题有点含糊不清。同一个图可以有许多不同的嵌入到平面中，这些嵌入可以有不同的面。例如，如果我们将点7向右移动，直到它穿过从3到4的线，F3就会失去一个顶点。那么...你是想找到特定嵌入到平面中的面吗？还是其他什么？ - meriton

我的图形实际上是嵌入式的，你可以看到每个顶点的坐标。 - Teh Swish

好的。顺便说一下，我看到了图片中的坐标，但也注意到你在第一次尝试解决问题时没有提供坐标，如果你实际上有坐标的话，这似乎很奇怪。这就是为什么我问的原因 :-) 我的回答有帮助吗？ - meriton

我想找到特定嵌入的面孔。我已经可以保证我的图是平面的，并且在平面上有一个嵌入。我还不明白的部分是如何找到它的面孔。我正在尝试在纸上使用一些方法“边排序”，但我不理解...有什么技巧吗？ - Teh Swish

3个回答

1

在仅由直线组成的平面嵌入中，相遇于顶点的面的边必须是该节点所有边中相邻的边。

因此，如果我们有这样的嵌入，并根据它们的方向对每个顶点的边进行排序，我们可以通过在到达的边的右侧立即进入每个顶点来轻松地走遍每个面的周长。

作为一种数据结构，我可能会选择这样的东西：

class Vertex {
    Edge edges;
}

class Edge {
    Vertex source;
    Vertex target;
    Edge reverse; // the same edge, seen from the other end
    Edge next; // forms a circular linked list, sorted in order of direction
}

然后我们可以像这样迭代面的周长：

Edge startingEdge = ...;
Edge currentEdge = startingEdge;
do {
    currentEdge = currentEdge.reverse.next;
} while (currentEdge != startingEdge);

为了根据方向排序边缘，我们可以利用这样一个事实：如果从坐标系原点看，a 在 b 的左侧，则 a x b 为负值。

boolean left(Point2D.Double a, Point2D.Double b) {
    return a.x * b.y - a.y * b.x < 0; 
}

我们可以使用简单的插入排序来按方向对边进行排序（这将足够快，因为平面图具有有限的平均节点度数，所以边列表会很短）。

- meriton

1

对于每条边，取出嵌入图中边的顶点的坐标并使用三角函数计算边的角度。

例如，从 (x₁, y₁) 到 (x₂, y₂) 逆时针测量与正 x 轴的夹角由 Math.atan2(y2-y1,x2-x1) 给出。
对于每个顶点，通过按其角度对边进行排序来创建一个循环边序列。这可以存储为一个数组或者您可以使用循环列表数据结构。
选择一条边，沿着它到达相邻的顶点，然后沿着下一个顺时针方向的边重复跟随边到达下一个顶点，然后是下一个顺时针方向的边，直到回到起始边；然后您找到了该图的一个面。
重复步骤 3，选择未访问过的边或先前相反方向的已访问边，并按同样的顺时针方向沿着它找到下一个面。重复此操作，直到所有边都被访问两次（每个方向一次），然后您找到了所有面。

在Java中，那将是：

import java.awt.geom.Point2D;
import java.awt.Polygon;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.stream.Collectors;
import java.text.MessageFormat;

public class GraphFaces
{
  static class Vertex
  {
    final int index;
    final Point2D point;
    final ArrayList<Edge> outboundEdges = new ArrayList<>();
    
    
    public Vertex( final int index, final Point2D point )
    {
      this.index = index;
      this.point = point;
    }
    
    public void addEdge( final Edge edge )
    {
      this.outboundEdges.add( edge );
    }
    
    public void sortEdges()
    {
      this.outboundEdges.sort((e1,e2)->Double.compare(e1.angle,e2.angle));
      
      Edge prev = this.outboundEdges.get(this.outboundEdges.size() - 1);
      for ( final Edge edge: this.outboundEdges )
      {
        edge.setNextEdge( prev );
        prev = edge;
      }
    }
    
    @Override
    public String toString()
    {
      return Integer.toString(this.index);
      // return MessageFormat.format("({0},{1})",this.point.getX(),this.point.getY());
    }
  }
  
  static class Edge
  {
    final Vertex from;
    final Vertex to;
    final double angle;
    boolean visited = false;
    Edge next = null;
    Edge reverse = null;
    
    public Edge( final Vertex from, final Vertex to )
    {
      this.from = from;
      this.to = to;
      this.angle = Math.atan2(to.point.getY() - from.point.getY(), to.point.getX() - from.point.getX());
      from.addEdge( this );
    }
    
    public Vertex getFrom()
    {
      return this.from;
    }

    public Vertex getTo()
    {
      return this.to;
    }

    public void setNextEdge( final Edge edge )
    {
      this.next = edge;
    }

    public void setReverseEdge( final Edge edge )
    {
      this.reverse = edge;
    }

    @Override
    public String toString()
    {
      return MessageFormat.format("{0} -> {1}", this.from, this.to);
    }
  }

  public static void main(final String[] args)
  {
    final Vertex[] vertices = {
      new Vertex( 1, new Point2D.Double(-4,+4) ),
      new Vertex( 2, new Point2D.Double(-1,+5) ),
      new Vertex( 3, new Point2D.Double(+3,+4) ),
      new Vertex( 4, new Point2D.Double(+4,+1) ),
      new Vertex( 5, new Point2D.Double(+0,-2) ),
      new Vertex( 6, new Point2D.Double(-1,+3) ),
      new Vertex( 7, new Point2D.Double(+2,+2) )
    };
     
    final int[][] graph = {
      {1, 2}, {1, 6}, {1, 5}, {2, 6}, {2, 3}, {3, 7}, {7, 4}, {3, 4}, {5, 4}, {6, 5}
    };
    
    final Edge[] edges = new Edge[2 * graph.length];

    for ( int i = 0; i < graph.length; i++ )
    {
      final Vertex from = vertices[graph[i][0]-1];
      final Vertex to = vertices[graph[i][1]-1];
      edges[2*i] = new Edge( from, to );
      edges[2*i+1] = new Edge( to, from );
      
      edges[2*i].setReverseEdge(edges[2*i+1]);
      edges[2*i+1].setReverseEdge(edges[2*i]);
    }
    
    
    for ( final Vertex vertex: vertices )
    {
      vertex.sortEdges();
    }
    
    final ArrayList<ArrayList<Edge>> faces = new ArrayList<>();
    for ( final Edge edge: edges )
    {
      if ( edge.visited )
      {
        continue;
      }
      final ArrayList<Edge> face = new ArrayList<>();
      faces.add( face );
      Edge e = edge;
      do
      {
        face.add(e);
        e.visited = true;
        e = e.reverse.next;
      }
      while (e != edge);
      
      System.out.println( face.stream().map(Edge::getFrom).collect(Collectors.toList()) );
    }
  }
}

输出：

[1, 2, 3, 4, 5]
[2, 1, 6]
[6, 1, 5]
[2, 6, 5, 4, 7, 3]
[3, 7, 4]

注意：这包括图形的外部面。

或者，如果您想要：测试图形的平面性；生成（双连通）图的所有可能嵌入；以及为其中一个（或多个）嵌入生成循环边顺序，则可以使用博士论文通过路径添加进行平面性测试，其中包括附录中的完整Java源代码。

- MT0

这是我解决问题的方式，你的解释帮助我解决了我遇到的角度排序问题。谢谢！ - Teh Swish

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

这里有一种基于半边思想的面部识别选项。从高层次上说，这种方法的步骤如下：

1. 用有向边（u，v）和（v，u）替换连接两个点u和v的每条边。这些被称为“半边”。 2. 将半边链接在一起，使得一个单独的半边链完美地跟踪平面图的一个面。 3. 沿着这些链行走，以识别平面图的所有面。

视觉上，它看起来像这样。我们将从以下这张图开始:

[图1]

并最终呈现以下这张图：

[图2]

一旦我们有了第二张图，沿着彩色链走可以确定所有的面。

问题是如何确定如何将半边链在一起。基本思想是：我们希望将边连接在一起，以便

所有内部面都有半边顺时针（或逆时针，取决于你来自哪一侧）缠绕，外部面的半边顺时针缠绕。

只要我们能够找到一个方便的策略将这些东西链在一起，我们就可以轻松地粘合半边，以得到我们想要的性质。有很多方法可以做到这一点，但我想专注于通过局部查看每个节点来工作的方法。

想象一下，您有一些节点X，它的邻居是A、B、C和D，如下所示。

[图3]

在这里，我用实线蓝色标记了离开X的半边，在虚线橙色中标记了进入X的半边。

现在，集中精力观察此图表中的出边(X，A)。当我们将所有东西连起来时，一些其他半边(_，X)需要链入(X，A)。它是哪条边？从图片中，我们可以看出它是半边(B，X)，形成部分链(B，X)，(X，A)。

同样地，关注此图中的半边（X，B）。如前所述，当我们将所有半边连接成链时，需要一些方法确定应该在其之前的半边（_，X）。通过检查，我们可以看到它将是（C，X）。

更一般地，注意到：

- 半边(X, A)之前的半边是(B, X)。 - 半边(X, B)之前的半边是(C, X)。 - 半边(X, C)之前的半边是(D, X)。 - 半边(X, D)之前的半边是(A, X)。

看出模式了吗？如果我们按逆时针（顺时针）顺序排列这个节点周围的邻居，那么可以按以下方式找到在边（X，Y）之前的半边：假设Z是节点逆时针方向的下一个邻居，则在边（X，Y）之前的半边是半边（Z，X）。

这为我们提供了一种非常好的策略来将边缘连接成链，并满足我们上面的要求。以下是一些伪代码：

For each node v:
    Get v's neighbors sorted anticlockwise as u_1, u_2, u_3, ..., u_n
    For each half-edge (v, u_i):
        Update half-edge (u_{i+1 mod n}, v) to chain to (v, u_i)

现在，我们已经把所有东西都连接成链了，完成了！

这里有一些技术细节我没有详细解释，需要在编写代码之前解决。例如：

如何逆时针排序节点v的邻居？可以通过使用 Math.atan2(dy, dx) 计算每个邻居相对于v所成的角度，并基于这些值进行排序。
如何跟踪哪个链进入哪个链？如果你只是要识别面，可以创建一个将每个半边与其后面的下一个半边关联起来的 Map<HalfEdge, HalfEdge>。如果您计划将链保留到未来，您可能希望使每个 HalfEdge 成为包含对序列中下一个半边的引用的链表的一部分。
如何从一对节点映射到连接它们之间的半边？这可以通过像从一对节点到半边的映射的 Map 来完成。您还可以构造半边，并让每个半边存储指向另一个方向的半边的指针。

^{来源：我最初从计算机科学Stack Exchange上的相关问题中学习了这个算法，该问题询问如何从线段集合构建双连通边列表 (DECL)。我的贡献在于将算法简化为仅返回识别面所需的链，并添加一些视觉元素以更好地激发概念。}