Wed, 06/28/2023 - 18:01
Forums:
I have a planar wire which self-intersect several times (black).
I would like to extract a wire representing the outer perimeter (red).
Any tool that could help with this?
Great thanks!
Attachments:
Collaborative development portal
Wed, 06/28/2023 - 22:58
There is no ready tool. You need to develop something new. The class Poly_MakeLoops can help after you split the curve at all intersection points.
Thu, 06/29/2023 - 09:04
Splitting the wire is aready something: once the wire is split in non-intersecting edges, one could pick a random point on the edge, trace a ray in a random direction and count the intersections with the rest of the edges, if odd the edge is discarded, if even it is kept. It should work, thank you.
Mon, 07/03/2023 - 19:21
Hi,
I had a similar problem, which I seem to have solved, however the solution is a little slow.
Basically the procedure is as follows:
- assuming all edges are in-plane XY
- perform a bool union to ensure all edge intersections are split
- assuming that both ends of all edges are connected to another edge (no unconnected edges)
To find a loop
- keep a set of visited edges
- start from a random edge not in any existing loop:
- pick a vertex to be the "end"
- look for an edge which connects to this vertex
- if found, push the new edge to the stack,
- if not found, pop off the stack and try again
- once you have looped back such that the "end" of the last vertex on the stack is equal to the "start" vertex, you have found a loop
Once a loop is found:
create a face and save it to the output,
repeat the loop finding procedure with the starting edge being an edge not present in any of the faces we have previously generated.
Once every edge is present on at least one face,
- bool.union + sew faces to get a single output face
I don't think this will respect any voids (e.g. nested rings), but if you just want the total outline that might not matter.
Also as you can see some of the loop faces look a little strange, but they seem to work out correctly when fused.
Tue, 07/04/2023 - 00:21
The making of loops in this solution can be done with ready to use class Poly_MakeLoops. If one charges it with all edges going in both directions the tool will construct all loops in counter-clock wise (CCW) direction, and the most outer loop - in clock wise (CW) direction. This latter loop will be the target one. Of course, if there are nested loops (like several concentric rings) there several CW loops will be found, but the target one will have the largest area with negative sign.
Tue, 07/04/2023 - 10:53
My understanding is that this is from the "Poly" package, which is for dealing with polygons. Would this work with arbitrary TopoDS_Edges ?
Tue, 07/04/2023 - 23:59
Just open that header file and read description. That class can work with arbitrary edges, which are defined by pairs of integers. Actually it finds all minimal loops in a graph. You give to the algorithm your own instance of special interface to your data structures.
Wed, 07/05/2023 - 00:01
Also, it can work with any dimension, 2D or 3D, you choose what you need.
Tue, 07/11/2023 - 13:47
Ah I see. Since the intersections are removed there is no longer a need to worry about the exact geometry of the edges? I guess there is one issue however: what about duplicate links (different TopoDS_Edge types sharing the same endpoints) in this case, would the algorithm be able to determine which edge represents the outer boundary? From what I can see it would not? (see attached)
Tue, 07/11/2023 - 13:54
(I suppose that's outside the scope of a single self-intersecting wire though!). Actually scratch that, maybe not...
Wed, 07/12/2023 - 00:22
You are right, there can be only one edge on two nodes. So, in your case with two such edges you need to introduce a fictive node for one of duplicates to overcome ambiguity.