有一个点列表,我如何找到顺时针顺序？
例如:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
会说它是逆时针(或逆时针,对某些人来说).
我需要一个工作算法来查找无向图中的所有简单循环.我知道成本可能是指数级的并且问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少.
经过长时间的研究(主要是在这里),我仍然没有工作方法.以下是我的搜索摘要:
无向图中的循环 - >仅检测是否存在循环
在无向图中查找多边形 - >非常好的描述,但没有解决方案
在有向图中查找所有循环 - >仅在有向图中查找循环
我发现的唯一一个解决我问题的答案是:
似乎找到一组基本的循环并对它们进行异或可以解决问题.找到一组基本循环很容易,但我不明白如何组合它们以获得图中的所有循环...
如何在无向图中找到所有无弦循环？
例如,给出图表
0 --- 1
| | \
| | \
4 --- 3 - 2
算法应该返回1-2-3和0-1-3-4,但绝不会返回0-1-2-3-4.
(注意:[1]这个问题与平面图中的小周期发现不同,因为图不一定是平面的.[2]我已经阅读了文章生成所有周期,无弦周期和哈密顿周期的原理排除,但我不明白他们在做什么:).[3]我已经尝试过CYPATH,但程序只给出了计数,readme.txt中的算法EnumChordlessPath有很大的拼写错误,而且C代码很乱.[4]我并不想找到任意一组基金会周期.循环基础可以有和弦.)