покрытие прямоугольниками

incwizitor

нужна идея для решения _на практике_ (то бишь си++) такой задачи.
есть целочисленная сетка (плоскость).
есть огромное множество прямоугольников на это сетке со сторонами параллельно осям координат.
требуется удалить те из них, которые накрываются двумя другими прямоугольниками.
вообще говоря, конечно, хочется минимальное покрытие, но это не обязательно, так что речь идет об ослабленной задаче о покрытии.
то есть накрытия одним прямоугольником легко убираются.
если такие накрытия для двух прямоугольников смогу удалить, то этого вполне хватит (пусть даже какие-то остануться, не очень критично)
ссылочки и советы приветствуются.
да..речь конечно в первую очередь о скорости
оценочно прямоугольников миллион, наложений меньше 10 тысяч, времени не более 5 минут.

user6705

Можно все треугольники разбить на тройки. Внутри каждой тройки проверять сумму расстояний между центрами каждой пары прямоугольниковна равенство сумме их диагоналей.
Кстати, как у тебя прямоугольники задаются?

incwizitor

да я не ожидал, что кто-то поймет о чем речь.
прямоугольники задаются своими вершинами.
не понял о каких треугольниках идет речь..и какие-такие расстояния помогут решить проблему наложений ;(

incwizitor

ну-ка, где вы, умники ? ;-)
Оставить комментарий
Имя или ник:
Комментарий: