So führen Sie einen rechteckigen Treffer-Test in PHP

Question

Ich habe WYSIWYG-Stil Javascript-Schnittstelle, mit der ein Designer rechteckige Bereiche erstellen können, um eine Dokument-Server-Seite zu generieren. Es ist wichtig, dass diese Regionen nicht überlappen.

Ich frage mich, was ist der einzige effizienteste Weg, um einen Hit-Test auf 2 rechteckigen Regionen durchzuführen, könnte es möglicherweise Hunderte sein, so ist Effizienz eine hohe Priorität.

Ich möchte die gleiche Funktionalität in Javascript-Client-Seite und PHP-Server-Seite, so dass ein Algorithmus/PDL-Snippet wäre großartig.

Dank

Answer 1

Ich empfehle eine intelligente Datenstruktur, wie ein R-Tree oder ein Quad Tree zu verwenden.