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

0 Members and 1 Guest are viewing this topic.

domenicomaria

  • Swamp Rat
  • Posts: 723
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: 12905
  • 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: 723
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


It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8659
  • 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


VovKa

  • Water Moccasin
  • Posts: 1626
  • 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: 723
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: 723
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: 1396
  • 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.
A man who never made a mistake never made anything

kdub_nz

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2121
  • 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.

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

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8659
  • 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

domenicomaria

  • Swamp Rat
  • Posts: 723
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.    (entmakex
  28.       (list   '(0 . "LINE") '(100 . "AcDbEntity") '(410 . "Model") '(100 . "AcDbLine") (cons 10 p1) (cons 11 p2) )
  29.    )
  30. )
  31.  
  32. ;-------------------------------------------------------
  33. (defun :SS-BEFORE-EL (  / tmp x-en)
  34.    (if(setq x-en (entlast) )
  35.       (if (setq tmp (entnext x-en)) (:SS-BEFORE-EN tmp) x-en)
  36.       nil
  37.    )
  38. )
  39.  
  40. ;-------------------------------------------------------
  41. (defun :SS-AFTER-SS (x-en / tmp ss)
  42.    (setq ss (ssadd))
  43.    (while (setq x-en (if x-en (entnext x-en) (entnext) ) ) (ssadd x-en ss) )
  44.    (if (> (sslength ss) 0) ss nil)
  45. )
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52. ;-------------------------------------------------------
  53. (defun c:MESH-SHAPE ( / eb p10 p11 p12 segs-lst shape-seg-lst ss ss-el-lst ssa trng-lst x-trng )
  54.    (and
  55.       (setq ss (LM:SSGET "\nselect 3DFACES to get their SHAPE <exit> :" '(((0 . "3DFACE"))) ) )
  56.       (setq ss-el-lst (:SS>ENTGET-LIST ss) )
  57.       (setq trng-lst (mapcar ':3DF-3V-LST ss-el-lst) )
  58.       (setq segs-lst (mapcar '(lambda (x-trng)
  59.                                  (setq p10 (car x-trng) p11 (cadr x-trng) p12 (caddr x-trng) )
  60.                                  (list (list p10 p11) (list p11 p12) (list p12 p10) )
  61.                               )
  62.                              trng-lst
  63.                      )
  64.       )
  65.       (setq segs-lst (apply 'append segs-lst) )
  66.  
  67.       (foreach x-seg segs-lst
  68.          (if(not (member (reverse x-seg) segs-lst) )
  69.             ;   (not (vl-member-if '(lambda (i) (equal i (reverse x-seg) 1e-6) ) segs-lst) )
  70.             (setq shape-seg-lst (cons x-seg shape-seg-lst) )
  71.          )
  72.          t
  73.       )
  74.      
  75.       (setq eb (:SS-BEFORE-EL) )
  76.       (foreach x-seg shape-seg-lst (:LINE (car x-seg) (cadr x-seg) ) )
  77.       (setq ssa (:SS-AFTER-SS eb) ) (sssetfirst ssa ssa)
  78.      
  79.    )      
  80.    
  81. )
  82. (defun C:MS () (c:MESH-SHAPE) )
  83.  
  84. (princ "\ntype \"MS\"")


domenicomaria

  • Swamp Rat
  • Posts: 723
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: 723
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: 723
Re: SHAPE of a 2D MESH
« Reply #13 on: May 19, 2023, 07:46:59 AM »
and this is the result ...

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8659
  • 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