topic Re: Polylines: touching or crossing in Visual LISP, AutoLISP and General Customization Forum

Polylines: touching or crossing

doaiena — Thu, 02 May 2019 21:05:19 GMT

Hello,

I am currently looking for a way to find out, whether 2 polylines are touching, or crossing each other. I have tried the "vla-intersectwith" method, but it returns an output in both cases. I don't want to use bounding boxes, as it would give false results, depending on the polylines' shapes.

I've spent a few hours on google, looking for an answer, but didn't find anything. I would be very thankfull if you could send some ideas my way, on how to approach the matter.

Thank you.

Re: Polylines: touching or crossing

devitg — Thu, 02 May 2019 22:57:43 GMT

You can check for each poly , for eachintersectpoint , by (vlax-curve-getParamAtPoint poly b) If any of it give you a Whole par value

Re: Polylines: touching or crossing

doaiena — Thu, 02 May 2019 23:57:25 GMT

That idea went through my mind at one point, but i wrote it off, because it will only work for rectangles. A whole parameter value indicates a vertex, which would work in cases, where one of the polylines touches the other with a vertex /or multiple verteces/.

Maybe my initial image wasn't a good example. I want to find out, whether the 2 plines are touching each other, regardless if it's at a vertex or not.

Re: Polylines: touching or crossing

devitg — Fri, 03 May 2019 00:09:50 GMT

You can check if there is more than one intersection and no (-par (fix par)) is = 0 [cross] and , or if there is only one intersection [touch] or if are more than 1 par and all are (= 0 (-par (fix par))) [touch] ,or no intersection [none]

Re: Polylines: touching or crossing

doaiena — Fri, 03 May 2019 00:08:19 GMT

In the first image /with the 2 rectangles/, there are 2 intersection points in both cases. Thats what i find weird about the "vla-intersectwith" method. I thought that the output would be different when the polylines are touching each other, not only at 2 points, but a long a certain length.

Re: Polylines: touching or crossing

devitg — Fri, 03 May 2019 00:12:56 GMT

ePlease check post 4 , I edited. the fact , is to check for intersection-s , and par at this those intersection-s

Re: Polylines: touching or crossing

doaiena — Fri, 03 May 2019 00:41:25 GMT

First of all i want to thank you for your ideas. I really appreciate your help.

Maybe my brain isn't working at the moment, so i can't quite get your idea. (- par (fix par)) would give me the parameter of the touch/cross, for the pline segment. At the moment i can't think of a way that is usefull for me.

Btw i just made another example of touching and crossing plines, both with 2 points, and both not on verteces, and i can't think of a way do differentiate the two.

Re: Polylines: touching or crossing

devitg — Fri, 03 May 2019 01:17:58 GMT

(= 0(- par (fix par))) will be T , for one or more touching points are at vertex if so.

For your 2 touching rectangle you will get 2 PARam as INT as 1.00 and 2.00 or 1 and 2

For your cross rectangle you will get 4 PARam , no one will fit (= 0(- par (fix par)))

For the 3 case an arc touching the poly you will get ONLY one intersection so IT TOUCH , no matter about PARam If no intersection , neither touch or cross.

For the 4 case , it had to be think

As ever, you and most poster , do not show all the cases.

Re: Polylines: touching or crossing

doaiena — Fri, 03 May 2019 01:04:10 GMT

The problem is, i myself don't know all the cases. I post, as i think of a new case. The basic idea was to be able to find out whether the plines are touching or crossing, no matter the shapes or point/points of contact.

Re: Polylines: touching or crossing

devitg — Fri, 03 May 2019 01:07:12 GMT

Ok, i'm thinkin about no vertex is touching

Re: Polylines: touching or crossing

Kent1Cooper — Fri, 03 May 2019 01:55:11 GMT

