怎么从线段集合中查找出闭合线段子集合?求高效算法
如何从线段集合中查找出闭合线段子集合?求高效算法。
二维图形判别问题:
现有给定的线段集合,线段是矢量数据,即每条线段的两个端点坐标都是已知的。需要一个高效的算法,能够找出其中彼此链接而且闭合的线段子集,比如组成的矩形或三角形的线段。
其中线段是用四插树存储的。
请高人给一个高效的查找算法。
------解决方案--------------------
用并查集。
初始时,所有线段各属于一个并查集。然后枚举每两条线段。
if (这两条线段相连)
if (这两条线段属于不同的并查集)
合并这两个并查找集
else
这个公有的并查集的所有或部分(*)线段组成一个线段子集。
在每个并查集里,还要维护线段顺序的列表,这样才能高效完成(*)的操作。
二维图形判别问题:
现有给定的线段集合,线段是矢量数据,即每条线段的两个端点坐标都是已知的。需要一个高效的算法,能够找出其中彼此链接而且闭合的线段子集,比如组成的矩形或三角形的线段。
其中线段是用四插树存储的。
请高人给一个高效的查找算法。
------解决方案--------------------
用并查集。
初始时,所有线段各属于一个并查集。然后枚举每两条线段。
if (这两条线段相连)
if (这两条线段属于不同的并查集)
合并这两个并查找集
else
这个公有的并查集的所有或部分(*)线段组成一个线段子集。
在每个并查集里,还要维护线段顺序的列表,这样才能高效完成(*)的操作。