Sort Curves

unhandled

(David S. Mavrov) #1

Can you suggest any way to sort my initial geometry? Lets say I have a bunch of curves as initial geometry. They can be either in 3D or 2D. What I need is a way to sort the geometry in polygons. They can be 3,4,5,6, etc. sided.

Here is an example geometry:
Sort Curves.gh (19.8 KB)

HS_Kim has suggested the following method, but I can only make it work for plannar geometry, not more complex shapes.


(Pfotiad0) #2

Until some good Samaritan (who plays ball with components) gives you the native components answer … get the attached (in fact 2 lines of code) : it puts polylines in a tree where the branch index equals the N of poly segments. Notify if you need further sorting on the Lists (per length for instance) of some other type of addicional sort/classification/whatever.

Sort Curves_V1.gh (25.9 KB)


(David S. Mavrov) #3

Just noticed that I havent internalized the first input.

Sort Curves.gh (24.7 KB)


(David S. Mavrov) #4

After inputting my original geometry, the result is not at all what I am looking for. The output in the example file is what the result must look like.


(Pfotiad0) #5

You have 40 curves right? They are Polylines with variable N of segments right?

If so the (very simple) thing provided is impossible to fail … beause is just 2 steps:

one question:

Dear polyline how many segments you have?

and one action:

Store polyline in a tree were the branch index equals the N of segments:

Or you actually mean that you want to find how many (primary) closed Cirquits (as is the classic name of that type of Loop) are possible from these polylines (if they are open) and then sort the Cirquits?


(Pfotiad0) #6

BTW: Is this what you are after? If so has nothing to do with Sort and as I said is a special kind of Cluster Analysis (so to speak) called: primary Cirquits


#7

This might not be a solution what you expect, and also not a general solution, though…

Sort Curves_re.gh (26.6 KB)


(qythium) #8

If I understand it correctly, your problem can be expressed in terms of an undirected multigraph where edges are your curves and the nodes are its end points, and you are trying to find the set of non-overlapping shortest cycles which span the entire graph?

It’s unlikely that you could use native components to solve something like this - I think the strategy would be to script some sort of breadth-first traversal of the graph from a given node, which returns the edges that make up the minimal cycle containing that node, and then iteratively remove those edges from the graph until there are none left.


(David S. Mavrov) #9

Looks like it :slight_smile:


(David S. Mavrov) #10

Hi Kim! I will test it as soon as possible.


(Pfotiad0) #11

Well … the issue was the term “Sort”. As the other fellow user stated correctly doing this for any Graph is impossible without code. The delicate point is the classification (not to mention the sear performance) of the code: in this occasion is strictly internal since closed primary cirquits are paramount in quite a few AEC solutions (complex random trusses with large amount of axis and the likes).

I’ll try to figure out a simplistic solution (using 100% code) that can being published here using connectivity trees (like the things that Sandbox does on Line Lists etc etc) taking advantage of the fact that common vertices have valence either 2 or 3,


(qythium) #12

I got curious and decided to implement it in Python after all - This works on your test cases but will probably crash and burn for even slightly ill-conditioned inputs, so be warned!
Sort Curves (1).gh (25.1 KB)

from Queue import Queue
from Grasshopper import DataTree
from Grasshopper.Kernel.Data import GH_Path
from collections import namedtuple

tol = 0.01  # tolerance when comparing end points of a curve


class Node(object):
    def __init__(self, point):
        self.location = point
        self.neighbors = []  # list of tuples (node, edge to that node)

    def add_neighbor(self, neighbor_node, edge):
        self.neighbors.append((neighbor_node, edge))

    def get_minimal_cycle(self, filter_edges):
        # breadth first search to find shortest (number of edges) cycle
        visiting = Queue()
        # keep track of current node, visited nodes and the edges leading up to it
        visiting.put((self, [self], []))

        while not visiting.empty():
            curr_node, visited, path = visiting.get()
            for next_node, next_edge in curr_node.neighbors:
                if not next_edge in filter_edges:
                    continue
                next_path = path + [next_edge]

                if next_node in visited:
                    if next_node == self and len(visited) > 2:
                        # a single edge (2 visited nodes) doesn't count as a cycle
                        return next_path
                    continue

                next_visited = visited + [curr_node]
                visiting.put((next_node, next_visited, next_path))

        raise RuntimeError('Could not find closed cycle')


Edge = namedtuple("Edge", "curve, start_node, end_node")


