### Author Topic: SHAPE of a 2D MESH  (Read 1434 times)

0 Members and 1 Guest are viewing this topic.

#### domenicomaria

• Swamp Rat
• Posts: 521
##### SHAPE of a 2D MESH
« on: May 18, 2023, 07:32:57 AM »
I need someone to point me to an algorithm to solve the following problem.

In the XY plane I have a mesh of triangles defined by 3 2D points, counterclockwise.

I need to know the contour that bounds the mesh
(not the bounding box, but the contour that defines the shape of the mesh in the XY plane)

And possibly if the mesh has holes, I also need to know the outline of the holes.

The whole thing has to be fixed without any ACAD command,
but only mathematically and geometrically.

Is there anyone who can tell me something ?

#### Lee Mac

• Seagull
• Posts: 12779
• London, England
##### Re: SHAPE of a 2D MESH
« Reply #1 on: May 18, 2023, 08:08:52 AM »
For convex areas, you can compute the Convex Hull of all points defining the mesh; for concave regions/holes the task becomes rather more complex.

#### domenicomaria

• Swamp Rat
• Posts: 521
##### Re: SHAPE of a 2D MESH
« Reply #2 on: May 18, 2023, 08:32:42 AM »
Thanks Lee

This evening (it's now 14.33 in Italy) I'll have a look at it!

I've seen the lisp code on your site and it looks simple.

Let's leave the holes alone,
but the mesh actually can also be concave . . .

With Acad commands the solution could be :
. convert 3dfaces into LWPolylines
. convert the LWPolylines into regions
. union everything
. explode the region
. join every thing

but I don't care

ciao

#### El Jefe

• Retired
• Needs a day job
• Posts: 7921
• AKA Daniel
##### Re: SHAPE of a 2D MESH
« Reply #3 on: May 18, 2023, 09:18:13 AM »
Concavity and holes are really hard, there’s a cool algorithm here:
https://github.com/mapbox/concaveman

Concavity can sometimes be calculated from a TIN, I played with it a bit here:
https://www.theswamp.org/index.php?topic=57122.msg607153#msg607153

Retired

#### VovKa

• Water Moccasin
• Posts: 1557
• Ukraine
##### Re: SHAPE of a 2D MESH
« Reply #4 on: May 18, 2023, 10:18:42 AM »
build a list of edges
remove all duplicate edges
then trace along all unique edges

#### domenicomaria

• Swamp Rat
• Posts: 521
##### Re: SHAPE of a 2D MESH
« Reply #5 on: May 18, 2023, 01:18:19 PM »
build a list of edges
remove all duplicate edges
then trace along all unique edges

Vovka, sounds like a simple and great idea...

i'll try it and let you know...

... but i really think this is the right way...

thanks

#### domenicomaria

• Swamp Rat
• Posts: 521
##### Re: SHAPE of a 2D MESH
« Reply #6 on: May 18, 2023, 03:48:25 PM »
however, I think a clarification is useful.

I don't have a 2d point cloud
and I don't need to determine which is the shape
that contains the cloud

I have a set of triangular 3dfaces
and I have to determine the external shape
and also any holes.

so the problem is much simpler than it may seem

vovka's solution is a bit slow (VLisp !) but it's perfect!

I can't imagine another solution.

As soon as I fix the code, I'll share it.

But i believe Vovka's solution is the right one!

#### BIGAL

• Swamp Rat
• Posts: 1226
• 40 + years of using Autocad
##### Re: SHAPE of a 2D MESH
« Reply #7 on: May 18, 2023, 09:17:45 PM »
Outside boundary may be possible by using bpoly draw a rectang around all triangles, then Bpoly pick a point between triangles and the outside pline a new pline should be made. Erase out side dummy pline.

Holes a manual way is again bpoly.

#### kdub_nz

• Mesozoic keyThumper
• SuperMod
• Water Moccasin
• Posts: 1702
• class keyThumper<T>:ILazy<T>
##### Re: SHAPE of a 2D MESH
« Reply #8 on: May 18, 2023, 09:38:00 PM »
Outside boundary may be possible by using bpoly draw a rectang around all triangles, then Bpoly pick a point between triangles and the outside pline a new pline should be made. Erase out side dummy pline.

Holes a manual way is again bpoly.

Yep, but
Quote
The whole thing has to be fixed without any ACAD command,
but only mathematically and geometrically.

Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

Sometimes the question is more important than the answer.[/i

#### El Jefe

• Retired
• Needs a day job
• Posts: 7921
• AKA Daniel
##### Re: SHAPE of a 2D MESH
« Reply #9 on: May 19, 2023, 12:59:24 AM »
post a sample drawing, might be a fun challenge
Retired

#### domenicomaria

• Swamp Rat
• Posts: 521
##### Re: SHAPE of a 2D MESH
« Reply #10 on: May 19, 2023, 03:28:03 AM »
Code - Auto/Visual Lisp: [Select]
1. ;-------------------------------------------------------
2. (defun LM:SSGET ( msg arg / sel )
3.     (princ msg)
4.     (setvar 'nomutt 1)
5.     (setq sel (vl-catch-all-apply 'ssget arg))
6.     (setvar 'nomutt 0)
7.     (if (not (vl-catch-all-error-p sel)) sel)
8. )
9.
10. ;-------------------------------------------------------
11. (defun :SS>ENTGET-LIST (ss / ind l)
12.    (setq ind 0 l '())
13.    (repeat (sslength ss) (setq l (cons (entget (ssname ss ind) ) l) )   (setq ind (+ 1 ind) ) )
14.    (reverse l)
15. )
16.
17. ;-------------------------------------------------------
18. (defun :3DF-3V-LST (x-el)
19.    (list (:DXF 10 x-el) (:DXF 11 x-el) (:DXF 12 x-el) )
20. )
21.
22. ;-------------------------------------------------------
23. (defun :DXF (code e-lst) (cdr (assoc code e-lst)))
24.
25. ;-------------------------------------------------------
26. (defun :LINE (p1 p2)
27.       (list   '(0 . "LINE") '(100 . "AcDbEntity") '(410 . "Model") '(100 . "AcDbLine") (cons 10 p1) (cons 11 p2) )
28.    )
29. )
30.
31. ;-------------------------------------------------------
32. (defun :SS-BEFORE-EL (  / tmp x-en)
33.    (if(setq x-en (entlast) )
34.       (if (setq tmp (entnext x-en)) (:SS-BEFORE-EN tmp) x-en)
35.       nil
36.    )
37. )
38.
39. ;-------------------------------------------------------
40. (defun :SS-AFTER-SS (x-en / tmp ss)
42.    (while (setq x-en (if x-en (entnext x-en) (entnext) ) ) (ssadd x-en ss) )
43.    (if (> (sslength ss) 0) ss nil)
44. )
45.
46.
47.
48.
49.
50.
51. ;-------------------------------------------------------
52. (defun c:MESH-SHAPE ( / eb p10 p11 p12 segs-lst shape-seg-lst ss ss-el-lst ssa trng-lst x-trng )
53.    (and
54.       (setq ss (LM:SSGET "\nselect 3DFACES to get their SHAPE <exit> :" '(((0 . "3DFACE"))) ) )
55.       (setq ss-el-lst (:SS>ENTGET-LIST ss) )
56.       (setq trng-lst (mapcar ':3DF-3V-LST ss-el-lst) )
57.       (setq segs-lst (mapcar '(lambda (x-trng)
58.                                  (setq p10 (car x-trng) p11 (cadr x-trng) p12 (caddr x-trng) )
59.                                  (list (list p10 p11) (list p11 p12) (list p12 p10) )
60.                               )
61.                              trng-lst
62.                      )
63.       )
64.       (setq segs-lst (apply 'append segs-lst) )
65.
66.       (foreach x-seg segs-lst
67.          (if(not (member (reverse x-seg) segs-lst) )
68.             ;   (not (vl-member-if '(lambda (i) (equal i (reverse x-seg) 1e-6) ) segs-lst) )
69.             (setq shape-seg-lst (cons x-seg shape-seg-lst) )
70.          )
71.          t
72.       )
73.
74.       (setq eb (:SS-BEFORE-EL) )
75.       (foreach x-seg shape-seg-lst (:LINE (car x-seg) (cadr x-seg) ) )
76.       (setq ssa (:SS-AFTER-SS eb) ) (sssetfirst ssa ssa)
77.
78.    )
79.
80. )
81. (defun C:MS () (c:MESH-SHAPE) )
82.
83. (princ "\ntype \"MS\"")

#### domenicomaria

• Swamp Rat
• Posts: 521
##### Re: SHAPE of a 2D MESH
« Reply #11 on: May 19, 2023, 03:33:37 AM »
the mesh is 3D ...
the 2D mesh is just a special case of the 3d mesh...

shape-seg-lst contains all the segments
of the outer shape that contains the set of triangles
and also the segments that define the hole inside ...

... now we need to join all the segments,
allways without using any Acad command  ...

... i tried and it did something but it malfunctioned
and I don't have time this morning to focus on this thing ...

... if anyone wants to help ...
« Last Edit: May 19, 2023, 04:53:38 AM by domenicomaria »

#### domenicomaria

• Swamp Rat
• Posts: 521
##### Re: SHAPE of a 2D MESH
« Reply #12 on: May 19, 2023, 03:42:03 AM »
if you want to test with your own meshes,

you before must ensure that the mesh contains :

. only triangular 3dfaces,

. with p13=p10 ,

. that in each 3dface there are no more than 1 segment (p13 p10) of zero length,

. and that the direction of the list of points is always counterclockwise,

. i.e. that the zeta component of the normal to the face is positive
« Last Edit: May 19, 2023, 03:45:15 AM by domenicomaria »

#### domenicomaria

• Swamp Rat
• Posts: 521
##### Re: SHAPE of a 2D MESH
« Reply #13 on: May 19, 2023, 07:46:59 AM »
and this is the result ...

#### El Jefe

• Retired
• Needs a day job
• Posts: 7921
• AKA Daniel
##### Re: SHAPE of a 2D MESH
« Reply #14 on: May 19, 2023, 09:23:34 AM »
well done! I was thinking of using the mid point of each edge as the check, instead of flipping them, not sure if that would work
I see you only needed a line, not a closed polyline, a bit of work to order the edges
Retired