Rectangle intersection

Discussion in 'C Programming' started by kimos, Sep 25, 2004.

  1. kimos

    kimos Guest

    hi all,

    how to calculate the intersection of 2 rectangle

    a rectangle is the following:

    Rectangle makeRectangle (Point lowerLeft, Point upperRight) {

    Rectangle r;

    r.pt1 = lowerLeft;
    r.pt2 = upperRight;
    return r;
    }

    and Point is the following:

    Point makePoint(int x, int y) {
    Point p;
    p.x = x;
    p.y = y;
    return p;
    }


    And i want the know how to make:

    Rectangle intersection(Rectangle r1, Rectangle r2)

    this should return the intersection of the 2 rectangles
    anyone can help me plz?
     
    kimos, Sep 25, 2004
    #1
    1. Advertising

  2. kimos <> scribbled the following:
    > hi all,


    > how to calculate the intersection of 2 rectangle


    > a rectangle is the following:


    > Rectangle makeRectangle (Point lowerLeft, Point upperRight) {
    >
    > Rectangle r;


    > r.pt1 = lowerLeft;
    > r.pt2 = upperRight;
    > return r;
    > }


    > and Point is the following:


    > Point makePoint(int x, int y) {
    > Point p;
    > p.x = x;
    > p.y = y;
    > return p;
    > }



    > And i want the know how to make:


    > Rectangle intersection(Rectangle r1, Rectangle r2)


    > this should return the intersection of the 2 rectangles
    > anyone can help me plz?


    Which part are you having trouble with, calculating the intersection's
    coordinates or implementing the algorithm as a C program?

    --
    /-- Joona Palaste () ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "Immanuel Kant but Genghis Khan."
    - The Official Graffitist's Handbook
     
    Joona I Palaste, Sep 25, 2004
    #2
    1. Advertising

  3. kimos

    Malcolm Guest

    "kimos" <> wrote in message
    news:...
    > hi all,
    >
    > how to calculate the intersection of 2 rectangle
    >
    > a rectangle is the following:
    >
    > Rectangle makeRectangle (Point lowerLeft, Point upperRight) {
    >
    > Rectangle r;
    >
    > r.pt1 = lowerLeft;
    > r.pt2 = upperRight;
    > return r;
    > }
    >
    > and Point is the following:
    >
    > Point makePoint(int x, int y) {
    > Point p;
    > p.x = x;
    > p.y = y;
    > return p;
    > }
    >
    >
    > And i want the know how to make:
    >
    > Rectangle intersection(Rectangle r1, Rectangle r2)
    >
    > this should return the intersection of the 2 rectangles
    > anyone can help me plz?
    >


    Rectangle intersection(Rectangle r1, Rectangle r2)
    {
    Find the leftmost and the bottommost rectangle.
    Find the rightmost and the topmost rectangle.

    If the left x co-ordinate of the non-leftmost rectangle is between the
    left and the right of the leftmost rectangle, you have the left cordinate of
    your intersection. If it is to the right you have no intersection, and the
    rectangles don't overlap. (If it is to the left you didn't calculate the
    leftmost rectangle correctly).

    Repeat for all the other coordinates (bottom, right, top).
    }
     
    Malcolm, Sep 25, 2004
    #3
  4. kimos <> wrote:
    > hi all,
    >
    > how to calculate the intersection of 2 rectangle


    Take the rightmost left-border, the left-most right border, the bottom-most
    top border and the top-most bottom border as borders for your intersection.
    If the left border of the intersection is on the right of the right border
    ot the top border below the bottom border, there is no intersection.
    --
    Simon Stienen <http://dangerouscat.net> <http://slashlife.de>
    »What you do in this world is a matter of no consequence,
    The question is, what can you make people believe that you have done.«
    -- Sherlock Holmes in "A Study in Scarlet" by Sir Arthur Conan Doyle
     
    Simon Stienen, Sep 25, 2004
    #4
  5. kimos

    SM Ryan Guest

    # this should return the intersection of the 2 rectangles
    # anyone can help me plz?

    Take two pieces of paper, overlay them, and think about you're looking at. Hint:
    the intersection is either empty, a point, or a rectangle.

    --
    SM Ryan http://www.rawbw.com/~wyrmwif/
    OOOOOOOOOO! NAVY SEALS!
     
    SM Ryan, Sep 25, 2004
    #5
  6. kimos

    xarax Guest

    "SM Ryan" <> wrote in message
    news:...
    > # this should return the intersection of the 2 rectangles
    > # anyone can help me plz?
    >
    > Take two pieces of paper, overlay them, and think about you're looking at.

    Hint:
    > the intersection is either empty, a point, or a rectangle.


    Or two points forming a line segment (the
    rectangles share some part of a border).
     
    xarax, Sep 25, 2004
    #6
  7. kimos wrote:
    > how to calculate the intersection of 2 rectangle


    The easiest way to think about this problem conceptually is to first
    come up with an algorithm for the 1D version, intersecting two line
    segments, then generalize it.

    Suppose we have a line from a to b and a line from c to d. There are
    four cases for intersecting them:

    a <= b < c <= d : a----b c----d
    In this case the intersection is empty.

    a <= b = c <= d : a----b/c----d
    In this case the intersection is the single point b=c (the line segment
    from b to b.)

    a <= c <= b <= d : a---c===b---d
    In this case the intersection is the line from c to b.

    a <= c <= d <= b : a---c===d---b
    In this case the intersection is the line from c to d.

    If you simply apply these same four cases to the x and y coordinate
    ranges of your rectangles separately, the result will be the x and y
    coordinate ranges of the intersection of the rectangles.
    --
    Derrick Coetzee
    I grant this newsgroup posting into the public domain. I disclaim all
    express or implied warranty and all liability. I am not a professional.
     
    Derrick Coetzee, Sep 26, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kenneth

    Rectangle object in asp.net?

    Kenneth, Jan 15, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    545
    Steve C. Orr [MVP, MCSD]
    Jan 15, 2004
  2. Alberto

    Paint a rectangle

    Alberto, Jan 1, 2005, in forum: ASP .Net
    Replies:
    1
    Views:
    438
    Scott Mitchell [MVP]
    Jan 1, 2005
  3. Tyrant Mikey
    Replies:
    10
    Views:
    5,507
    Tyrant Mikey
    Feb 7, 2005
  4. Praveen

    Draw a rectangle

    Praveen, Feb 24, 2005, in forum: ASP .Net
    Replies:
    1
    Views:
    494
    Kevin Spencer
    Feb 24, 2005
  5. bigbinc

    scale rectangle based on x,ys

    bigbinc, Dec 17, 2003, in forum: Java
    Replies:
    1
    Views:
    1,366
    bigbinc
    Dec 17, 2003
Loading...

Share This Page