speed up search of list

[Anonymous]

I have drawings with 1-200 circuit plines each with 1-500 vertexes.

There are also device blocks at the pline vertexes (10-10000).

I have several commands that look at specific plines and then find the devices on that pline.

My code finds all plines and creates a list of vertexes, then finds all device blocks and creates a list of the insertion point and entity name.

To find all blocks on a pline, I have been checking each vertex against the device coordinate list.

I have tried while, foreach and they are too slow when I start having more than 500 devices.

I am looking for a faster method of searching the lists.

Note -

blocks might be at several vertexes of multiple plines (so I can stop once I find a block)

the blocks might be just off the vertex by miniscule amount, so I have to use (equal P1 P2 0.00000000001) or (< (distance P1 P2) 0.00000000001)

Any help would be great!

[Kent1Cooper]

---

@Anonymous wrote:

....

I have several commands that look at specific plines and then find the devices on that pline.

My code finds all plines and creates a list of vertexes, then finds all device blocks and creates a list of the insertion point and entity name.

To find all blocks on a pline, I have been checking each vertex against the device coordinate list.

.... 

---

You should be able to significantly narrow down the quantity of Blocks you need to check against Polyline vertices by using the Polyline as a Fence for selection:

(ssget "_F" (list-of-a-Polyline's-vertex-points) '((0 . "INSERT")))

That way, you don't need to find all Blocks in the drawing, nor compare most of them to each Polyline's vertices, but look at only those that actually lie along it.  But it depends on any given Polyline not passing through any Blocks other than those inserted along it -- I would hope that circuiting drawings should be safe from that possibility.

Depending on your circumstances, you could further limit it by adding Block names and/or Layer names and/or scale factors to the (ssget) filter.

That could mislead if the Polylines might have arc segments, but not if Blocks can be located only at vertex locations, so it doesn't sound from your description like that will be an issue.

[dbroad]

Optimization might depend on what you have more of.  If you have fewer devices than verticies, you might get faster performance by working through the list of devices looking for plines.  If you have fewer plines/verticies, then parsing the plines might make more sense.

If I were trying to model a circuit with devices, I wouldn't be depending on proximity to determine connectivity.  I would use either dictionary or xdata relationships instead.  I would probably create a circuit, add the plines/lines/arcs and whatever that visually display the circuit and add the devices. Each device would have xdata for the handles representing connecting elements that relate to it.  Each connector would have xdata handles representing the devices the devices it connects.

Posting what you have along with a sample drawing might generate more responses.

[dgorsman]

My line of thinking as well.  If devices are always placed to a certain criteria (ie. must be on a circuit or circuits), control placement so the linking is done during placement.  Trying to dynamically work things out at the back end when that criteria isn't strict takes a lot more work since computers aren't great at "kinda-sorta" work.

[Anonymous]

Kent... that is an idea I had not thought of. I will give the fence selection a try. I don't use arcs in polylines, but I can't control what an end user does. I guess I can always check if there are arcs, then use the old (slower) method. Thanks!

[Anonymous]

Doug.. I originally started using xdata, but found that end users sometime take shortcuts of copying blocks instead of using the program to insert, so it broke the connectivity.

[Kent1Cooper]

---

@Anonymous wrote:
.... I don't use arcs in polylines, but I can't control what an end user does. I guess I can always check if there are arcs....

---

Arc segments will never be a problem if the Blocks are always at vertices, which it sounds like is the case from your original description.  They could be trouble only if Blocks might lie along the curve of an arc segment, away from a vertex, and if that arc segment bulges far enough that its chord [what the Fence approach will use] doesn't pass through the Block.  Or, if an arc segment might ever bulge far enough to pass through some Block that is associated with a different circuit path.

[Anonymous]

The blocks are always at the vertexes, never along a line. I haven't had time to modify code to Fence selection, but look forward to testing.

[martti.halminen]

If you go for high-end stuff, there is plenty of science and existing programs for this kind of stuff, Google for spatial search or spatial indexing.

One algorithm used for this: http://en.wikipedia.org/wiki/R-tree

- I haven't looked more closely a that, whether it would be feasible to implement it in AutoLISP.

If we stay at more modest approaches, the general approach for problems with combinatorial explosion is partitioning: it is often faster to run a thousand 1000-element searches than one million-element search.

- For this the fence selection idea sounds good. If it doesn't work, you could try others: if the individual plines don't stretch all over the drawing, you could find the bounding box of each, and check only against the blocks inside that box. Or you could try splitting the drawing into a 10x10 grid and handling each box separately, then combining the results.

-- 

[dbroad]

"dbroad

I originally started using xdata, but...."

Object reactors could be used to make up for CAD operators not following directions.  The :vlr-copied object could be used to manage the copying of devices if you decide to go that direction.

[Scottu2]

Mracad,

I found this to be an interesting problem.  The slow down is caused by storing the large lists as AutoCAD LIST objects.

And then creating a sorted LIST objects and another LIST object to hold the results.  

I have a suggestion, but it involves rewriting the code to use text files.

Create the vertices list but instead of adding to a LIST Object write the result as one line of text.

Close the file when all vertices are recorded.

Do the same with the device blocks.

I would also suggest that the files are writen as a TAB chr(9) delimited file (not CVS).

vertices-X TAB vertices-Y

vertices-X TAB vertices-Y

vertices-X TAB vertices-Y

vertices-X TAB vertices-Y

vertices-X TAB vertices-Y

Insert-X TAB Insert-Y TAB entity name

Insert-X TAB Insert-Y TAB entity name

Insert-X TAB Insert-Y TAB entity name

At this point open the files with Excel and sort the two files.

Then save them as a TAB text files.

In AutoCAD:

 Read one line of vertices file.

 Parse the string using the TAB chr(9) to separate the values if required.

 Compare it to each line read from the device block file.

 If the match is found then store the results in a LIST*.

 Repeat the comparison for each line in the vertices file.

* if the routine inserts a block (or object) at the vertex then place it on a Frozen Layer.

And when the routine is complete then turn on that layer to show the results.

Using files to emulate large AutoCAD LIST objects saves on memory space.

I hope this helps.

Scott

[stevor]

Even if the Blocks are inserted off a vertex,

Kent's Fence could be effective by either:

1 Testing each insert point for a matching vertex,

  by a SSGET; and correcting off base Inserts.

2. Making an offet fence,

which could also follow the arc-bulges

with segmented straddling.

[martti.halminen]

Another idea you might try: what happens if you don't collect all the devices, but just run SSGET at each vertex with a small pick box and filtering for the blocks?

- This might be a total stinker if the SSGET implementation is clumsy, but AutoCAD itself has to be pretty good at spatial indexing.

- This may have problems with the limits on the total number of selection sets, so you may need to free or re-use ssets.

-- 

[martti.halminen]

Given that RAM is several orders of magnitude faster than disk, I'd be really surprised if using text written on disk and re-parsed on input were faster than an in-memory approach.

-- 

[Scottu2]

I agree, RAM would be faster that a disk. Although, the original posting refers to a speed problem when the volume of data points increases. I have noticed a similar slowness problem with VBasic and list boxes when the data got larger.

[Scottu2]

martti,
The R-tree concept got me thinking.

If the vertices and device block lists are sorted, then cut the vertices list to 300 items, and then determine which device block fall within the x range of the vertices. The match can be made in small groups, like the boxes in the R-Tree.

The next vertices list only contains items 301-600, a re-scan of the device block list to find those that fit within the group.

The lists are then manageable, except the first Vertices list. That can be written to disk, sorted and then read back into the required group.

That would make the routine capable of large number of vertices.

[Anonymous]

I tried Kent's method of ssget "_F" and here are the results -

Total Number of lines = 362

Total Number of Vetexes on all lines = 5316

Total Number devices = 2292

Old method of search each line, then each vertex and then each block = 289 seconds (ouch!)

New method using get line, get vertexes on line, ssget "F" using list of vetexes, then search each vertex against smaller block list = 85 seconds.

I changed this to a subroutine to run this only once, storing the information for use by other programs.

If the user changes any plan data, they can rerun the subroutine.