You have two lists: ListA and ListB which contain references to instances of T_Thing. An object can be in either or both lists. You want to efficiently compare each member of ListA to each member of ListB. You dont want to compare members of A to A or B to B unless they are also in the other list.
My suggestion has two requirements:
1) A flag in T_Thing - say MemberOfListA. This will simply indicate which members of ListB are also in ListA.
2) (if not already) A unique Id or memory address such that between any two items one is considered 'higher' than the other. It doesn't matter which is higher just that they are in some order. It is *not* required that the lists be sorted by this Id.
Algorithm:
That's it. It still considers a * b items but only calls TestCollision the minimum number of times as requested. This is worth doing if the cost of TestCollision is relatively high.
Consider also doing a cheap initial collision test such as just bounding rectangles before a more expensive full test such as pixel perfect.
If you have some moderate to large number of items in one or both lists then there are much better approaches. For example pre-sorting the lists according to the bounding rectangles (say X order within Y order) and doing a skip list process. Probably the best for large cases would be Quad-tree (2D) or Oct-tree (3D). You spend some time preparing the data structure but more than make up for it by the comparisons that you don't have to perform.
Hope this helps.
My suggestion has two requirements:
1) A flag in T_Thing - say MemberOfListA. This will simply indicate which members of ListB are also in ListA.
2) (if not already) A unique Id or memory address such that between any two items one is considered 'higher' than the other. It doesn't matter which is higher just that they are in some order. It is *not* required that the lists be sorted by this Id.
Algorithm:
// First some initialisation. This is only required if the membership of ListA or ListB has changed since last pass // Set MemberOfListA off for all objects in ListB foreach (T_Thing item in ListB) item.MemberOfListA = false // Set MemberOfListA on for all objects in ListA foreach (T_Thing item in ListA) item.MemberOfListA = true // Now when we process ListB we'll know which objects will be checked anyway because they are also in ListA // Nested comparison loops foreach (T_Thing A in ListA) foreach (T_Thing B in ListB if A.Id == B.Id continue // Don't compare to self if B.MemberOfListA and B.Id < A.Id continue // The test will be performed the other way around if TestCollision(A, B) ... // Handle a collision
That's it. It still considers a * b items but only calls TestCollision the minimum number of times as requested. This is worth doing if the cost of TestCollision is relatively high.
Consider also doing a cheap initial collision test such as just bounding rectangles before a more expensive full test such as pixel perfect.
If you have some moderate to large number of items in one or both lists then there are much better approaches. For example pre-sorting the lists according to the bounding rectangles (say X order within Y order) and doing a skip list process. Probably the best for large cases would be Quad-tree (2D) or Oct-tree (3D). You spend some time preparing the data structure but more than make up for it by the comparisons that you don't have to perform.
Hope this helps.