To Find Self Intersection of LWPOLYLINE

To Find Self Intersection of LWPOLYLINE

MehtaRajesh
Advocate Advocate
11,994 Views
123 Replies
Message 1 of 124

To Find Self Intersection of LWPOLYLINE

MehtaRajesh
Advocate
Advocate

Hi,

I am posting useful function to find Self Intersection for selected LWPOLYLINE.
You might be having other options, but I find this one as a quickest and Simple


(defun IsSelfIntersect (l / vcnt vcnt1 crossresult pt1 pt2 pt3 pt4)
(setq vcnt 0)
(setq crossresult F)
(repeat (1- (length l))
 (setq pt1 (nth vcnt l))
   (setq pt2 (nth (1+ vcnt) l))
   (setq vcnt1 vcnt)
 (setq isdone "T")
 (while isdone
  (if (and (nth (+ 2 vcnt) l) (nth (+ 3 vcnt) l))
  (progn
   (setq pt3 (nth (+ 2 vcnt) l))
   (setq pt4 (nth (+ 3 vcnt) l))
       (if (inters pt1 pt2 pt3 pt4)
   (progn
      (setq crossresult T)
   );progn
   );if
  );progn
  (progn
   (setq isdone nil)
  );progn
  );if
    (setq vcnt (1+ vcnt))
 );while
   (setq vcnt (1+ vcnt1)) 
);repeat
crossresult
);defun

Below Function to get the Coordinate list of LWPOLYLINE

(defun lwptslw (lst / pair rtn)
  (while (setq pair (assoc 10 lst))
    (setq rtn (cons (cdr pair) rtn)
   lst (cdr (member pair lst))
    )
  )
  (reverse rtn)
)

USAGE:
Command: (IsSelfIntersect (LWPTSLW (ENTGET (CAR (ENTSEL "\nSelect Lwpolyline to find Self Intersectioni")))))

Regards,
Rajesh

0 Likes
11,995 Views
123 Replies
Replies (123)
Message 21 of 124

АлексЮстасу
Advisor
Advisor

Hi,

 

It doesn't matter what exactly we consider self-intersections. What matters is what AutoCAD calls self-intersections. 🙂


AutoCAD considers both self-overlapping and self-touching cases in many of its commands to be self-intersections. And users don't get the results of these commands. Or the programs cannot solve their tasks.

 

Self-overlap and self-touch can be considered as special cases of self-intersection - when the intersection area is 0.


... I have not yet found any really working lisp that finds all cases of at least ‘true’ intersections.


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes
Message 22 of 124

john.uhden
Mentor
Mentor

@АлексЮстасу wrote:

" I have not yet found any really working lisp that finds all cases of at least ‘true’ intersections."

Um, did you try out my latest offering?  If "it doesn't work" for you please tell me in what way it fails.

John F. Uhden

0 Likes
Message 23 of 124

АлексЮстасу
Advisor
Advisor

@john.uhden,

Please forgive me for not posting right away - I thought the example from @komondormrex in #17 was sufficient.


My three test files are:
1. Artificial, start_test_100-100.dwg. In the blue box are basic examples. In yellow I have circled the cases that your selfinters 11-15-2024 does not consider as self-intersections.
2. The real one, Level 4_self-intersections_or_not.dwg from a very old thread about self-intersections. In it, selfinters does not find self-intersections. But there's one or two of them there - the second one is more of a point duplication.
3. Artificial, mill_pl.dwg with realistic in cartography coordinates in millions and close to real cases. I have circled in yellow the object where selfinters self-intersections are not found. And magenta is the object that selfinters finds self-intersecting. But there are no self-intersections in this object.
Apparently, ‘detection’ of non-existent self-intersections is a consequence of such coordinates in millions and applied methods - Pline_SelfInters from #15 also finds fictitious self-intersections at such coordinates.

 

It is especially important to me now that your selfinters 11-15-2024 works the fastest.


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes
Message 24 of 124

