yade-users team mailing list archive
Mailing list archive
Re: Contact detection
just a quick question on the contact detection method used by Yade
code. Well, looking at the sweep and prune algorithm actually I see that it
sorts the min and max coordinates of the bb. My question is: Why do we need to
extend the sorting to all the bb and not just for instance to bb close to each
The algorithm DO NOT extend the sorting to BB coordinates that are far
to each other. You don't need to compare each element to the full list
in this type of sorting.
For instance, if you need to sort this :
A C B D E F ....
You will compare :
- A vs. C : correct
- C vs. B : wrong -> move C
- B vs. C : correct
- C vs. D : correct
- D vs. E : correct
- E vs F : etc.
You will never compare A with Z.
In an arbitrary step of Yade (not the first one), you have an ordered
list with just a few elements to move, and you will only compare
coordinates that are close to each other.
I'm not claiming that the algorithm is perfect and I'm all for
improvement (and actually, I don't even know if it is still used in the
latest QuickSort collider), but at least it is not a N^2 algorithm.
Maître de Conférences
Laboratoire 3SR - bureau E145
BP 53 - 38041, Grenoble cedex 9 - France
Tél : 33 4 56 52 86 21
Fax : 33 4 76 82 70 43