Overlapping squares

This is a discussion on Overlapping squares within the C++ Programming forums, part of the General Programming Boards category; How would i calculate a surface that up to 10^5 squares cover. The info you get is xpos,ypos and width ...

  1. #1
    Registered User
    Join Date
    May 2013
    Posts
    12

    Overlapping squares

    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.

  2. #2
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,403
    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.

    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!
    Last edited by rogster001; 05-24-2013 at 01:14 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  3. #3
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    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.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Overlapping memory addresses in a struct :/
    By std10093 in forum C Programming
    Replies: 2
    Last Post: 11-02-2012, 08:50 AM
  2. Replies: 4
    Last Post: 05-02-2012, 10:22 PM
  3. Overlapping Memory
    By hammer1234 in forum C Programming
    Replies: 1
    Last Post: 04-05-2006, 03:05 AM
  4. Overlapping arrays problem
    By earth_angel in forum C++ Programming
    Replies: 4
    Last Post: 07-05-2005, 09:19 AM
  5. Overlapping toolbars
    By minesweeper in forum Windows Programming
    Replies: 3
    Last Post: 06-14-2003, 11:26 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21