Sorting edges/vertices


#1

Hi,

I’m having some trouble with correctly generating the shape of multiple faces that have the same plane and are connected. I already have an algorithm that returns the outer edges of multiple faces, but I still haven’t figured out how I can use this information correctly.

Take this simple example:

http://imgur.com/ldXe0y4

The algorithm correctly detects the outer edges, but then I have trouble using those edges to get a new face, one that encompasses all 3 faces on the bottom. The points I got are out of order, which is important.

def self.entity_set_border(entities)
    edges = Set.new(entities.map{ |face| face.edges }.flatten)	    
    border = edges.select { |edge| 1 == edge.faces.count { |face| entities.include?(face) }}
    border
end

def self.calculate_outer_loop(entities)
	border = self.entity_set_border(entities) # get outer edges
	points = border.map{|b| b.vertices}.flatten
	group = Sketchup.active_model.entities.add_group 
	# face = group.entities.add_face border 	# Error: #<ArgumentError: Edge has different parent>
	# face = group.entities.add_face points 	# Error: #<ArgumentError: Duplicate points in array>
	face = group.entities.add_face points.uniq # Wrong order
	result = face.vertices.map{|v| v.position}
	Sketchup.active_model.entities.erase_entities group
	result
end

I tried a few different approaches, but apparently I got a log stuck before my eyes. Sorting the points manually (calculating the center of the array of points and sort them by their angle to it) doesn’t work with more complicated shapes like my example.

Any ideas?


#2

You need to get the edges using Face#outer_loop not Face#edges. The latter does not return the Edges in sorted order whereas the former returns a Loop object in which they are ordered.


#3

I used both, but the problem was during the face generation. When the edges are in the wrong order, the resulting face is already “corrupt”.

In the mean time I wrote this to travel the edges from one end to the other and sort them myself, it kinda works, but there are still some edgecases I think…

def self.sort_edges(edges, reversed)
	curr = edges.first
	edges.delete curr
	vertices = curr.vertices
	start = reversed ? vertices[0] : vertices[1]
	other = reversed ? vertices[1] : vertices[0]
	result = [start, other]
	while start != other  
		n = edges.select{|x| x.vertices[0] == other || x.vertices[1] == other}.first
		edges.delete n
		other = n.vertices[0] == other ? n.vertices[1] : n.vertices[0]
		result << other
	end
	result
end

#4

A face outer_loop,vertices is returned ccw, any inner loops are cw.
Taking into account the face.normal.
Confusion can arise id a face has been reversed and the loop is unchanged.
Also a face made at z=0 always [initially] faces downwards, irrespective of the loop’s vertices direction.
So making a face at z=0 with a ccw set of points still has its normal as ==Z_AXIS.reverse anyway.

To remove the shared edges [I’d forget about loops, normals etc]…

faces = [face1, face2, face3] edges = [face1.edges, face2.edges, face3.edges].flatten togos = [] edges.each{|e| next unless e.faces[1] ### only look at shared edges shared = true e.faces.each{|f| shared = false unless faces.include?(f) ### skip shared edges which are NOT shared by any of the three faces } togos << e if shared } togos[0].parent.entities.erase_entities(togos) if togos[0]

Or something similar…
I fixed it at three faces but of course you can make a more generic format…


Detect the doors exists in which face
#5

I wasn’t looking to remove shared edges, but having a correct representation of the “whole” face that I can store and use for something else without altering the model. Things like area, dimensions etc. That’s why I tried creating such an imaginary face, storing those details (in my example only the “border”) and then remove it.


#6

You can easily replicate those three faces inside a temporary group, then delete the shared edges.
I’d probably replicate their other_loop edges and then use edge.find_face to make the faces, before finding the edge.faces[1] ones which need removing…
Note how in this approach the check for shared edges that are not shared by one of the three faces is then superfluous.
Inside the group you’ll then have a single combined face.
Get the ordered outer-loop vertices/points from that…
Do what you want with those… and later on delete the temp-group ?

edges = [face1.other_loop.edges, face2.other_loop.edges, face3.other_loop.edges].flatten.uniq
group = face1.parent.entities.add_group()
gents = group.entities
edges.each{|e| gents.add_line(e.start, e.end) }
gents.grep(Sketchup::Edge).each{|e| e.find_faces unless e.faces[0] }
togos = []
gents.grep(Sketchup::Edge).each{|e| togos << e if e.faces[1] }
gents.erase_entities(togos) if togos[0]
face = gents.grep(Sketchup::Face)[0] ### there should be only one ?
verts = face.outer_loop.vertices
### do what you want with the vertices / points etc
...
### erase temp group
group.erase!
...

#7

Cool, that should work, I didn’t make that connection. Will see which method is faster and less error-prone… Thanks for your advice


#8

hi @TIG, could you share me how to make the code to get other_loop on each Face?


#9

Faces have loops.
All faces have an outer loop.
If there are 'holes in the face these are inner loops.
I assume you want to get a face’s inner, ‘other’ [non-outer], loops ?

Following from the earlier example…

# We have a preset reference to a face: 'face'
loops = face.loops
# which is an array of all loops used by that face - 
# it will always contain at least one element [the outer loop]
outer = face.outer_loop
# i.e. the one loop forming that face's outer perimeter
inners = loops - [outer]
# an array of any other loops that are NOT the face's outer loop

Remember that the ‘inners’ array might be empty [] - if there are no ‘holes’…