How to perform a rectangular hit test in PHP

Question

Hi,

I have WYSIWYG style javascript interface that allows a designer to create rectangular regions to generate a document server side. It is important that these regions do not overlap.

I was wondering what is the single most efficent way to perform a hit test on 2 rectangular regions, there could potentially be hundreds, so efficency is a high priority.

I want to implement the same functionality in Javascript client side, and PHP server side, so an algorithm / PDL snippet would be great.

Thanks

Answer 1

I recommend to use some smart data structure, such as an R-Tree, or a Quad Tree.