Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Say I have a rectangle and a point inside the rectangle. If the rectangle was split up diagonally, how could I tell which portion the point is in?

Here is a cute little mspaint diagram, where the portions are labeled with letters, and the point is shown with the red circle:

Please excuse the MS Paint

Also, if it helps, I am working in c++

share|improve this question
    
I think it is the cross product and the sign of the result to say whether you are on the left or right side of a line but I think that is what you are looking for here in the generic case. If you are looking for something a bit more special case you might find something a bit faster processor wise. –  James Mar 14 '12 at 23:14
add comment

4 Answers 4

up vote 4 down vote accepted

You basically just need to check the slope of the line from the bottom two corners rise over run. Here's some pseudocode

min = {x:10, y:10 } <- lower left corner of rectangle
max = {x:100,y:100} <- top right corner
width = max.x-min.x
height = max.y - min.y
string quadrant(Point p) { 
    // if above-diagonal1, we are in quadrant A or B
    ab = (p.y - min.y) * width > height * (p.x - min.x)
    // if above-over-diagonal2, either quadrant A or D
    ad = (p.y - min.y) * width > height * (max.x - p.x)
    return (ab && ad   ? "A" :
            ab && !ad  ? "B" :
            !ab && !ad ? "C" : "D")
}

Here's an implementation in javascript

share|improve this answer
    
Excellent demo. This seems like the best way. Thanks a lot! –  sFuller Mar 15 '12 at 2:18
add comment

You can narrow down which quadrant the point is in, check whether the point is above/below center and left/right of center. That gives you 4 cases to check. Then you just need to determine which side of the bisecting line the point is on. A good answer for that is here.

share|improve this answer
add comment

In short:

Split up the Rectangle into the 4 triangles (quadrant), then find which triangle the point is in.

Explanation

Say we are given the Rectangle with the x, y, width, and height.

TL +--------------+ TR
   |              |
   |              |
   |      C       |
   |              |
   |              |
BL +--------------+ BR

We can then find all the points labeled:

TL: (x, y)  //topLeft
TR: (x + width, y)  //topRight
BL: (x, y + height)  //bottomLeft
BR: (x + width, y + height)  //bottomRight
 C: (x + width/2, y + height/2)

Then we create our 4 triangles (quadrants) using the same notation you have above:

a: (TL, TR, C)
b: (TL, BL, C)  
c: (BL, BR, C)
d: (TR, BR, C)

Using these 4 triangles, check to see if the point is inside, if it is then you found your quadrant.

To find if a point is in a triangle you can use these:

Method1:

  public boolean pointInTriangle(Point p)
  {
    Point a = points[0];
    Point b = points[1];
    Point c = points[2];

    double dot00 = dot(c.x - a.x, c.y - a.y, c.x - a.x, c.y - a.y);
    double dot01 = dot(c.x - a.x, c.y - a.y, b.x - a.x, b.y - a.y);
    double dot02 = dot(c.x - a.x, c.y - a.y, p.x - a.x, p.y - a.y);
    double dot11 = dot(b.x - a.x, b.y - a.y, b.x - a.x, b.y - a.y);
    double dot12 = dot(b.x - a.x, b.y - a.y, p.x - a.x, p.y - a.y);

    double invDenom = 1.0 / (dot00 * dot11 - dot01 * dot01);
    double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    double v = (dot00 * dot12 - dot01 * dot02) * invDenom;

    if ((u > 0) && (v > 0) && (u + v < 1))
      return true;
    return false;
  }

  public double dot(double x1, double y1, double x2, double y2)
  {
    return x1 * x2 + y1 * y2;
  }

Method2:

  public boolean pointInTriangle2(Point p)
  {
    double invDenom = 1.0 / det(points[1], points[2]);
    double u = (det(p, points[2]) - det(points[0], points[2])) * invDenom;
    double v = -(det(p, points[1]) - det(points[0], points[1])) * invDenom;

    if ((u > 0) && (v > 0) && (u + v < 1))
      return true;
    return false;
  }

  public double det(Point p1, Point p2)
  {
    return p1.x * p2.y - p1.y * p2.x;
  }
share|improve this answer
add comment

In the case outlined above, take the distance of the point to all four sides of the rectangle, and also take the ratio of the width of the box to the height. If the ratio is greater than one, divide the horizontal distances by it, and if it is less than one, multiply the vertical distances by it. The lowest distance will correspond the triangle the point is is in.

In code: (haXe)

static function createBox(offsetX:Float, offsetY:Float, width:Int, height:Int):Void
{
    var box:Sprite = new Sprite();
    var lineThickness:Float = 2.0;
    var lineDefaultColor:Int = 0;
    var lineClosestColor:Int = 0x00CC00;
    var boxwidth:Int = width;
    var boxheight:Int = height;
    var boxOffsetX:Float = offsetX;
    var boxOffsetY:Float = offsetY;
    stage.addChild(box);

    var closest:Int = 0; // top=0, right=1, bottom=2, left=3, for the sides

    stage.addEventListener(Event.ENTER_FRAME, function(e:Event):Void
    {
        var mx:Float = stage.mouseX;
        var my:Float = stage.mouseY;
        //See if the pointer is inside the box
        //        x1                           x2                     y1                      y2
        if (mx > boxOffsetX && mx < boxOffsetX + boxwidth && my > boxOffsetY && my < boxOffsetY + boxheight)
        {
            var ratio:Float = boxwidth / boxheight;
            //                            x1
            var distLeft:Float = mx - boxOffsetX;

            //                             x2
            var distRight:Float = (boxwidth + boxOffsetX) - mx;

            if (ratio > 1)
            {
                distLeft /= ratio;
                distRight /= ratio;
            }

            var minHorizDist:Float = Math.min(distLeft, distRight);
            //                           y1
            var distTop:Float = my - boxOffsetY;
            //                                 y2
            var distBottom:Float = (boxOffsetY + boxheight) - my;

            if (ratio < 1)
            {
                distTop *= ratio;
                distBottom *= ratio;
            }

            var minVertDist:Float = Math.min(distTop, distBottom);

            var minDist:Float = Math.min(minHorizDist, minVertDist);

            switch(minDist)
            {
                case distLeft:
                    closest = 3;
                case distRight:
                    closest = 1;
                case distTop:
                    closest = 0;
                case distBottom:
                    closest = 2;
            }
        }
        else
        {
            //if the pointer is outside the box
            closest = -1;
        }


        //...flash specific drawing stuff...    
    });
}

Swfup crops the swf, unfortunately, but here's a demo.

complete source, I'd use FlashDevelop and the haXe compiler to build.

share|improve this answer
    
Works for a square, but doesn't work for long, thin rectangles. –  Nathan Reed Mar 14 '12 at 23:51
    
Technically, it doesn't work for any rectangles, if you think about it. I imagine there's a way to approximate it, though. Good catch, thanks. –  Quasiperfect Mar 15 '12 at 0:03
    
It now works for any axis aligned rectangle, oriented ones will have to be rotated so that they are, and then rotated back. –  Quasiperfect Mar 15 '12 at 0:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.