1

I was wondering if the following algorithm to check if a point is inside a rectangle is valid. I've developed it using my own intuition (no strong trig/math basis to support it), so I'd love to hear from someone with more experience in the matter.

Context:

  • The rectangle is defined with 4 points. It could be rotated.
  • Coordinates are always positive.
  • By definition, the point is considered inside the rectangle if intersects it.

Hypothesis:

  • Use the distance between the point and the rectangle vertices (first diagram below).
  • The maximum possible total distance is when the point is in one vertex (second diagram).
  • If the point is just outside the rectangle, the distance will be greater (third diagram).

Diagram link: http://i45.tinypic.com/id6o35.png

Algorithm (Java):

static boolean pointInsideRectangle(Point[] rect, Point point) {
    double maxDistance = distance(rect[0], rect[1]);
    maxDistance += distance(rect[0], rect[2]);
    maxDistance += distance(rect[0], rect[3]);

    double distance = 0;
    for (Point rectPoint : rect) {          
        distance += distance(rectPoint, point);
        if (distance > maxDistance) return false;
    }
    return true;
}

Questions: is this correct?

user1442081
  • 13
  • 3

2 Answers2

3

Short answer: NO :P (don´t fell bad about it)

Long Answer: Intersecction the areas from the four circles that you mention (max distance between opposite vertex) does not produce a rectangle.Common area of four circles of radius equal to the rectangle´s diagonal with center in each corner Since I´m a bit rusty in geometry I can´t give full mathematical explanation (time constrain for my part), but give you some pseudocode of the procedure with the constrains that you ask (no fancy formulae), valid for any rectangle the wikipeida or a geometry book can fill the gaps.

  • Find the N,E,S,W vertex (the uppermost, rightmost, lowest and leftmost vertex) this is trivially easy for any rectangle but the axis aligned who can produce oddly assignation of the vertex (see images with examples) enter image description here
  • Find the NE, SE, SW and NW border, this is the line equation in wikipedia or another link, again should be easy, but the axis aligned border should be analized carefully because those generate another type of ecuation/restriction.

  • Check if your point is on the "right side" of the border see inequality as mathematical term, only a point inside your rectangle satisfy the four restrictions as you can see in the image attached. for each "border" the green area present a valid place for the point

  • my apologies if I have overlook some command of java.geom that can accomplish this task

I hope this help with your endevour

Alen
  • 1,040
  • 1
  • 8
  • 13
  • I have found many implementation of this and much, much, much better algoritms (silly me I forgot to check the G with "check if a point is inside a polygon") where this question is answered plethora of times in better ways than mine:[Stackoverflow](http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test), this [web](http://alienryderflex.com/polygon/) and in the [Wikipeida](http://en.wikipedia.org/wiki/Point_in_polygon) – Alen Jun 07 '12 at 13:43
0

You can try this.Lets name the point we have as A.Draw a line between A and every point of the rectangle.After that you get 4 different triangles.Calculate the area the triangles are taking(using Heron's formula) and compare it to the area of the rectangle.If the areas are the same then your point is inside the rectangle. Cheers

Aleksandar
  • 51
  • 3