Are the likely shapes "ordinary" enough, and is the degree of overlap [if any] smallish compared to the sizes, as in your examples, and would there not be other stuff around inside the shapes? If so, you could find the centroids or middles of bounding boxes, use those as internal-pick points for BOUNDARY commands, and compare the areas of the results to the areas of the originals. If the originals touch but don't overlap, there will be something returned by the (intersectwith) method, but the BOUNDARY results will have the same areas as the originals, no matter how many points of intersection or how much length of coincident edge(s) there may be. If the originals overlap, the BOUNDARY results would each have a smaller area than its corresponding original, no matter how many points of intersection there are.

Re: Polylines: touching or crossing

phanaem — Fri, 03 May 2019 06:24:17 GMT

First, check for intersections with vla method.

Now check if the points between every 2 consecutive intersections of one polyline are inside/outside the other polyline.

Based on the alternation inside/outside, you can establish the relative position of the 2 polys.

Now you only need a good inside_p function 🙂 I guess you'll find some in this forum.

See the image for demonstration. Notice it doesn't matter which polyline is checked against the other.

Re: Polylines: touching or crossing

doaiena — Fri, 03 May 2019 11:49:19 GMT

@Kent1Cooper : As you have pointed out, picking a point for a boundary is not reliable in all cases /depending on the plines' shapes/. I thought of something similar, that doesnt rely on picking points, but i was sure there must be a more straight forward way to perform this check.

My idea was:

1. Region the plines.

2. Intersect.

3. If there is any geometry left over, the 2 plines are crossing /erase the remaining region/; else they are just touching.

@phanaem : That's an interesting idea. I haven't thought it through, but at a glance, it might work.

Re: Polylines: touching or crossing

Kent1Cooper — Fri, 03 May 2019 12:17:07 GMT

Further questions....

Are you talking about only and always closed Polylines? Or other closed shapes [Circles, Ellipses, Splines]? If so, there's one definitive condition: if there's only one intersection, that means they touch but do not overlap, so no further analysis would be needed.

And what about shapes that overlap but do not intersect?

Re: Polylines: touching or crossing

devitg — Fri, 03 May 2019 12:20:30 GMT

For 2 rectangles touched side by side , it will be 2 intersections.

See the first post,please

It have 2 case , rectangles overlapping , and rectangles touching

Re: Polylines: touching or crossing

doaiena — Fri, 03 May 2019 12:37:35 GMT

Yes, i am talking about closed polylines. I wanted to know whether 2 plines are touching or crossing each other. It doesn't matter if one of the plines is inside or outside the other one.

In the 1-st and 3-rd images in this thread, are cases where the plines produce 2 intersection points, both for crossing and touching.

Re: Polylines: touching or crossing

Kent1Cooper — Fri, 03 May 2019 12:47:41 GMT

@doaiena wrote:

....
In the 1-st and 3-rd images in this thread, are cases where the plines produce 2 intersection points, both for crossing and touching.

Yes, and the upper one in Message 3 is what I was talking about -- one intersection, so you don't need to bother analyzing whether they simply touch or overlap [as you would if there are more than one intersection], because if they're both closed, one intersection can only mean that they touch without overlapping.

Re: Polylines: touching or crossing

doaiena — Fri, 03 May 2019 20:42:34 GMT

@phanaem : I turned your suggestion into code, and it seems to be working. So far it gives correct results on all of the test cases i throw at it. Thank you for the interesting idea.

Re: Polylines: touching or crossing

devitg — Fri, 03 May 2019 20:46:23 GMT

Hi doaiena , would you please , share your Lisp code.

If you want , you can send me to my email

myusernamehere at gmail

Re: Polylines: touching or crossing

doaiena — Fri, 03 May 2019 21:44:39 GMT

Offcourse, i will share it with everyone. It's not ready though. The code is not optimal, but i wrote it in a hurry, to test if this approach works. I commented the code, so that at least you can follow the logic somewhat. If you want, you can streamline and optimize the code, and post a better version.

(defun c:test ( / obj1 obj2 acadmodel inter interPts pts result)

;NEEDS ERROR HANDLER

;select 2 closed polylines
(while (not obj1) (setq obj1 (car (entsel "\nSelect first polyline: "))))
(while (not obj2) (setq obj2 (car (entsel "\nSelect second polyline: "))))
(setq obj1 (vlax-ename->vla-object obj1))
(setq obj2 (vlax-ename->vla-object obj2))
(setq acadmodel (vla-get-modelspace (vla-get-activedocument (vlax-get-acad-object))))
(setq result "\nThe polylines do NOT touch")

;NEEDS TO BE ADDED:
;- restrict selection to polylines only
;- check if plines are closed - vlax-curve-isClosed


;check for intersection between the 2 plines
(setq inter (vlax-invoke obj1 'intersectwith obj2 acExtendNone))

;group intersection result into list of points
(repeat (/ (length inter) 3)
(setq result "\nThe polylines TOUCH")
(setq interPts (cons (list (car inter) (cadr inter) (caddr inter)) interPts))
(setq inter (cdddr inter))
)

;group the intersection points into pairs

;group first and last point if there are more than 2 points
(if (> (length interPts) 2)
(setq pts (cons (list (last interPts) (car interPts)) pts))
)

;group the remaining pairs of points
(while (> (length interPts) 1)
(setq pts (cons (list (car interPts) (cadr interPts)) pts))
(setq interPts (cdr interPts))
)

;if there is at least 1 pair of points
(if (> (length pts) 0)
(progn

;check if the pair of points are because of touching or crossing
(mapcar '(lambda ( x / pt1 pt2 pr1 pr2 prStart prEnd ptStart ptEnd prMid1 prMid2 ptMid1 ptMid2)

(setq pt1 (car x) pt2 (cadr x))
(setq pr1 (vlax-curve-getparamatpoint obj1 pt1))
(setq pr2 (vlax-curve-getparamatpoint obj1 pt2))
(setq prStart (vlax-curve-getStartParam obj1))
(setq prEnd (vlax-curve-getEndParam obj1))
(setq ptStart (vlax-curve-getpointatParam obj1 prStart))
(setq ptEnd (vlax-curve-getpointatParam obj1 prEnd))

;comment:
;on a closed pline the start and end parameter share the same point
;so if the start/end vertex is part of the calculation
;vlax-curve-getparamatpoint doesn't always return the correct parameter
;the cond statement below takes care of that

;get the parameters between the 2 points on each side
(cond
;if the first intersection point is the start/end vertex
((equal pt1 ptStart)
(setq prMid1 (+ (/ (abs (- prStart pr2)) 2) (min prStart pr2)))
(setq prMid2 (+ (/ (abs (- prEnd pr2)) 2) (min prEnd pr2)))
)
;if the second intersection point is the start/end vertex
((equal pt2 ptStart)
(setq prMid1 (+ (/ (abs (- pr1 prStart)) 2) (min pr1 prStart)))
(setq prMid2 (+ (/ (abs (- pr1 prEnd)) 2) (min pr1 prEnd)))
)
;if the intersection points DONT lie on the start/end vertex
(t
(setq prMid1 (+ (/ (abs (- pr1 pr2)) 2) (min pr1 pr2)))
(setq prMid2 (+ (+ (/ (abs (- pr1 pr2)) 2) (min pr1 pr2)) (/ prEnd 2)))
(if (> prMid2 prEnd) (setq prMid2 (- prMid2 prEnd)))
)
);cond

;get the points of the 2 mid parameters
(setq ptMid1 (vlax-curve-getpointatparam obj1 prMid1))
(setq ptMid2 (vlax-curve-getpointatparam obj1 prMid2))

;check if either of the mid points are inside the polyline using ray casting
(mapcar '(lambda (pt / pt2 ray inter)

(setq pt2 (vlax-curve-getclosestpointto obj2 pt))
(if (not (equal pt pt2 0.0001))
(progn
(setq ray (vla-addray acadmodel (vlax-3D-point pt) (vlax-3D-point pt2)))
(setq inter (vlax-invoke ray 'intersectwith obj2 acExtendNone))
(vla-delete ray)
(if (equal (rem (length inter) 2) 1) (setq result "\nThe polylines CROSS"))
))
)
(list ptMid1 ptMid2)
);mapcar

)
pts
);mapcar

));if 2 points intersect

(princ result)
(princ)
);defun