Topic: How to get points within a specific distance of a polyline？

[20060510412]

In a dwg file, there are many points and a polyline. I would like to get the points that are within a certain distance from the polyline.

Currently, I have considered the following solutions:

1.Using a global traversal can definitely solve the problem, but the efficiency is too low.

2.Another method is to use the offset function to obtain a closed area and then use ssget for filtering. However, this method may not work well when the polyline shape is complex.

Can algorithms like quadtree be used to achieve this purpose?

[ribarm]

Consider using :

Code - Auto/Visual Lisp: [Select]

1. (< (distance pt (vlax-curve-getclosestpointto lw pt)) distancefuzz)
2.  

[20060510412]

Consider using :

Code - Auto/Visual Lisp: [Select]

1. (< (distance pt (vlax-curve-getclosestpointto lw pt)) distancefuzz)
2.  

If there are 20000 points，Is the efficiency of this method too low?

[Peter2]

What is efficiency? Half a second? Half a minute? Half an hour?

IMHO this is the best way and easy to use. Try it ...

[It's Alive!]

post a sample drawing

[kdub_nz]

Another consideration is :
Do you want to do all this without user interaction
or would the user select the polyline and ( possibly ) select a window area for the candidate points ??

If candidates can be selected the process would be much simpler and faster.

>>> If there are 20000 points，Is the efficiency of this method too low?

For instance, this number could be reduced considerably.

If the process is a black box ( sight unseen, no interaction ) any arbitrary choice ( like an expanding selection area based on the polyline bounding box ) would probably be slower than a programatic selection and test of all points.

Though, I s'pose the complexity of buildibg a selection area around the polyline would depend on the shape of the polyline.

Knowing the usecase would assist in designing a solution [ the first consideration would be how often the routine is used ]
my gut says get it working first , then test if the speed seems acceptable for you before looking for optimisations.

Regards,

[It's Alive!]

getClosestPointTo is going to be pretty fast, this is with python, but lisp should be as fast

this is 100,000 points

Code - Python: [Select]

1. def PyRxCmd_doit2() -> None:
2.     try:
3.         filter = [(Db.DxfCode.kDxfStart, "POINT")]
4.         sspointres: tuple[Ed.PromptStatus, Ed.SelectionSet] = Ed.Editor.select(filter)
5.         if sspointres[0] != Ed.PromptStatus.eOk:
6.             print("Oops {}: ".format(sspointres[0]))
7.             return
8.  
9.         esplineres = Ed.Editor.entSel("\nPick a pline: ", Db.Polyline.desc())
10.         if esplineres[0] != Ed.PromptStatus.eOk:
11.             print("Oops {}: ".format(esplineres[0]))
12.             return
13.  
14.         distres = Ed.Editor.getReal("\nEnter a distance: ")
15.         if distres[0] != Ed.PromptStatus.eOk:
16.             print("Oops {}: ".format(distres[0]))
17.             return
18.        
19.         start = time.time()
20.  
21.         pline = Db.Polyline(esplineres[1])
22.         pnts = [Db.Point(id).position() for id in sspointres[1].objectIds()]
23.        
24.         close = []
25.         for p in pnts:
26.             x = pline.getClosestPointTo(p)
27.             if x.distanceTo(p) <=distres[1]:
28.                 close.append((p,x))
29.                  
30.         print(len(close), time.time() - start)
31.        
32.         for item in close:
33.             Ed.Core.grDraw(item[0], item[1], 4,0)
34.        
35.     except Exception as err:
36.         traceback.print_exception(err)
37.  
38.  

Enter a distance: 200
7534, 0.27800893783569336 seconds

[20060510412]

Thank you all for your help.
I just thought that it is unnecessary to traverse every point. Comparatively, the quadtree algorithm should be more efficient.
Of course,  I found that implementing a quadtree in Lisp is not quite suitable.

getClosestPointTo is going to be pretty fast, this is with python, but lisp should be as fast

this is 100,000 points

Code - Python: [Select]

1. def PyRxCmd_doit2() -> None:
2.     try:
3.         filter = [(Db.DxfCode.kDxfStart, "POINT")]
4.         sspointres: tuple[Ed.PromptStatus, Ed.SelectionSet] = Ed.Editor.select(filter)
5.         if sspointres[0] != Ed.PromptStatus.eOk:
6.             print("Oops {}: ".format(sspointres[0]))
7.             return
8.  
9.         esplineres = Ed.Editor.entSel("\nPick a pline: ", Db.Polyline.desc())
10.         if esplineres[0] != Ed.PromptStatus.eOk:
11.             print("Oops {}: ".format(esplineres[0]))
12.             return
13.  
14.         distres = Ed.Editor.getReal("\nEnter a distance: ")
15.         if distres[0] != Ed.PromptStatus.eOk:
16.             print("Oops {}: ".format(distres[0]))
17.             return
18.        
19.         start = time.time()
20.  
21.         pline = Db.Polyline(esplineres[1])
22.         pnts = [Db.Point(id).position() for id in sspointres[1].objectIds()]
23.        
24.         close = []
25.         for p in pnts:
26.             x = pline.getClosestPointTo(p)
27.             if x.distanceTo(p) <=distres[1]:
28.                 close.append((p,x))
29.                  
30.         print(len(close), time.time() - start)
31.        
32.         for item in close:
33.             Ed.Core.grDraw(item[0], item[1], 4,0)
34.        
35.     except Exception as err:
36.         traceback.print_exception(err)
37.  
38.  

Enter a distance: 200
7534, 0.27800893783569336 seconds

[It's Alive!]

you would have to touch each point to insert it into a tree.
A tree would probably be better in some cases, i.e. for multiple searches.
But then you must maintain a state.

Anyway, welcome to the swamp!

[xdcad]

In a dwg file, there are many points and a polyline. I would like to get the points that are within a certain distance from the polyline.

Currently, I have considered the following solutions:

1.Using a global traversal can definitely solve the problem, but the efficiency is too low.

2.Another method is to use the offset function to obtain a closed area and then use ssget for filtering. However, this method may not work well when the polyline shape is complex.

Can algorithms like quadtree be used to achieve this purpose?

n points, one polyline?

Then if you traverse the points globally and obtain the points within the tolerance range, the time complexity of the algorithm is n. How come it is inefficient?