Thread: Help me with this algorithm please

  1. #1
    Banned
    Join Date
    Mar 2008
    Posts
    78

    Help me with this algorithm please

    Picture: http://xs227.xs.to/xs227/08194/draw931.jpg

    I have this matrix where each cell has N of width and M of height. (I know they appear to have diferent sizes but paint s*cks :P)


    I have the values of p1 and p2 (x and y) given by p1[x] and p1[y], p2[x] and so on...

    I have the (x,y) of the center C (of every cell, not only the 10th one).

    I know the size of the whole matrix given by P(width) and Q(height).

    The objective is: To find out all areas that include that blue box.
    In this example areas 5 6 7 8 9 10 11 12 13 and 14 include it.

    The box can have various sizes..
    I cant find a good algorithm, can you help me? Thanks!

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Usually I tell people who seem to think they need to get to Calculus III before they can program not to fret, but I am going to have to go ahead and suggest a couple more math classes to you, or at least a few hours of online tutorials.

    If you know (x,y) is the center of an N by M square and you know which square (x,y) resides, you can certainly use basic algebra to calculate the absolute position of (x,y).

    Example:
    Code:
    In my example I am going to use some ascii art, and ignore your duplicate "5" square.
    
    Lets say you p2 is in some known relative location in square number 15.
    I hate 2d arrays so we can see that each row is 5N wide, thus a the row is mathematically,
    3M * 5N
    
    From there you can add the column which you desire, which in this case is the fourth one
    4N
    
    So we know you are dealing with square 3M * 5N + 4N (yes this could be simplified further, but we needn't mess with that now).
    That should get you started. On an important note: do not forget that when you are programming your geometry will be going the opposite direction and your counting will always be starting with 0.

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Since you know p1 and p2, you have their x & y values.

    Therefore, you get your minimum and maximum x values from p1 and p2, and get the min and max y values from p2.

    Then, if any square in your grid satisfies both conditions for x (min_x <= your square <= max_x) and the same for y, you have the answer you need.

    Todd
    Mainframe assembler programmer by trade. C coder when I can.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM