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
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.
@АлексЮстасу 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
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.
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...
@АлексЮстасу 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
@АлексЮстасу , @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
@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)
)
)
@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
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.
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?
@АлексЮстасу 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
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?
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
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.
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.
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
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)
continuing the fun here
https://www.theswamp.org/index.php?topic=59870
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.
Can't find what you're looking for? Ask the community or share your knowledge.