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:

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

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:

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

1 Like

just add this to your while loop:

stupid +=1

if stupid >â€¦:

break

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

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:

1 Like

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

1 Like