Creating outlines from lines

Rhino Rhino for Windows
1

Maybe someone had already this issue.
I have a bunch of lines. If needed I can also make a graph where nodes are end points of lines.

What would be an approach to sort them in such a way to create closed cells?

I tried to search for graph methods to find simplest cycles such as topological sort, Tarjan, Johnson algoritms.
But I think they would not work in such cases.

@PeterFotiadis I saw you once on the old thread you did something similar an example how to solve this issue?

Sort
Sort.png1116Ă—752 13.5 KB

3

Hi @Petras_Vestartas I have done this with surfaces in python - it took me a while to find the method!
Could you create surfaces from your lines? Then the process I use is:

import rhinoscriptsyntax as rs

border = rs.DuplicateSurfaceBorder(surf, type = 1)
edges = rs.ExplodeCurves(border, delete_input = True)
pts = []
for edge in edges:
    pts.append(rs.CurveStartPoint(edge))

The key feature is that the edges are automatically sorted in the way you are looking for

4

No, that is the issue that lines have no particular order and try to find those loops

5

@piac’s mesh from lines is now part of Rhino

6

Sorry maybe I did not describe the question well. The thing is that I have bunch of lines that does not form neither a loop, nor are sorted. For instance there 9 lines in a flatten list, but they should form 3 loops.

7

Taking a bunch of curves and running the _PlanarSrf command followed by the _Split command using the original curves as dividers I can get (say 3) surfaces from the curves and then the solution above works for each surface.
It’s a bit hacky making surfaces from the curves and then curves from the surfaces but if it works…?

8

Hi Petras,

CurveBoolean might help…

If that’s not accomplishing what you’re after or you are instead looking for an automated approach using a script or Grasshopper, please post a sample file and change the topic category (e.g. scripting, grasshopper) to get in front of the best people to answer it.

9

Thanks, but in case they are 3D distorted?:

lines
lines.png1266Ă—453 86.4 KB

10

Have you tried MeshFromLines? It detects loops, without needing ordered input.

11

Yap, mesh from lines works, I was thinking it would be only for one cell, but it does work for many,
Thank you. Wondering what is the secret behind that component. :thinking:

12

Hi Petras,

I have lot’s of C# that do various things on graphs … but let’s clarify the issue (speaking having the general case in mind [islands, that is]):

  1. You have a graph (any graph) meaning a bunch of edges (lines or curves) connected with some way.
  2. If the graph yields islands (i.e: they exist collection(s) of nodes not connected with other collection(s)) then you’ll need to cluster the edges first and then compute the VV, VE, EV etc etc connectivity (you’ll need trees with 2 dimensions, obviously) related with the DataTree of edge clusters. For instance this random (proximity) edges collection yields 8 clusters.

Screen%20Shot%20008
Screen%20Shot%200081446Ă—691 452 KB

3. Then the issue of yours is to detect closed cirquits in these clusters using the conn Trees? (I do hope that you have experience with recursion).

13

For instance assume that you have a VV tree from some cluster (for clarity you can extract the sub tree since the main dimension is the cluster index and work with 1 dim conn tree).

Screen%20Shot%20009
Screen Shot 009.JPG1149Ă—635 196 KB

Recursion starts from index 0 on the VV meaning that the VV.Branch(0) contains the neighbors: 5,10,9,12,6. For each of these get the neighbors (i.e. VV.Branch(5), VV.Branch(10), …) and since you work by searching any cirquit both sides mastermind a way to keep track of the 2 way order of indices visited. If at any stage the Lists intersect you subtract the latest common from one of the 2, you reverse it and add the remaing range to the first list (or just reverse it and add all to a HashSet: crude but why bother?): that’s your closed cirquit. If any given neighbor-neighbor List contains 1 item … this means the obvious (orphan/naked node).

Note: if your edges are curves you’ll need an EV conn tree as well in order to sample the pieces into the cirquits.

14

BTW: Closed cirquits is a critical thingy for AEC matters. Anyway that’s from some demo graph made years ago with regard cirquits for my people in the practice (who claim that they understand [In fact, they don’t at all] C#, Recursion and other mysterious things).

Screen%20Shot%20010
Screen%20Shot%200101557Ă—642 337 KB

Notice the 2 conditions for success (N: neighbor, L: List of indices):

  1. Blue Loop3: NL1 intersects with NL2 - you add the common index.
  2. Magenta Loop4: NL2 contains the parent of NL1 (and the other thing) - you add nothing.
1 Like
15

Not sure if this helps, but I believe this formally would be the problem of finding the chordless cycles in a graph. Which, I suppose, is what MeshFromLines solves somehow. I believe the brute force graph approach would be to identify all cycles in the graph (which can be super heavy) and then filter out the ones that aren’t chordless. Anywho, some food for thought/Googling/PhD’ing :nerd_face:

1 Like
16

@DanielPiker once shared this post with a question I asked a while ago:

It may be helpful for you to call @piac 's wb algorithm in script and retrieve the polylines instead of mesh.