Нахождение пересечения второй степени из матрицы пересечения
У меня есть n прямоугольников, и мне нужно выяснить, сколько из них перекрывается. Что я сделал и создал матрицу пересечения, которая выглядит следующим образом для приведенного ниже JSON, где каждая запись представляет прямоугольник, а 1 - перекрытие. Это симметричная матрица, и я предположил, что прямоугольник перекрывает себя.
{
"rects": [
{"x": 100, "y": 100, "w": 250, "h": 80 },
{"x": 120, "y": 200, "w": 250, "h": 150 },
{"x": 140, "y": 160, "w": 250, "h": 100 },
{"x": 160, "y": 140, "w": 350, "h": 190 }
]
}
Теперь я знаю, что может быть 2 или более прямоугольников, перекрывающих друг друга. Как я могу найти их, используя эту матрицу пересечений? Или есть другой подход к этому?
например, 1,3,4 и 2,3,4