yade-users team mailing list archive

[Bruno Chareyre <bruno.chareyre@xxxxxxxxxxx>]

Hello,
> 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.

Bruno

>   


--

_______________
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
________________