← Back to team overview

yade-users team 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 others?
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.



Chareyre Bruno
Maître de Conférences

Grenoble INP
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

Follow ups