Finding Faces in Edge Collection

[wandererfan]

Does anybody have an algorithm for finding the Faces(closed regions?) in a collection of Edges? There are multiple regions - see picture.

edgesToFaces.png (4.3 KiB) Viewed 2424 times

The HLR algorithms only return Edges. ShapeAnalysis_FreeBounds::ConnectEdgesToWires uses each edge only once, so doesn't work in this case (an Edge can be a boundary of multiple regions). ShapeAnalysis_FreeBounds::SplitWires helps a bit, but still only uses each edge once.

A walker that visits each Vertex, remembers which Edge it followed out and repeats until all the paths have been followed? Sounds complex.

Any ideas appreciated.

wf

[ulrich1a]

Does anybody have an algorithm for finding the Faces(closed regions?) in a collection of Edges? There are multiple regions - see picture.

OCCT returns the shapes in a way, that the edges are ending in vertices, where a connection between two or more edges exist. This must not be the case for the HLR algorithm.
The needed algorithm needs more tests, if there are connections, where one edge has no vertex.

A walker that visits each Vertex, remembers which Edge it followed out and repeats until all the paths have been followed? Sounds complex.

I have done something similar in the sheet-unfold-macro. I did generate a tree of faces of one side of a metal-sheet, based on a search starting at one face.

My idea is an recursive search, where at each connection, that has more than two edges, new searches are started for each additional edge.
The search would for example always follow an edge, that has the smallest clockwise angle.
The search is finished, if an already walked vertex is reached, or if the edge has no connections.
If an already walked vertex is reached, a face is returned.

Ulrich

[wandererfan]

OCCT returns the shapes in a way, that the edges are ending in vertices, where a connection between two or more edges exist. This must not be the case for the HLR algorithm.

The HLR Edges have vertices, but the Vertices at the connection points are no tneccessarily the same (ie IsSame() == false). So I guess the first step would be to create metaVertex(V1,V2,...Vn) - one per connection node - for all V that have the same Point.

My idea is an recursive search, where at each connection, that has more than two edges, new searches are started for each additional edge.
The search would for example always follow an edge, that has the smallest clockwise angle.
The search is finished, if an already walked vertex is reached, or if the edge has no connections.
If an already walked vertex is reached, a face is returned.

That's where I was going, I think. I was hoping somebody could point me to the well known, but elusive, "Morgenstern-Nkombe-Chen algorithm "

Thanks for the tips.

wf

[DeepSOIC]

Hi!
If the edges are all in one plane, then it is possible with Boolean operations.
Steps:
1. Create a big face around all wires (use bounding box )
2. extrude the edges, to get a non-manifold shell
3. Part Cut the big face with the shell
4. Remove one the outermost face from the result of cutting. Done!
This can be done with Lattice workbench. My Skyscraper Generator project is powered by this method.

[DeepSOIC]

Another topic on this. Planar again.
viewtopic.php?f=22&t=12396#p117328

[wandererfan]

If the edges are all in one plane, then it is possible with Boolean operations.

At one time BOPs on 2D objects were discouraged due to unreliability. Is this no longer true?

If 2D BOPs are OK, your solution looks great! The Edges are all in the plane of a DrawingPage.

Boost Graph Library can do a Planar Face Traversal, but I think learning how to use it would be harder than writing from scratch.

wf

[DeepSOIC]

Just like with solids, there are problems with tangent intersections. Apart from that, I had no trouble so far. And I actually use 2d Booleans quite often, because they are much faster.

[wandererfan]

Excellent!

DeepSOICMethod.png (3.9 KiB) Viewed 2343 times

How do you find the big Face in the list? Biggest OuterWire.Length?

Spasibo!
wf

[DeepSOIC]

I have been finding it by its interaction with bounding box (it is the face that defines the bounding box of the result). I don't know how exactly do you make the big face... but if it is polygonal (that is, outer wire is made of only lines), you can find a vertex that is the most extreme on one of coordinates (say, largest X coordinate), and the face that has the vertex will be the face to remove.

Largest length of outer wire isn't always correct. An inner face may happen to have a longer outer wire if it is very very non-convex (e.g. star-shaped).