TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: 20060510412 on March 08, 2024, 02:54:10 AM

Title: How to get points within a specific distance of a polyline？
Post by: 20060510412 on March 08, 2024, 02:54:10 AM
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?
Title: Re: How to get points within a specific distance of a polyline？
Post by: ribarm on March 08, 2024, 03:23:41 AM
Consider using :

Code - Auto/Visual Lisp: [Select]
  1. (< (distance pt (vlax-curve-getclosestpointto lw pt)) distancefuzz)
  2.  
Title: Re: How to get points within a specific distance of a polyline&#38;#38;#38;#65311;
Post by: 20060510412 on March 08, 2024, 03:40:48 AM
Quote from: ribarm on March 08, 2024, 03:23:41 AM
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?
Title: Re: How to get points within a specific distance of a polyline&#38;#38;#65311;
Post by: Peter2 on March 08, 2024, 07:39:39 AM
What is efficiency? Half a second? Half a minute? Half an hour?

IMHO this is the best way and easy to use. Try it ...
Title: Re: How to get points within a specific distance of a polyline&#38;#38;#65311;
Post by: It's Alive! on March 08, 2024, 07:52:31 AM
post a sample drawing
Title: Re: How to get points within a specific distance of a polyline&#38;#38;#65311;
Post by: kdub_nz on March 08, 2024, 08:00:49 PM
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,
Title: Re: How to get points within a specific distance of a polyline&#38;#38;#65311;
Post by: It's Alive! on March 08, 2024, 08:22:08 PM
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.  

Quote
Enter a distance: 200
7534, 0.27800893783569336 seconds
Title: Re: How to get points within a specific distance of a polyline&#38;#38;#38;#38;#65311;
Post by: 20060510412 on March 09, 2024, 07:59:26 PM
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.




Quote from: It's Alive! on March 08, 2024, 08:22:08 PM
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.  

Quote
Enter a distance: 200
7534, 0.27800893783569336 seconds
Title: Re: How to get points within a specific distance of a polyline&#38;#38;#65311;
Post by: It's Alive! on March 09, 2024, 08:38:38 PM
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!
Title: Re: How to get points within a specific distance of a polyline&#38;#38;#65311;
Post by: xdcad on March 28, 2024, 03:57:51 PM
Quote from: 20060510412 on March 08, 2024, 02:54:10 AM
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?