АлексЮстасу
Advisor
Advisor

@john.uhden,

 

My friend, an absolute amateurs in programming, was able to write such a kind of function on my solution ideas.
Of course, it is not a real function, because my friend does not know how to vla-, lambda, etc. It is rather ideas and algorithm.


;--------------------------------------------
;; Обнаружение самопересечений lwpolylines
;; М. Брагин, 2024
(defun mb:Pline_SInters (Pline / clr cmd PntList Pnt1 Pnt2 Pnt3 Pnt4 intct overt dst kk ll mm nn)
  
  (setq PntList (mapcar 'cdr (vl-remove-if-not (function (lambda (x) (= (car x) 10))) (entget Pline)))
  )
  (if (and (vlax-curve-isClosed (vlax-ename->vla-object Pline)) (not (equal (car PntList) (last PntList) 1e-8)))
    (setq PntList (append PntList (list (car PntList))))
  )
  (setq cmde (getvar "CMDECHO"))
  (setvar "CMDECHO" 0)
  (setq clr (getvar "CECOLOR"))
  
  (setq nn 0 ll (length PntList))
  (while (< (+ nn 1) ll)
    (setq kk (+ nn 1)
	  Pnt1 (nth nn PntList)
	  Pnt2 (nth (+ nn 1) PntList)
    )
    (while (< (+ kk 1) ll)
      (setq Pnt3 (nth kk PntList)
	    Pnt4 (nth (+ kk 1) PntList)
	    dst (distance Pnt1 Pnt2)
	    mm nil
      )
      	(cond
	  ((and (> kk 1)
	        (not (equal Pnt4 (car PntList) 1e-6))
		(and (setq mm (inters Pnt1 Pnt2 Pnt3 Pnt4)) (not (vl-member-if '(lambda (x) (equal mm x 1e-6)) intct)))
	   )
	    (setq intct (cons mm intct))
	    (setvar "CECOLOR" "1")
	    (vl-cmdf "_.circle" mm 25)
	  )
	  ((and (> kk 1) (>= dst (distance Pnt1 Pnt3))
	        (not mm) (equal dst (+ (distance Pnt1 Pnt3) (distance Pnt2 Pnt3)) 1e-6) (not (vl-member-if '(lambda (x) (equal Pnt3 x 1e-6)) overt))
	   )
	    (setq overt (cons Pnt3 overt))
	    (setvar "CECOLOR" "4")
	    (vl-cmdf "_.circle" Pnt3 20)
	  )
	  ((and (>= dst (distance Pnt1 Pnt4)) (not (equal Pnt4 (car PntList) 1e-6))
		(and (not mm) (equal dst (+ (distance Pnt1 Pnt4) (distance Pnt2 Pnt4)) 1e-6) (not (vl-member-if '(lambda (x) (equal Pnt4 x 1e-6)) overt)))
	   )
	    (setq overt (cons Pnt4 overt))
	    (setvar "CECOLOR" "4")
	    (vl-cmdf "_.circle" Pnt4 20)
	  )
        ) ; _ cond
      (setq kk (1+ kk))
    ) ; _ while
    (setq PntList (cdr PntList)
	  ll (1- ll)
	  nn 0)
  ) ; _ while
  (setvar "CECOLOR" clr)
  (setvar "CMDECHO" cmde)
  (if IsRus
    (princ (strcat "\n - Самоналожения: " (vl-princ-to-string overt) "\n - Самопересечения: " (vl-princ-to-string intct) "\n"))
    (princ (strcat "\n - Self-overlapping: " (vl-princ-to-string overt) "\n - Self-crossing: " (vl-princ-to-string intct) "\n"))
  )
  (append (list overt) (list intct))
  (princ)
) ; _ defun  _ mb:Pline_SInters

 

But it finds all self-intersections and all self overlaps. And it doesn't give dummy self-intersections at millions of coordinates.
That's very good.
The bad thing is that it can't work at the right speed - for polylines with thousands of vertices it works for minutes. And we need only the first seconds...

 


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes
Message 25 of 124

john.uhden
Mentor
Mentor

@АлексЮстасу wrote, "Alexander, private person, pacifist, english only with translator ."

 

I am still working on this thing!

How about you and I duke it out in public while speaking only Swahili?

(Of course that leaves me speechless.)  😶

John F. Uhden

Message 26 of 124

john.uhden
Mentor
Mentor

@АлексЮстасу , @bergerF5EFQ , @komondormrex , @Kent1Cooper , @MehtaRajesh ,

Attached is a new version of selfinters.lsp plus a selfinters.dwg for testing.  The lisp file contains two (2) versions of the function... one for use and one for testing.

Rather than counting vertices vs. intersects, it checks for intersects that are not equal to any of the vertices.

In the drawing, that leaves #8 as nonintersecting even though there is one vertex that just "touches" a segment.

Now if #8 should be treated as selfintersecting, then I may have an alternate plan (in my head) to test for such conditions.  Please give me your opinions.

John F. Uhden

0 Likes
Message 27 of 124

Moshe-A
Mentor
Mentor

@john.uhden  hi,

 

i admit i wasn't in this thread until now but here is my version...

i put my 'fortune'  😀 on Lee's Mac (LM:intersections) function.

 

#1, #2, #5, #7 and #8 consider self intersect

#3, #4 and #6 - not

 

about efficiency? leave it for you to judge 😀

 

Moshe

 

 

;; Intersections  -  Lee Mac
;; Returns a list of all points of intersection between two objects
;; for the given intersection mode.
;; ob1,ob2 - [vla] VLA-Objects
;;     mod - [int] acextendoption enum of intersectwith method

(defun LM:intersections ( ob1 ob2 mod / lst rtn )
    (if (and (vlax-method-applicable-p ob1 'intersectwith)
             (vlax-method-applicable-p ob2 'intersectwith)
             (setq lst (vlax-invoke ob1 'intersectwith ob2 mod))
        )
        (repeat (/ (length lst) 3)
            (setq rtn (cons (list (car lst) (cadr lst) (caddr lst)) rtn)
                  lst (cdddr lst)
            )
        )
    )
    (reverse rtn)
); LM:intersections


;; obj is ENAME or VLA-OBJECT of polyline
(defun self-inters (obj / _isJoined ; local function
		          AcDbPline malloc ent Result AcDbObj0 AcDbObj1 ename0 ename1 p0 p1 p2 p3)

 ; anonymous function
 (setq _isJoined (lambda (b0 lst) (vl-some (function (lambda (b1) (equal (distance b0 b1) 0.0 1e-3))) lst)))

  
 ; here start (self-inters)
 (cond
  ((and
     (eq (type obj) 'ENAME)
     (wcmatch (cdr (assoc '0 (entget obj))) "POLYLINE,LWPOLYLINE")
   )
   (setq AcDbPline (vlax-ename->vla-object obj) malloc t)
  ); case
  ( t
   (setq AcDbPline obj)
  ); case
 ); cond
   
 (setq ent (entlast))
 ; allocating memory
 (setq objects^ (vlax-safearray->list (vlax-variant-value (vla-explode AcDbPline))))

 (setq result
	(vl-some
	 (function 
          (lambda (AcDbObj0)
	   (setq ename0 (vlax-vla-object->ename AcDbObj0))
	   (setq p0 (vlax-curve-getStartPoint ename0))
	   (setq p1 (vlax-curve-getEndPoint ename0))

	   (if (> (distance p0 p1) 0.0)
	    (vl-some
	     (function
	      (lambda (AcDbObj1)
               (setq ename1 (vlax-vla-object->ename AcDbObj1))
	       (setq p2 (vlax-curve-getStartPoint ename1))
	       (setq p3 (vlax-curve-getEndPoint ename1))

	       (if (> (distance p2 p3) 0.0)
	        (cond
	         ((or
		   (_isJoined p0 (list p2 p3))
		   (_isJoined p1 (list p2 p3))
		  )
		  nil
	         ); case
	         ((LM:intersections AcDbObj0 AcDbObj1 acExtendNone))
	        ); cond
	       ); if
		
              ); lambda
	     ); function
	     (cdr (member AcDbObj0 objects^))
	    ); vl-some
	   ); if
	    
	  ); lambda
	 ); function
         (reverse (cdr (reverse objects^))) ; chop last
        ); vl-some
 ); setq

 ; disppose memory
 (foreach o objects^
  (vlax-release-object o)
 )
  
 ; get rid from exploded objects
 (while (setq ent (entnext ent))
  (entdel ent)
 )

 ; dispose memory
 (if malloc
   (vlax-release-object AcDbPline)
 )
  
 Result ; list of inters points or nil
); self-inters


(defun c:test (/ pick ename)

 (if (and
       (setq pick (entsel))
       (setq ename (car pick))
     )
  (self-inters ename)
 )
)

 

0 Likes
Message 28 of 124

komondormrex
Mentor
Mentor

hey @john.uhden 

those of yours do not work / give t for that particular pline

 

komondormrex_0-1732375718567.png

 

0 Likes
Message 29 of 124

john.uhden
Mentor
Mentor

@komondormrex wrote "those of yours do not work..."

Could you explain what you mean by that?

Could you refer to each of the numbered conditions that "do not work?"

John F. Uhden

0 Likes
Message 30 of 124

АлексЮстасу
Advisor
Advisor

@john.uhden,

 

It's great that your new version can account for cases with arc segments.
It seems to me that your cases #6 and #8 are very similar - cases of touching, not full intersection. I would consider that #6 could also be a T.

 

In start_test_100-100_ju_test.dwg I have circled in yellow what your programme does not consider as self-intersections. Although, many cases are similar to your #7.

In Level 4_self-intersections_or_not.dwg it finds two self-intersections, but where there are none. And it doesn't find the cases I labelled.
In mill_pl.dwg with coordinates in millions for a smaller object, it finds many self-intersections, but they are not there.

 

But for a huge object with 4685 vertices it found both cases in 14 seconds. Of all the variants I found, this is the fastest speed.

 


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes
Message 31 of 124

АлексЮстасу
Advisor
Advisor

@Moshe-A,

 

In my start_test_100-100_lm_test.dwg I have circled in yellow what the Lee Mac function does not consider self-intersections. (Which I consider self-intersections or self-overlaps so far).

And in dark blue what the programme only gives one point.
In mill_pl.dwg with coordinates in millions for a smaller object it finds one self-intersection, but it is not there.
For the larger object I stopped waiting for the result after 7 minutes.

 

We in cartography sometimes have to work in coordinates in millions. And some lisp-functions do not work or give unexpected and strange results.
What can be the matter, in which lisp functions?

 


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes
Message 32 of 124

Moshe-A
Mentor
Mentor

@АлексЮстасу  hi,

 

finding self intersection is one thing finding overlapping is another. the function i send yesterday only finds self intersection.

if we are talking about millions of vertices\nodes, then i think you also should look for solution in the sharp c# \ object arx forums 

an application in latter, would be much faster than autolisp.

 

Moshe

 

0 Likes
Message 33 of 124

АлексЮстасу
Advisor
Advisor

Hi, @Moshe-A,

 

I wrote above that intersection and overlap are different. And in our function in #24 they are fixed and marked differently. However, it seems quite acceptable to find them with one function.

 

I wrote not about millions of vertices, but about coordinates with values in millions: 7600000.000, 6500000.000 or so on.
Some of the lisp functions or some actions in lisp do not accept such values correctly. For example, in the Lee Mac functions you cited.
But which ones?

 


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes
Message 34 of 124

Moshe-A
Mentor
Mentor

looking at "mill_pl.dwg" i thinking this is totaly crazy!!! a normal function must check each segment against all other 

you can not expect autolisp to find self intersections (+ overlapping) and do it in seconds - no way!

 

Moshe

 

0 Likes
Message 35 of 124

АлексЮстасу
Advisor
Advisor

@Moshe-A,

 

There are two very different problems with mill_pl.dwg: 1. speed and 2. incorrect results.

 

1. Using the @john.uhden, #26 and @Kent1Cooper, #2 functions as an example, we can assume that on lisp, analysing 4685 segments can be done in about 15 seconds. The lisp function BOZ, #15 does in about 25 seconds. But not a few minutes.

 

2. Incorrect functions results for objects with coordinates in millions. This problem is not related to self-intersections, it appears on quite other functions as well. Functions start producing incorrect results.
Self-intersection functions may show non-existent intersections. The function we use to get the centroid can put it outside the area. And so on.

 


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes
Message 36 of 124

АлексЮстасу
Advisor
Advisor

@john.uhden,

 

If move the polylines from mill_pl.dwg to coordinates closer to 0,0, your function stops giving the wrong result for the smaller polyline. But it starts to be wrong for the larger one - it gave me 347 self-intersections.

 


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes
Message 37 of 124

john.uhden
Mentor
Mentor

@АлексЮстасу ,

First, thank you so much for keeping interest in this thread.

True, there are still too many failures.

I have come up with a different approach, so stick around.

John F. Uhden

Message 38 of 124

daniel_cadext
Advisor
Advisor

IMHO, an interesting approach from an ARX/.NET perspective, is AcGeCurveCurveInt3d class. Once constructed, you can extract how (AcGeXConfig) curves intersect and or overlap. Some fancy footwork is needed for self-intersections, this Python sample uses AcGeCompositeCurve3d from the polyline, though one could investigate using individual components

 

 

from pyrx_imp import Rx, Ge, Gs, Gi, Db, Ap, Ed, Br
import traceback
from timeit import default_timer as timer

def PyRxCmd_doit():
    try:
        es, id, pnt = Ed.Editor.entSel("\nPick it: \n", Db.Polyline.desc())
        start = timer()
        pl = Db.Polyline(id)
        pntset = set(pl.toPoint3dList())  # vertex set

        # create CurveCurveInt3d from composit curves
        c1 = pl.getAcGeCurve()
        c2 = pl.getAcGeCurve()
        cc = Ge.CurveCurveInt3d(c1, c2)

        hits = []
        # iterate intersections
        for idx in range(0, cc.numIntPoints()):
            pnt = cc.intPoint(idx)

            # investigate how, I.e AcGeXConfig::kLeftRight
            config1wrt1, config1wrt2 = cc.getIntConfigs(idx)
            #print(config1wrt1, config1wrt2, pnt)

            if not (Ge.AcGeXConfig.kOverlapOverlap & config1wrt1
                and Ge.AcGeXConfig.kOverlapOverlap & config1wrt2):
                hits.append(pnt)

            if not pnt in pntset:
                hits.append(pnt)

        print(timer() - start)
        hits = set(hits)
        for p in hits:
            Ed.Core.grDrawCircle(p, 10, 10, 2)

    except Exception as err:
        traceback.print_exception(err)

 

 

inter1.png

inter2.png

Python for AutoCAD, Python wrappers for ARX https://github.com/CEXT-Dan/PyRx
Message 39 of 124

daniel_cadext
Advisor
Advisor

continuing the fun here

https://www.theswamp.org/index.php?topic=59870

Python for AutoCAD, Python wrappers for ARX https://github.com/CEXT-Dan/PyRx
0 Likes
Message 40 of 124

АлексЮстасу
Advisor
Advisor

@john.uhden,

It's great that you and other participants are ready to look for real solutions!
We are now making our own alternative solution too.
It will be the fastest and most correct for AutoCAD. 🙂
But it is very funny and almost cheating.

 

 


-- Alexander, private person, pacifist, english only with translator 🙂 --

Object-modeling _ odclass-odedit.com _ Help

0 Likes