也许这是一个 XY 问题，尽管我个人不这么认为……
我们有一个平面无向图。本质上，将多边形分割成多个部分（这是 X :)）。任务是找到简单的（基本的，或者任何不包括其他的循环）循环（阅读 - 这些区域被划分成的区域。
例如，这是一个图表：
处理后，我需要类似向量的向量 - {2,6,11,10}，{6,11,5,7} 等。
我发现了一个类似的问题，但我不明白如何从那里获得我需要的东西。
初始问题：平面上有N个点，在这些点上有N个顶点的所有星形多边形中，找到面积最小的一个。这些区域是可能的星形多边形的核心。如果我找到了它们，那么将它们全部构建并找到合适的将是一项非常简单的任务。该图显示了点集 {1,2,3,4,5} 的内核。
如果您有节点坐标和边列表，您可以这样做：
我们不是形成每条边，而是形成两条弧（有向边），例如 1-8 和 8-1。
让我们以左下角为例。我们逆时针绕外边缘走一圈，选择最右边的出线弧线，这里是1-8-9-3-13-7-6-2-10-12-14-1，删除弧线。
我们从剩余的弧中取出任何弧，围绕第一条边 - 再次选择最右边的传出弧 - 例如，1-14-4-8-1（记住 1-8 不再存在），删除弧。
对剩余的弧重复上述操作。结果应该是
F = E - V + 2面孔（包括外面的面孔）核心图
让我们在凸包内放置一个点（我们称之为核心点）。让我们按围绕该点的角度对集合中的点进行排序。让我们用一条虚线将它们连接起来——我们得到一个星形多边形。让我们找到它的核心（多边形的每条边定义一个半平面；如果它们相交，就会有一个核心）。核心是凸多边形。
当核心点在核心内部移动时，构造的构型不会改变——星形多边形相同，核心也相同。让我们将点带到核心的边缘（配置不变），将其移动通过边缘并无限靠近边缘停止。配置已更改。您需要从旧的星形多边形中删除三个边并在其位置插入其他三个边。再次不同的是：旧多边形的顶点按角度排序。穿过核心的边缘后，两个顶点改变顺序（我们知道它们是哪两个顶点），这会影响（破坏并重新创建）星形多边形的三个边。
使用新的多边形构建新的核心。
让我们将核收集到图中：核是图的顶点，如果两个核具有公共边，则它们通过边连接（当核点移动通过核边时，从第一个核构建第二个核） ）。
该图的边使我们超越了凸包。当穿过这样的核边缘时，核点超出了点集的凸包。在这种情况下，新的核心将是一个空集。我们从图中排除此类边。
我们有一个图和一个顶点。不需要构建整个图；我们有一个在图中搜索相邻顶点（穿过核心边）的过程。这足以使用广度优先搜索来遍历图。在图的每个顶点，星形多边形及其核心都是已知的。
注意：要在图形中移动（构造新的多边形及其内核），不需要内核点。
复杂：
总复杂度n 5 logn。
注意您问题中的图片与此答案中的图表直接相关。图片中的边缘是该答案中图形的核心和顶点。不要对图表感到困惑，有两个不同的图表。你的一个是一幅画，第二个是抽象的，与你的是双重的。
还原性安全数据表
集合中的任何一对点都定义一条直线，该直线被分为点和两条射线之间的线段。我们只对光线感兴趣，并且只对它们与一组点的凸包的相交感兴趣。也就是说，一对点定义零（两个点都在凸包的边界上）或一个（边界上的一个点）或两个线段（两个点都在凸包内部）。
让我们创建一个具有双连接 (DCEL) 的边列表。让我们将凸包的边缘和上述所有线段放入其中。RSDS 定义了平面图。我们固定任何面，选择其中的任何点并围绕它构建一个星形多边形。可以看出，该多边形的核心与所选面重合。
换句话说，RSDS将包含我们需要的核图。让我们绕着它的宽度，计算星星和它们的面积。
RSDS 的成本为O(n 4 )。同时，可以计算所有恒星的面积——“邻近”恒星的面积相差固定的项数。
整体复杂度为四级，但需要配合RSDS。
PS是否可以不完整搜索星星？