Closed Curve Intersection Network

I was looking at a post earlier today, which got me thinking about the logic of how to collect intersected curves into discrete, closed cells. This got me looking at this post which led me to the excellent codequotidian blog by Trevor Patt and this post, which uses half-edge mesh data structures to sort curve networks. I've been lucky to closely observe Daniel Piker and Will Pearson as they work their magic with Plankton, so I thought I'd take a look at sets of intersecting curves alone to see if a similar approach could organize them effectively. What I've done is a pretty rough workthrough of examining planar curves, blasting them apart based on intersections, and creating sets of "half-curves"...much like half-edges, but these allow for curves of any type to be used for edges in composing faces. I've only done planar curves because calculating angles is the means by which they are sequenced, but I think it'd be possible to also do this for curves on a surface or mesh, with local planes for calculating angles determined according the surface or mesh normals at each vertex.

No doubt the code's pretty ugly, and there'll be bugs. It definitely likes curves that intersect...I haven't resolved how curves that float alone are treated, or if closed curves lie inside of other closed curves...But in any event, here's the code, have a play if you like...and enjoy!

131111_curve_network.gh

Comment

You need to be a member of Grasshopper to add comments!

Comment by Andy Murray on November 11, 2022 at 11:55pm: Closed Curve Intersection Network is a great way to show how traffic can be controlled on a road. The main reason I like this network is because it allows me to see how many vehicles pass through each intersection. If you have ever been stuck in traffic, then you know that it can take forever to get through a single intersection. Go to employee cards for more useful information. If there are too many cars at an intersection, then it can cause backups and delays for other vehicles. In order to avoid these issues, we need a method of controlling traffic flow at intersections.

Comment by Andy Murray on October 22, 2022 at 4:11am: I think it's a very good idea. I like to see the students have to use their own thinking and come up with their own solutions. I have read some of your other posts and they were really helpful. I would recommend Home Gym Equipment For Kids to buy best home Equipment for kids at cheap prices. I am glad that you are making an effort to share your knowledge with others, even if it is in just short articles like this one. It is important to share knowledge so that others can learn from it and improve their lives as well.

Comment by Brian Ringley on February 12, 2016 at 12:46pm: YOU RULE DAVE

Comment by David Stasiuk on August 17, 2015 at 9:23am: Hi Max-

I can imagine how to do it pretty directly, but I think it might take a little time to implement, and I am not sure that for all networks it's even possible to have a strictly correct distribution of non-intersecting lists. I haven't looked at this code for some time now...but I think the key would be to start with one resulting face, set it to, say, side A, and then set all faces that share a half-curve with the first one to side B, and mark all of the faces as having been "solved and all of those half-curve pairs as having been solved. Then you iterate over all of the "unsolved" half-curves from the ones you've just set to B, setting all unsolved adjacent faces to A. You keep up with this until all faces are set either to A or B.

Comment by Max Malein on August 17, 2015 at 8:24am: Hi David, your code is fantastic!

Do you see any quick way to sort resulting surfaces into two non-intersecting lists? Considering that all intial curves are closed in this case.

Comment by Богдан Кузьміч on November 14, 2013 at 2:50am: Simple test:

VB result in 5 seconds

standard one just freezes and not responding

Like it!

Comment by Pieter Segeren on November 13, 2013 at 1:04pm: Very impressive work david! And thanks for sharing it. Really Cool.

Comment by Arie-Willem de Jongh on November 12, 2013 at 8:27am: David, your the man! Thanks for this, I wrote also a really dirty solution, but it takes ages to compute and only works with polylines.

Thanks for sharing!

Cheers!

Comment by alex.lupascu on November 12, 2013 at 4:27am: Yes, there is definitely a difference in processing time - a fair price to pay though if you can't code :)

thanks

Comment by David Stasiuk on November 12, 2013 at 3:42am: Yes...split surface definitely works, and it's a solution I've used before as well. The primary difference is computational time, really. Splitting a surface gets extremely heavy when you introduce many curves (even with just the few curves in the example definition, splitting curves runs at 868ms versus 18ms for the script...try doing it with a few hundred curves :) ). Likewise, I started this thinking more along the lines of creating regions for curve networks that were near breps/surfaces/meshes...but just threw it together quick last night and kept it in planar space.