Здравствуйте, wvk.
Спасибо за отклик.

wvk>Ты не упомянул об отбрасывании по минимальному расстоянию между охватывающими прямоугольниками.

Да, за истекшее время я уже нашел и реализовал такой критерий. Кстати, точнее — охватывающие параллелипипеды (у меня — 3D).

wvk>И тест на пересечение, я надеюсь не порёберная проверка.
С этого места, пожалуйста, подробнее?
Единственный окончательный критерий того, что они пересекаются, который я на данный момент осознал, такой: какое-либо ребро пересекает внутренность другого многоугольника. Вы знаете лучше? Подскажите, пожалуйста.
С другой стороны, я использую дополнительные проверки, которые во многих случаях "говорят", что они заведомо не пересекаются.

wvk>А так, для выпуклых, наверное только полным перебором пар вершин...
И ребер, как я уже писал.
И для невыпуклых, мне кажется, тут ничего не меняется.