Merging a bunch of separated segments into a neat set of polygons.

Questions
,
1

Hello Everyone,

This is my first request to the group. I’ve been trying to import dxf files with 2D drawings. Depending on the dxf source, I get often simple “exploded” lists like that:

{Line[{{-16.73, 61.8, 0.}, {-16.53, 61.8, 0.}}], 
 Line[{{-16.53, 61.8, 0.}, {-16.53, 61.9, 0.}}], 
 Line[{{-16.53, 61.9, 0.}, {-16.58, 61.9, 0.}}], 
 Line[{{-16.58, 61.9, 0.}, {-16.58, 62.7, 0.}}], 
 Line[{{-16.58, 62.7, 0.}, {-16.44, 62.7, 0.}}], 
 Line[{{-16.44, 62.7, 0.}, {-16.44, 61.9, 0.}}], 
 Line[{{-16.44, 61.9, 0.}, {-16.49, 61.9, 0.}}], 
 Line[{{-16.49, 61.9, 0.}, {-16.49, 61.76, 0.}}], 
 Line[{{-16.49, 61.76, 0.}, {-16.61, 61.76, 0.}}], 
 Line[{{-16.61, 61.76, 0.}, {-16.61, 61.1747, 0.}}], 
 Line[{{-16.61, 61.1747, 0.}, {-18.2904, 60.376, 0.}}]}

