Thread: Help me with this algorithm please

  1. #1
    Join Date
    Mar 2008

    Help me with this algorithm please


    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
    Visalia, CA, USA
    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).

    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
    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
    Katy, Texas
    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.

    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

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
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM