Sorting algorithm

bomastudio

Hi guys! I need some help, not directly on SU. I'm am able to read a *.dxf file, looking for lines entities. I want to find lines that belongs to a closed loop but I can't be sure that vertex are sorted as I expect. Have you some suggestion?

Aerilius

What sort of entities and data structures do you have (array of line entities, array of vertices, or line entities with random orientation)?
Can a line end be connected to more than one other line? Then we would need more criteria.

bomastudio

The file is a *.dxf one, so extracting datas gives me an array like the following:


% assuming a 2D drawing, so only x- and y- coords...
%
% drawing a triangle (with edges not well sorted)
% first line from (0,0) to (3,0)
% second line from (0,4) to (0,0)
% third line from (3,0) to (0,4)

lines=[0,0,3,0,0,4,0,0,3,0,0,4]

% the array lines, of course, will have lots of couples of vertex (a line goes from a point (x1,y1) to the second (x2,y2) )
%
% Moreover I can't be sure if between these vertex could be other vertex that belongs other polygon..

% I need to understand which of these vertex build a polygon, so I need to understand which lines form a continuous loop, a path....

TIG

Rather than worrying about 'sorting' these lines inside the dxf data... why not just import it into a SKP.

The resulting new component will include all of the dxf's lines as new edges - collect those with say:
edges=dxf_defn.entities.grep(Sketchup::Edge)
Now use edge.find_faces on all of those.
Any edge.faces.length==0 is not part of a 'loop'.
So if you no longer need those then you can erase them [?].
Reiterate the entities to collect all of these faces:
faces=dxf_defn.entities.grep(Sketchup::Face)
Now each ' edge' in each face.edges are part of a 'loop'.
To find a 'set' of these edges use face.loops and then use loop.edges for each loop.
Remember that a face might have an outer and inner loops - if you only want the outer one use face.outer_loop instead...
Also an edge could be shared by two touching faces' loops and will be collected more than once - you need to decide how you resolve this...

Thus you can readily find 'connected edges that form loops'...
As you haven't really explained why you need to sort these lines inside the dxf, then this is a much simpler approach...

bomastudio

Thanx TIG, it could be a possibile solution.
Well, I will try to explane better the problem: I need to sort NOT inside the dxf but after read the file and before draw on SU. I want to identity all lines of a loop so I can create a face and then extrude it for every loop on a specific layer. If the loop is a polyline the task is simple (each polyline is a loop) but if it is made of separate lines....

TIG

My method does that for you...
It will find all possible faces for the DXF's imported edges inside its component.definition.entities, using edge.find_faces on every edge in the collection.
Then you can collect the faces=component.definition.entities.grep(Sketchup::Face)
Then you can use those faces make sub-groups, make extrusions, change materials, move onto layers etc etc as you wish...
You seem to be over thinking this; there is no need to collect loops of edges from the DXF itself and add faces to them.
Import its edges.
Then the act of edge.find_faces makes all possible faces for you.
You then do what you will with those faces...

bomastudio

TIG excuse me, only to deeply understand: I read the dxf, and draw it into a group. Then collecting the lines with

edges=mygroup.entities.grep(Sketchup;;Edge)

So you say using edge.find_faces on all of edges? Say

edges.each{|e|
    myface = e.find_faces
    if myface.length==0
        mygroup.entities.erase_entities(e)
    end    
}

This code will create each face between all loops, is this right?

TIG

No, you don't seem to understand the basics...

You import the dxf.
Either using the native importer or for 'Free' one of the other importer plugins.
You should then have a component containing the imported geometry.
If you do not then make it into one,

You now do all of your processing inside the component.definition.entities collection.
Making 'collections' of objects to be processed:
edges=component.definition.entities.grep(Sketchup::Edge)
which will find all of its edges.
Then add faces to those with:
edges.each{|e| e.find_faces }
Now find those faces:
faces=component.definition.entities.grep(Sketchup::Face)

Now do what you want with those faces...
faces.each{|face| ### }
Where the ### is whatever you want to do..........

***If the imported dxf has unfaced edges and you want to delete them, then AFTER adding ALL of the faces, use something like:
togos=[]; edges.each{|e| togos << e if e.faces.length==0 }; edges[0].parent.entities.erase_entities(togos) if togos[0]
It's best to do this once ALL edges are processed, occasionally you might need to try and face more that one edge in a loop to make it face - similar to overdrawing edges, which sometimes will not for a face...
Remember that if the dxf is shoddily made in CAD - there might be crossing lines or lines with tiny gaps / overlaps - then it might not form a face, simply because there is no proper 'loop'...

bomastudio

Ok TIG I understand.....I just said "group" because I don't use neither the SUpro import nor external plugin, I'm using mine importer: it return to me a group with all the dxf drawing. I used your technique (sustituting the group to the componenet.definition) and it works fine..