class Graph(object):
    def __init__(self, curves):
        self.nodes = []
        self.edges = []
        # construct graph
        for crv in curves:
            self.edges.append
            start_pt, end_pt = crv.PointAtStart, crv.PointAtEnd
            start_node, end_node = None, None
            for node in self.nodes:
                # test if end points of curve are already existing nodes
                if start_node is None and node.location.EpsilonEquals(start_pt, tol):
                    start_node = node
                if end_node is None and node.location.EpsilonEquals(end_pt, tol):
                    end_node = node
                if start_node and end_node:
                    break
            if start_node is None:  # create new node
                start_node = Node(start_pt)
                self.nodes.append(start_node)
            if end_node is None:
                end_node = Node(end_pt)
                self.nodes.append(end_node)
            edge = Edge(crv, start_node, end_node)
            start_node.add_neighbor(end_node, edge)
            end_node.add_neighbor(start_node, edge)
            self.edges.append(edge)

    def get_cycles(self):
        result = []
        remaining_edges = set(self.edges)
        while remaining_edges:
            for start_edge in remaining_edges:
                break  # choose random edge
            node = start_edge.start_node  # choose random node
            cycle_edges = node.get_minimal_cycle(remaining_edges)
            remaining_edges.difference_update(cycle_edges)
            result.append([edge.curve for edge in cycle_edges])
        return result


result = Graph(curves).get_cycles()  # input 'curves', type hint: Curve, List Access

tree = DataTree[object]()  # output
for i, cycle in enumerate(result):  # convert nested list to datatree
    tree.AddRange(cycle, GH_Path(i))

(David S. Mavrov) #13

Found a solution. Geometry gym! The ggNetworkPolygons nails it. It will be interesting if I am capable of doing it with no plugin.


(David S. Mavrov) #14

Here is an universal solution. I have tested it in any possible combination and it works. The clever “magical” part is ggNetworkPolygons as I have said. And it is really interesting to know how it is done.


(Tom) #15

I wonder why nobody noticed one important aspect of polygons:
If you walk through a set of curves and you always choose the most left (alt.: most right) lines connected, you always end up at the beginning line, and if not (after x iterations) its no polygon.


(David S. Mavrov) #16

This makes sense. But you would have to trace both in left and right direction and then delete the dublicate polygons, no? Any way to do this without plug-ins?


(Tom) #17

First of all this problem isn’t solvable in 30 minutes. You need much more time in implementing a good and robust algorithm. Without coding I see no chance.

I think qythiums approach points into the right direction. You need a graph, where you sort your lines into neighbouring relations. You also need to filter out already walked lines depending on direction of traversal. Each line can only share one polygon in one direction of traversal.
Left-Right checking only works if a line has 2 neighbours at one end, because you need to make a plane for it. Otherwise it is not determine where left and right is. Left - Right checking works with the dot of a normal (based on that plane) from you line. Assuming your normal is right, if the dot is <0 its left,if 0 its parallel or antiparallel if > 0 its right.


(Pfotiad0) #18

Almost nobody I confess (BTW: drop a word (mail): what’s going on? (and why)) .

But the big thing is the 23.59 factor: when you are tired, out of time and (most importantly) out of cigars/vodka … and you think that there’s CCX Events around whilst they are not. What to do?


(Tom) #19

I actually learned it the hard way, but once I knew the trick, my life (and algorithms) became much better.
Cad rule 2359 is often misinterpreted. It basically just says, that it’s a good idea to organise yourself and your clients in a way that you never run out of sleep, time and vodka. (Not to smoke also helps…)

It begins with the philosophy that good things need enough kappa and euros.
I would never sell my algorithmic skills as something faster, efficient or superior to others. That just invites
people for testing it out. In my universe there is no place for bad curve input, because you won’t make good
surface data from imprecise curves anyway :wink: Besides that I would never run into a situation where I need to reorganise curves like that, but that’s another story.
It’s just that most people don’t like to hear that, they always outsource work
to others, dreaming of a world where computers and few na(t)ive europeans people do all the work.

Nice work by the way,

So yes I’m doing good, how are you?


(Pfotiad0) #20

Yikes! Who wants to live for ever? You tell me.

Other than that my universe is full of bad data, wrong data, stupid data and data that make no sence at all (Karma what else?). So for the pro internal C# stuff … 90% of effort is wasted to deal with that bad version of the universe (Karma what else?).

Additionally the Panigale fried (Karma, what else?) the ECU and I’m forced to ride a stupid BMW R1200S (Karma, what else?). Kinda driving a Skoda I confess.

Moral: How had the mighty fallen.