1
$\begingroup$

A rectangle is defined by the 4 points ABCD. How can I tell if a given point, (x,y), is in the interior of the rectangle?

My current guess is the following:

  • To be inside the rectangle, the point should be between the lines AB and CD, and between the lines AD and BC.
  • The equation of line AB (and, similarly, the other lines) can be written as:

$$ \frac{x-x_A}{y-y_A} = \frac{x_B-x_A}{y_B-y_A} $$

  • In order to be between line AB and line CD, one of the following must hold:

Either:

$$ \frac{x-x_A}{y-y_A} > \frac{x_B-x_A}{y_B-y_A} and \frac{x-x_D}{y-y_D} < \frac{x_C-x_D}{y_C-y_D} $$

Or vice versa:

$$ \frac{x-x_A}{y-y_A} < \frac{x_B-x_A}{y_B-y_A} and \frac{x-x_D}{y-y_D} > \frac{x_C-x_D}{y_C-y_D} $$

(According to the actual values of A, B, C and D, some of these conditions may be impossible or trivial).

  • In order to be between line AD and BC, one of the following must hold:

Either:

$$ \frac{x-x_A}{y-y_A} > \frac{x_D-x_A}{y_D-y_A} and \frac{x-x_B}{y-y_B} < \frac{x_C-x_B}{y_C-y_B} $$

Or vice versa:

$$ \frac{x-x_A}{y-y_A} < \frac{x_D-x_A}{y_D-y_A} and \frac{x-x_B}{y-y_B} > \frac{x_C-x_B}{y_C-y_B} $$

Is this correct? Is there an easier way to calculate if a point is inside a square?

$\endgroup$
  • $\begingroup$ Perhaps Computational Geometry may help you to solve more complex queries of this kind. $\endgroup$ – pushpen.paul Jun 30 '14 at 4:52
2
$\begingroup$

Assuming $ABCD$ are in cyclic order around the rectangle, if $P$ is your point, consider the points as vectors. You want $(A-B)\cdot P$ to be between $(A-B) \cdot A$ and $(A-B) \cdot B$ and $(A-D) \cdot P$ to be between $(A-D)\cdot A$ and $(A-D) \cdot D$.

$\endgroup$
  • $\begingroup$ I fail to see the geometry behind this solution. AFAIU, (A-B) is a vector that points from B to A, and P is a vector that points from the origin to P. What is the geometric meaning of their dot product? $\endgroup$ – Erel Segal-Halevi Oct 18 '13 at 10:39
  • 1
    $\begingroup$ My condition says that the component of $P$ in the direction of each of the axes of the rectangle is between the two values of that component on the vertices of the rectangle. $\endgroup$ – Robert Israel Oct 18 '13 at 14:53
  • $\begingroup$ Got it, thanks! $\endgroup$ – Erel Segal-Halevi Oct 19 '13 at 17:47
1
$\begingroup$

I suspect that you mean "quadrilateral", not rectangle (i.e. a polygon with 4 sides).

If so, then this is the classical "point in polygon" problem. There are two ways to attack it -- one way is to use ray casting, counting crossings, and the other is to use winding numbers.

You'll find lots of other material if you search for "point in polygon". Here is one link, and here is another one.

$\endgroup$
  • $\begingroup$ Thank you for the links, but you refer to algorithmic solutions, and I am looking for a closed-form formula, that I can use in theoretic proofs. $\endgroup$ – Erel Segal-Halevi Oct 18 '13 at 8:24
  • $\begingroup$ Will the "winding number" function work, then? $\endgroup$ – bubba Oct 18 '13 at 9:18
  • $\begingroup$ I found several definitions of the winding number: en.wikipedia.org/wiki/Winding_number but I am not sure how to apply them to a simple rectangle. Needs more thought. $\endgroup$ – Erel Segal-Halevi Oct 18 '13 at 10:43
  • $\begingroup$ The ray-crossing method is also a possible solution, thanks. $\endgroup$ – Erel Segal-Halevi Oct 19 '13 at 17:48
1
$\begingroup$

I found several definitions of the winding numer: Wikipedia:Winding_number but I am not sure how to apply them to a simple rectangle.

Consider the rectangle as a closed curve $C$, then apply equations from the section Differential geometry and Complex analysis in the Wikipedia article:

  • in a real plane XY: $$\text{winding number} = \frac{1}{2\pi} \oint_C \,\frac{x}{r^2}\,dy - \frac{y}{r^2} \,dx$$
  • in a complex plane Z: $$\text{winding number} = \frac{1}{2\pi i} \oint_C \frac{dz}{z}$$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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