Grouping curves for paneling

Hey All,

I have an interesting problem I'm trying to wrap my head around. I have a set of lines that intersect with each other forming a curve network. What I'm trying to do is shattering the lines at there intersecting points and then form closed curves for panelisation. The first part I achieved, shattering the curves at there intersecting points.

But the second part seems simple, but is quite a bitch. I assume there needs to be some custom coding done. I was thinking in pseudo code:

1) looping trough the curve pieces one by one

2) find the curves that end/start with the curve from 1

So far so good, but then I'm stuck as in how to select the proper curve to join with the curve from 1 to eventually get a closed curve. I can imagine this has been researched but with meshes. If someone could give me some hints or tips that would be greatly appreciated.

P.S below is an image of what I'm trying to achieve, so basically join curves 6,13,35,40 in one closed curve. join 5,4,34 in a closed curve, 4,33 in a closed curve, 34,41,32,4 in a closed curve etc, etc...

Cheers!

Replies to This Discussion

Permalink Reply by Mateusz Zwierzycki on May 22, 2013 at 8:50pm

I've tried to do that for quite a long time.... but I didn't manage to do it and I couldn't find any paper about it. Formally you can search for "finding cycles in undirected graphs"...

Permalink Reply by Mateusz Zwierzycki on May 22, 2013 at 9:15pm

If your graph is planar, you can try with this solution (wall following maze solver). The planarity is crucial, otherwise there won't be any way to tell which edge is the "rightmost".

Permalink Reply by Arie-Willem de Jongh on May 24, 2013 at 8:55am

Mateusz, I digged some stuff up online and found some interesting arcticles. The problem is that they are really mathematical, I know my fair share of math haha, but they became to much. I understand that most of the time a depth first search (DFS) is needed. This runs trough all the nodes + connections and eventually finds cycles. I found some snippets of code in a python script, it works, the only thing is that it returns all the cycles. And from what i understood I'm looking for the chordless cycles. I think from having all the cycles to the chordless cycles is not that hard, I imagine looping trough all the cycles and check if they have subset of cycles if so delete is not it is the smallest cycle so it is chordless.

Anyway I'll be checking this, Ill keep you posted here is the link to the python script.

Attachments:

UndefinedCylces.gh, 2 KB

Permalink Reply by Jon Mirtschin on May 22, 2013 at 11:39pm

BullAnt has functionality to generate this. One component can shatter the curves at intersections, and another to process the curve network and generate faces.

There's some examples at http://geometrygym.blogspot.com/search/label/Cell or if you can post or email your model I'll assist with applying if you have problems.

Cheers,

Jon

Permalink Reply by Piotr on May 23, 2013 at 1:37am

Hi Arie-Willem

My approach would be:

1. single surface based on input curves (patch?)

2. Splitting it with input curves

3. Extracting edges from resulting surfaces

4. Removing outside element

Not very clever but it may work.

Permalink Reply by Arend on May 23, 2013 at 2:19am

Hee Arie, long time no see. I wrote this definition a while ago, creating a pseudo-curve boolean by first converting it to a surface and then splitting it, perhaps this is of use to you?

Attachments:

Example-pseudo-curve-boolean.gh, 5 KB

Permalink Reply by Arie-Willem de Jongh on May 23, 2013 at 10:46am

Thanks all for your responses in such a short amount of time :) !

Mateusz: Thanks, I'll have a look at that wall following maze algorithm. For now my curves are planar, so sorting them clock/counterclock wize when grouping might work.

John: Thanks I didnt know that geometry gym has this ability, really cool! unfortunatley here in my work i can't install software, so this would have to wait untill I have some time in the weekend so i can check it out on my personal laptop. The image you send has lines as input, does it also work with curves? (deg>3). Also I'm more interested in the way this problem is solved, rather than just getting the result. Could you give maybe a little info on how the component solves this issue?

Piotr: Your solution works indeed, it's kind of a workaround but yes defenitley! Thanks! Like I told john I'm more interested in the algorithm of how this can be solved, rather than getting the result. This issue has been on my mind for some time, and I wanted to know if you guys had some thoughts on this.

Arend: thanks for that def I'll check it out!

Cheers all!

Permalink Reply by Arie-Willem de Jongh on May 31, 2013 at 11:14am

Hey all!,

I found some interesting writing and some usefull scripts, mainly from Code Quotidien, about half mesh edges:

http://codequotidien.wordpress.com/2012/08/15/half-edge-mesh-2/

There is a def there that has an interesting script that sorts the curve network and creates closed loops. When I have some more time ill dig into this script it is quite interesting the approach. For now some eye candy I did to test the possiblities of a comp like this: