Jump to content

Request for Reducing Time Complexity in my code.


j2lstaples

Recommended Posts

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.

Link to comment
Share on other sites

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. 

Link to comment
Share on other sites

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

 

 

 

Link to comment
Share on other sites

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))

 

  • Like 1
Link to comment
Share on other sites

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)

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...