Committed an update to GeomUtilTileTest.java that supports using a quad space (my fave
) to separate out the search domains for the combination. This works with the original test data with various settings so I'm thinking it probably works for all the cases it did before (let me know it thats not the case - there might be some corner cases between segments).
Performance wise it's a considerable improvement. I'm using the checker board case as probably the worst case. On my local test machine (dual core something or other):
50x50 Checker Board
Before with brute force: 1.8 seconds
After with quad space with 8x8 segments: 0.3 seconds
100x100 Checker Board
Before with brute force: 29.2 seconds
After with quad space with 8x8 segments: 1.9 seconds
With tiny maps that don't have much in the way of isolated bodies theres slight degradation due to having generate the quad space at all (I've left it so you can just swap between the two). The segment count needs tuning for the type of map but for 100x100 tiles 8x8 seems to be close to optimal.