Request for Reducing Time Complexity in my code.

[j2lstaples]

Hello everyone,

I'm back here again because I've hit a stumbling block in my code. I have the following code:

 

; Intersections in Set
; returns a list of intersection output with the selected intersection function/method.
(defun MA:intersectionsinset (sel tol / id1 id2 ob1 ob2 rtn) 
  (repeat (setq id1 (sslength sel)) 
    (setq ob1 (ssname sel (setq id1 (1- id1))))
    (repeat (setq id2 id1) 
      (setq ob2 (ssname sel (setq id2 (1- id2)))
            rtn (cons (MA:endptintersections ob1 ob2 tol) rtn)
      )
    )
  )
  (apply 'append (reverse rtn))
)

 

I have a selection set sel and I process a repeating process for each item in the selection set. 

So, what I did was to process the last item in comparison to the rest of the list, remove that item from the list and then repeat until I exhaust the selection set.

So basically, what this does is compare item n with item n-1 until item 1, then compare item n-1 with item n-2 until item 1, etc.

So, the calculations would take: n(n-1)/2. For example with a selection set that has 188 objects, it would need to take 17578 calculations. 

 

If I could use C:FS, which is Fast Select, it would probably let this function go way faster than usual. It only makes sense for MA:entptintersections to only work with ob1 and ob2 that has intersections and FS can do this really quickly. However, (C:FS) requires user input. I don't want to use user input cause that doesn't make any sense. 

 

If I could do something like

(setq sel1 (C:FS ob1))
(repeat (sslength sel1)
	....

It would reduce the list that each item sees/processes with. I can't seem to find how FS works.

[dan20047]

Take a look at CAB's routine which breaks all selected objects at intersection. I assume he figured out some efficiency

http://www.theswamp.org/index.php?topic=10370.0

 

[j2lstaples]

3 minutes ago, dan20047 said:

Take a look at CAB's routine which breaks all selected objects at intersection. I assume he figured out some efficiency

http://www.theswamp.org/index.php?topic=10370.0

 

I'm not really trying to break anything really. 

 

Maybe I'm thinking about this too widely and shallow. I guess a better way is to create a fence line creator for each (ssname sel id1), that will give me a fence selection argument so that it's only going to process nearby objects. This exhaustive list is going to be terrible to scale. 

[Steven P]

I have done something similar I think which works for lines:

- Make a 'master' selection set, sel

- Repeat through each item in that list, remove the item as you go

- Create a second selection set using the points of the line using 'crossing' as a filter. The points are the end points of the line offset slightly at each end (mapcar '+ '( 0.1 0.1 0) point)

Which should give you every object crossing that entity and which should be a smaller list to calculate

- MHUPPs code below creates a selection set which is the intersection of 2 selection sets, what is in sel and your crossing selection set.

and then you can work on that much smaller set

 

 

 

[j2lstaples]

2 minutes ago, Steven P said:

I have done something similar I think which works for lines:

- Make a 'master' selection set, sel

- Repeat through each item in that list, remove the item as you go

- Create a second selection set using the points of the line using 'crossing' as a filter. The points are the end points of the line offset slightly at each end (mapcar '+ '( 0.1 0.1 0) point)

Which should give you every object crossing that entity and which should be a smaller list to calculate

- MHUPPs code below creates a selection set which is the intersection of 2 selection sets, what is in sel and your crossing selection set.

and then you can work on that much smaller set

 

 

 

 

Yeah, I thought of a similar solution as you, but I'm working with blocks. I need to create a function that converts that block into a set of points so I can maybe use a fence selection. I'm still mulling over this since I don't want to do exhaustive processing. What I'm thinking is something like this:

(setq sel1 (LM:ss->ent sel))
(repeat (setq id1 (sslength sel))
	(setq id1 (1- id1))
	(setq ob1 (car (reverse sel1)))
    (setq sel1 (reverse (cdr (reverse sel1)))) ; remove the last entity from list
	(setq fpoints (fencepoints ob1)) ; generate fence points list for ssget
	(setq sel2 (ssget "_F" fpoints))
    (setq sel2 (LM:ss->ent sel2))
	(setq sel3 (and_list sel2 sel1)) ; reduces the list from sel2 to sel3 that only exists in sel1
    (setq id2 -1)
    (repeat (length sel3)
    	(setq ob2 (nth (setq id2 (1+ id2)) sel3)
        	  rtn (cons (MA:endptintersections ob1 ob2 tol) rtn
        )
    )
)
(apply 'append (reverse rtn))

 

[Steven P]

something like that yes, 

[BIGAL]

I use CAB breakall and its instant result, make a copy and look at finding the intersection point maybe try rather than Break use POINT. 

 

Try changing this its multiple times.
(command "._break" obj2break "_non" (trans brkpt 0 1) "_non" (trans p2 0 1))

(command "POINT"  "_non" (trans brkpt 0 1) )
not tested maybe use (trans p2 0 1)