How to order a list of curves. Ideas?

Could anyone suggest an algorithm to arrange a set of curves where each curve is intersected only by two others in that list. I need to order this list like this:

image

even if drag-selecting them or selecting in scrambled order.

Not sure but my logic would be:
Pick one curve,
Find intersection with the rest
Gives two resulting curves,
Pick one of them and repeat, this gives you again two intersections but this time with curve 0 and another. Pick the other
Repeat → gives intersection with curve 1 and another. Etc.

1 Like

How many curves per operation? How many operations?

in fact if you remove the intersected curve from the list each time then only one intersection will be found each time - the one you are looking for.

1 Like

not if you select the curves randomly you won’t

This is what I have so far:

############################
### ORDER LIST OF CURVES ###
############################
import System
import rhinoscriptsyntax as rs
import scriptcontext as sc
import Rhino
import time

tol = sc.doc.ModelAbsoluteTolerance

def order_curves(curves_ids = None):
    
    if curves_ids == None:
        curves_ids = rs.GetObjects("get curves: ",rs.filter.curve)
        if curves_ids == None:return
    curves = [rs.coercecurve(id) for id in curves_ids if id is not None]
    
    tmp_curve_list = []
    
    for i in range(-1,len(curves)-1):
        #print curves[i]
        curve_0 = curves[i-1]
        curve_1 = curves[i]
        curve_2 = curves[i+1]
        
        if not curve_0 or not curve_1 or not curve_2: return
        
        # Calculate the intersection
        intersection_tolerance = tol
        overlap_tolerance = 0.0
        insect_event_01 = Rhino.Geometry.Intersect.Intersection.CurveCurve(curve_0, curve_1, intersection_tolerance, overlap_tolerance)
        insect_event_12 = Rhino.Geometry.Intersect.Intersection.CurveCurve(curve_1, curve_2, intersection_tolerance, overlap_tolerance)
        if insect_event_01.Count == 1:
            if curve_0 not in tmp_curve_list:
                tmp_curve_list.append(curve_0)
        #print tmp_curve_list
        #print len(tmp_curve_list)
        rs.AddTextDot(i,curve_1.PointAt(curve_1.Domain[1]*0.5))


if __name__ == "__main__":
    ts = time.time()
    #rs.EnableRedraw(False)
    
    order_curves()
    
    print "Elapsed time is {:.2f}".format(time.time()-ts)

If the time taken is significant then you could wrap your logic in a while curves: loop, use curves.pop() to get the first curve, then search for an intersection, remove that curve, repeat until there are no more curves, your while loop exits…

This avoids searching the whole list multiple times

1 Like

good idea @Dancergraham, thanks,

I’ll try it out, hope I won’t crash rhino with the while loop :crazy_face:

1 Like

just add this to your while loop:

stupid +=1
if stupid >…:
break
:slight_smile:

2 Likes

This seems to work:

############################
### ORDER LIST OF CURVES ###
############################
import System
import rhinoscriptsyntax as rs
import scriptcontext as sc
import Rhino
import time

tol = sc.doc.ModelAbsoluteTolerance

def order_curves_gk(curves_ids = None):
    
    intersection_tolerance = tol
    overlap_tolerance = 0.0
    
    curves = [rs.coercecurve(id) for id in curves_ids if id is not None]
    curve0 = curves.pop()
    rs.AddTextDot(0,curve0.PointAt(curve0.Domain[1]*0.5))
    index = 0
    
    while curves:
        for i, curve1 in enumerate(curves):
            insect_event = Rhino.Geometry.Intersect.Intersection.CurveCurve(curve0, curve1, intersection_tolerance, overlap_tolerance)
            if insect_event.Count:
                index += 1
                rs.AddTextDot(index,curve1.PointAt(curve1.Domain[1]*0.5))
                curve0 = curves.pop(i)
                
                break



if __name__ == "__main__":
    curves_ids = rs.GetObjects("get curves: ",rs.filter.curve)
    
    ts = time.time()
    #rs.EnableRedraw(False)
    
    order_curves_gk(curves_ids)
    
    print "Elapsed time is {:.2f}".format(time.time()-ts)
2 Likes

Thanks @Dancergraham, that’s awesome :slight_smile:

Another alternative. Not the most elegant but seems to work here and is OOPy-ish:

import Rhino as R
import rhinoscriptsyntax as rs
import scriptcontext as sc


class Link:
    def __init__(self, guid):
        self.guid = guid
        self.curve = rs.coercecurve(self.guid)
        self.links = []
        self.index = None
        
    def find_links(self, others):
        for link in others:
            if not link == self:
                isect = R.Geometry.Intersect.Intersection.CurveCurve(self.curve, link.curve, sc.doc.ModelAbsoluteTolerance, sc.doc.ModelAbsoluteTolerance)
                if isect:
                    self.links.append(link)
                    
    def make_label(self, label):
        label = R.Geometry.TextDot(label, self.curve.PointAtNormalizedLength(0.5))
        sc.doc.Objects.AddTextDot(label)


class Chain:
    def __init__(self):
        self.links = []
        self.ordered = []
        
    def make_links(self):
        guids = rs.GetObjects('select curves')
        for guid in guids:
            self.links.append(Link(guid))
            
        print('{} links created'.format(len(self.links)))
        
    def find_connected_links(self):
        for link in self.links:
            link.find_links(self.links)
            if len(link.links) < 1:
                print('link not connected')
                
    def order_links(self):
        self.orderd = []
        for i, link in enumerate(self.links):
            if i == 0:
                link.index = i
                self.ordered.append(link)
                continue
            last = self.ordered[i-1]
            for link in last.links:
                if not link in self.ordered:
                    link.index = i
                    self.ordered.append(link)
                    break
    
    def make_text_dots(self):
        for link in self.links:
            link.make_label(link.index)
            

chain = Chain()
chain.make_links()
chain.find_connected_links()
chain.order_links()
chain.make_text_dots()

Plenty of room for improvement and error checking (end links, not connected…). If a large number of curves then maybe use an r-tree to prune the intersection searches.

output:

image

1 Like

that’s a wonderful learning example @nathancoatney, not just about curve list order but python too, thanks for sharing.

1 Like