Printable View
How would i calculate a surface that up to 10^5 squares cover. The info you get is xpos,ypos and width for each square. How would you calculate the total surface covered (if any overlap only one counts).
Cannot use a big array of bools as the memory limit is 512 MiB.
Darn those pesky rules! they stop people like us giving away free completed code assignment work.Quote:
Cannot use a big array of bools as the memory limit is 512 MiB.
You could work out the w, h of the entire space that the squares sit in using the highest horizontal edge, leftmost vertical edge and the reverse of these for the lower corner of entire region, to obtain space topleft x,y space bottom right x,y . Then calculate that area. Then work out the 'unfilled' area of that space, and subtract that total from the whole region total. Whether you work on empty space or overlapping space its about breaking areas into other squares/rectangles - easy on pen and paper, harder in programming as you need to loop / recurse to detect edges.
thats my thoughts on going about it, but am sure there is some high school maths that simplifies an algorithm for it!
It's a very simplified version of collision detection. I'd try a sweep and prune algorithm (which you can read about on Google) to find all overlapping pairs, and subtract out the area of their overlap from the total sum of areas of each square.