Удобный интерфейс к GEOS может быть библиотекой, для которой вы ищете, но я никогда не использовал ее для этой цели.
В этом случае может быть проще катиться самостоятельно. Алгоритм представляет собой простой алгоритм развертки, со средней сложностью на прямоугольник, пропорциональный log (N).
A) Каждый прямоугольник характеризуется четырьмя координатами: слева, справа, сверху, снизу.
В) Прямоугольники будут обработаны в порядке их левых координат
с) Интервал Дерево используется для поддержания верх-низ диапазоны для каждого прямоугольника, левый край был получен и правый край не имеет еще встречались
D) приоритетную очередь поддерживается, упорядочены по правому краю, из всех прямоугольников, которые в настоящее время находятся в интервале Tree
1) Получить первый или следующий прямоугольник который должен быть обработан. Если больше нет, выйдите.
2) Хотя любой элемент в очереди приоритетов имеет приоритет, меньший или равный левому значению этого прямоугольника, удалите этот элемент из очереди приоритета и связанного с ним элемента из дерева интервалов.
3) Найдите Дерево интервала для перекрытия с диапазоном Top-Bottom этого прямоугольника; обрабатывать каждое совпадение.
4) Вставьте верхний нижний диапазон этого прямоугольника в Дерево интервала и добавьте элемент в очередь приоритетов с приоритетом, установленным справа от прямоугольника, ссылаясь на интервал, добавленный в Дерево интервала ,
5) Вернитесь к шагу 1), чтобы получить следующий прямоугольник.
Можете ли вы объяснить, что представляют собой эти прямоугольники? Эти изображения, которые ваша программа должна распознать? Можете ли вы добавить такое изображение в качестве примера? – physicalattraction
@physicalattraction - это простой список прямоугольников в виде координат типа прямоугольников (0,0,2,2). Ничто не связано с распознаванием образов, но сложный бит будет эффективно определять, является ли перекрытие между N прямоугольниками и объединить их в один или несколько неперекрывающихся прямоугольников. – ttback
Хорошо, вижу. У вас есть массив «ящиков» с каждым из четырех кортежей с координатами (левый, верхний, правый, нижний), и теперь вам нужен эффективный алгоритм, который проверяет, перекрываются ли определенные прямоугольники. Я понимаю проблему сейчас, но, к сожалению, я не могу помочь вам в ответе, поскольку я не знаю о такой библиотечной функции. – physicalattraction