This (generally huge) list of independant segments constitutes (in the design I import) a set of many polygonal paths (closed or not) that I want to identify and store as such (in the form of {Line{p1,p2,p3,…pn},Line{q1,q2,q3,…qm},etc…},each “Line” object storing a different polygon. I have built a pedestrian approach by starting with the first segment of the list and seaching the next neighbor segment by selecting the segment that a common vertex (it is assumed that there are no branches, so only polygonals contour, closed or not, are expected) and so on, removing the extracted lines from the initial list. It is slow , painfull and not very cleanly written I must admit.
Has someone a neat one-liner to propose to perform the function? Or even a built-in funtion that does the job?

Unfortunately enough , some crazy dxf are not so neat so I may find sometimes two aligned segments (with a shared intersection) that I should merge in a first phase (otherwise the above algorithm is lost in the middle of a polygon) . It takes some time to check all possible pairs of segments, check if they are aligned and in that case check if they intersect, then replace them by their union. So same question for this preparatory work: is there a clever way to do it ?

Thanks in advance for your comments

Christian

2

I am a bit confused. Are you saying that you have duplicate segments and need to to delete them? Ot segments are always unique and in a proper sequence? - which seems to be true for the sample data you gave. Maybe you could show your code? It is a bit unclear to me what do you need to do.

3

Probably there is not a simple one-liner that will do this for you, maybe you can give us a real-world example (upload the file somewhere on the internet) and your first attempt. Maybe we can shave down the running-time of your script or find a neat algorithm.

If they are ordered you could put them together using (something like):

l={Line[{{-16.73,61.8,0.},{-16.53,61.8,0.}}],Line[{{-16.53,61.8,0.},{-16.53,61.9,0.}}],Line[{{-16.53,61.9,0.},{-16.58,61.9,0.}}],Line[{{-16.58,61.9,0.},{-16.58,62.7,0.}}],Line[{{-16.58,62.7,0.},{-16.44,62.7,0.}}],Line[{{-16.44,62.7,0.},{-16.44,61.9,0.}}],Line[{{-16.44,61.9,0.},{-16.49,61.9,0.}}],Line[{{-16.49,61.9,0.},{-16.49,61.76,0.}}],Line[{{-16.49,61.76,0.},{-16.61,61.76,0.}}],Line[{{-16.61,61.76,0.},{-16.61,61.1747,0.}}],Line[{{-16.61,61.1747,0.},{-18.2904,60.376,0.}}]}

l=l//.{a___,Line[{x___,y_}],Line[{y_,z___}],b___}:>{a,Line[{x,y,z}],b}

Graphics3D[l]

It is very short code, and probably will not be the fastest solution to your problem :wink:

4

Here is more efficient but less universal version of Sander’ solution:

l={Line[{{-16.73,61.8,0.},{-16.53,61.8,0.}}],Line[{{-16.53,61.8,0.},{-16.53,61.9,0.}}],Line[{{-16.53,61.9,0.},{-16.58,61.9,0.}}],Line[{{-16.58,61.9,0.},{-16.58,62.7,0.}}],Line[{{-16.58,62.7,0.},{-16.44,62.7,0.}}],Line[{{-16.44,62.7,0.},{-16.44,61.9,0.}}],Line[{{-16.44,61.9,0.},{-16.49,61.9,0.}}],Line[{{-16.49,61.9,0.},{-16.49,61.76,0.}}],Line[{{-16.49,61.76,0.},{-16.61,61.76,0.}}],Line[{{-16.61,61.76,0.},{-16.61,61.1747,0.}}],Line[{{-16.61,61.1747,0.},{-18.2904,60.376,0.}}]}

l2=Line[Append[l[[All, 1, 1]], l[[-1, 1, -1]]]]

Graphics3D[l2]

Another version:

l2 = Level[l, {-2}]
l2 = Line@DeleteDuplicates[l2]
Graphics3D[l2]
5

Hello All, and thank you very much for your proposals. The segments are unfortunately not ordered and I had to match vertex under a distance criteria (such as EuclideanDistance < epsilon). I am currently not on my PC at work but I’ll try to get and send the code (and more representative data) to be more precise.

More to come

Christian

6

Hello again,

Here is a more representative data sample I use to build the polygonal chains I need:

sampledata={{{171.797, 143.727}, {165.422, 143.727}}, {{165.422,
   143.727}, {165.422, 140.844}}, {{165.422, 140.844}, {165.223,
   140.844}}, {{165.223, 140.794}, {165.422, 140.794}}, {{165.422,
   140.794}, {165.422, 137.91}}, {{165.422, 137.91}, {171.797,
   137.91}}, {{171.797, 137.91}, {171.797, 143.727}}, {{178.197,
   143.827}, {165.223, 143.827}}, {{165.223, 143.777}, {171.847,
   143.777}}, {{171.847, 143.777}, {171.847, 137.91}}, {{171.847,
   137.91}, {178.197, 137.91}}, {{178.197, 137.91}, {178.197,
   143.827}}, {{184.597, 143.977}, {165.223, 143.977}}, {{165.223,
   143.877}, {178.247, 143.877}}, {{178.247, 143.877}, {178.247,
   137.91}}, {{178.247, 137.91}, {184.597, 137.91}}, {{184.597,
   137.91}, {184.597, 143.977}}, {{190.997, 144.177}, {165.223,
   144.177}}, {{165.223, 144.027}, {184.647, 144.027}}, {{184.647,
   144.027}, {184.647, 137.91}}, {{184.647, 137.91}, {190.997,
   137.91}}, {{190.997, 137.91}, {190.997, 144.177}}, {{197.397,
   144.427}, {165.223, 144.427}}, {{165.223, 144.227}, {191.047,
   144.227}}, {{191.047, 144.227}, {191.047, 137.91}}, {{191.047,
   137.91}, {197.397, 137.91}}, {{197.397, 137.91}, {197.397,
   144.427}}}

Using a manipulate function, it can be seen that all individual segments build a set of 5 open polygons that I want to detect but all segment are not ordered by polygon …

Manipulate[Take[sampledata, {1, i}] // Line // Graphics, {i, 1,Length[sampledata], 1}]

EndSegs2D is a list supposed to content all pairs of points each constituing a 2D segment , in the form {{p1, p2}, …} where p1 = {x1, y1}, p2 = {x2, y2}, etc …

EndSegs2D = sampledata
polygons = {};
TreatedSegs2D = {};
i = 1;
While[Length[EndSegs2D] != 0,
i0 = 1;
endpoint = EndSegs2D[[i0, 1]];
startpoint = EndSegs2D[[i0, 2]];
origin = endpoint;
epsilon = 0.001;
vertex = {origin};
point = {};
test = 1;
While[point != origin,
  point1 =
   Select[EndSegs2D, (EuclideanDistance[#[[1]], startpoint] <=
        epsilon && EuclideanDistance[#[[2]], endpoint] > epsilon ) &];
  point2 =
   Select[EndSegs2D, (EuclideanDistance[#[[2]], startpoint] <=
        epsilon && EuclideanDistance[#[[1]], endpoint] > epsilon ) &];
  point = {};
  If[point1 != {}, point = point1[[1, 2]];
   pos = Position[EndSegs2D, point1[[1]]][[1, 1]];
   AppendTo[TreatedSegs2D, EndSegs2D[[pos]]];
   EndSegs2D = Delete[EndSegs2D, pos]];
  If[point2 != {}, point = point2[[1, 1]];
   pos = Position[EndSegs2D, point2[[1]]][[1, 1]];
   AppendTo[TreatedSegs2D, EndSegs2D[[pos]]];
   EndSegs2D = Delete[EndSegs2D, pos]];
  If[point == {}, EndSegs2D = Delete[EndSegs2D, 1];
   Print["Break at ", EndSegs2D // Length, " ", i]; test = 0; Break[]];
  If[point == origin, Print["Ok ", i];
   AppendTo[TreatedSegs2D, EndSegs2D[[1]]];
   EndSegs2D = Delete[EndSegs2D, 1]];
  endpoint = startpoint;
  AppendTo[vertex, startpoint];
  startpoint = point];
If[Length[vertex] > 3, AppendTo[vertex, origin];
  AppendTo[polygons, vertex]; i++];]

Here a graphics check of the result. It can be seen that my code is not perfect because each independant polygon chain is not detected (it seems that the detection is faulty because each polygon is essentially scanned in one direction)

{{Green, Line[polygons]}, {Blue, vertex // Line}, {Black,Line[sampledata]}} // Graphics

Hope this is more clear.

Thanks in advance for your comments

Christian