CODEWITHSUNDEEP
algorithmintersection
Gumeni Pero
Gumeni Pero

Reputation: 1

N rectangle intersection

Consider set of n axis-parallel rectangles. Brute-force algorithm is to check does one rectangle intersect with others and complexity is O(n^2). Is there any algorithm with complexity of O(nlogn) for finding all intersections between these set of rectangles?

Second question is how to find rectangles that are inside other rectangle in given set of rectangles also with complexity O(nlogn)?

Upvotes: 0

Views: 128

Answers (1)

Diniden
Diniden

Reputation: 1125

Look into Quad Trees or axis aligned bounding box broadphase for hit detection.

These are typical game usage / physics engine systems for rectangle hit detection.

Upvotes: 2

Related Questions