hewih wrote:to avoid NxN checks i want to take the first element and check it against the rest, take the next and check it against the rest and so on. the result should be a "collision list" of collision pairs: ((box1 circle3) (circle7 circle3) (box2 circle7)). is there a existing function or idiom which handles these combinations?
This is something Lisp is naturally good at.
On first glance, I'd write something that takes a list as a required argument (I'll call it
inlist here), plus an optional argument that defaults to NIL, which I'll call
acc.
acc is an accumulator for the result.
If the cdr of the list is null, it'd return
acc.
Otherwise, it'd take the car of
inlist and iteratively check it for collisions against each element of
inlist's cdr, probably using mapcar or one of its immediate relatives - this may or may not be best accomplished via a helper function that takes an atom and a list and simply returns a list of collisions, possibly using delete-if. Either way, it would call itself on the cdr of
inlist and, if it found any collisions, it would append the list of collisions to
acc (using either nconc or append) and pass that as the second argument.
That should at least get you something that'll work, and that can be optimised later. It's also a generally useful idiom, which can be implemented either as a function accepting other functions as arguments, or as a macro. Paul Graham covered this patch of ground pretty well in
On Lisp, if you want to pursue it a bit further.