0
$\begingroup$

I need a little help with a few simple Geometry question that I need to resolve:

How to know if given a point of (X, Y) is that point inside or outside a list of shapes that I have with some information of those shapes.

1- A Rectangle (I have the Length and Width and the (X, Y) of one of the corners of the rectangle)

2- A Square (I have the size of the side and the (X, Y) of one of the corners of the square

3- A Circle (I have the radius and the (X, Y) of the center of the circle)

4- A Triangle (I have the three (X, Y) for each vertices of the triangle)

5- A Donut (I have the (X, Y) of the center of the donut and both the small and big radius)

Thanks for any help that can be provided...

$\endgroup$
  • $\begingroup$ For 1,2 you need to know the orientation of the square / rectangle. For instance, you could have one corner, but is the shape, with respect to that corner, in the first, second, third or fourth quadrant? $\endgroup$ – DanZimm Jun 7 '14 at 23:37
  • $\begingroup$ I don't really have that information in the exercise... There is no way of knowing 1 and 2 only based on that information and maybe additional assumptions?? What about the other shapes? $\endgroup$ – Alonso Quesada Jun 7 '14 at 23:48
  • $\begingroup$ You really need to know the orientation of the shape, meaning which corner you're given. In my answer I assume you're given the bottom left corner. $\endgroup$ – DanZimm Jun 7 '14 at 23:54
0
$\begingroup$

Both $1,2$ are similar cases, let's focus on the rectangle, since a square is simply a special case of a rectangle. As mentioned in the comments you need to know the orientation of the shape. Let's assume that you're given the bottom left corner $(x_0,y_0)$ of the rectangle. We can characterize the points in this rectangle as $$ R = \{ (x,y) \mid x = x_0 + u \cdot w, y = y_0 + v \cdot h, u,v \in [0,1] \} $$ Where $w = \mathrm{width}, h = \mathrm{height}$. Then a point $(x,y)$ is in $R$ (and thus inside the rectangle) iff $x = x_0 + u \cdot w, y = y_0 + v \cdot h$ for some $u,v \in h$. Note now that a square is simply a rectangle with $w=h$.

Next a circle and a donut are similar shapes, we can consider a circle to be a donut with inner radius of $0$. Let the donut be centered at $(x_0,y_0)$ with inner radius $r_i$ and outer radius $r_o$. Then this shape can be described by the set $$ D = \{ (x,y) \mid r_i^2 \le (x-x_0)^2 + (y-y_0)^2 \le r_o^2\} $$ so to test whether or not a given $(x,y) \in C$ (and thus whether the point is inside the circle) we need to check wether or not $ r_i^2 \le (x-x_0)^2 + (y-y_0)^2 \le r_o^2$.

EDIT: Realized I made the wrong lines for the triangle, doh!

Finally for a triangle with corners $(x_0,y_0),(x_1,y_1),(x_2,y_2)$ consider the lines from the point to we're testing $(x,y)$ to each of the corners: $$ y - y_0 = m_{0}(x - x_0) \\ y - y_1 = m_{1}(x - x_1) \\ y - y_2 = m_{2}(x - x_2) $$ where $m_{i} = \frac{y_i - y}{x_i - x}$. In order to test whether or not this point is in the interior of this triangle we would need to have the sum of the angles (taking the smallest of the angles) between these lines to be $2 \pi$, otherwise if it's on the exterior it will be less than $2 \pi$. As for calculating these angles you would need some linear algebra. Construct vectors for each of the lines, take dot products and then find the angle that way. Although this is intuitive it clearly isn't the fastest way, other algorithms are detailed in many programming websites such as this one.

$\endgroup$
  • $\begingroup$ So if I'm getting it correctly, for 1, 2 when they give me the pair (x, y) I should do x0 + u * w and that should be equal to the x of the pair given to me and then do the same for y0 + v * h... If that's correct, then what I'm not sure about is what the values for u and v are? $\endgroup$ – Alonso Quesada Jun 8 '14 at 13:49
  • $\begingroup$ @AlonsoQuesada if there exists a $u \in [0,1]$ and a $v \in [0,1]$ so that $x_0 + u \cdot w = x, y_0 + v \cdot h$ then the point is inside the rectangle. Another way to view this is by checking whether or not $x = x_0 + u \cdot w$ has a solution for $u$ where $0 \le u \le 1$, and likewise for the $y-$coordinate equation. $\endgroup$ – DanZimm Jun 8 '14 at 13:52
  • $\begingroup$ So I have to find out what the value for u and v is and if its inside the [0,1] then the point is inside the rectangle? What Im completely not getting is the triangle example :(... Sorry for asking so much and thanks for your time... $\endgroup$ – Alonso Quesada Jun 8 '14 at 13:59
  • $\begingroup$ @AlonsoQuesada no problem, you are completely correct on the rectangle, as for the triangle issue let me edit the post. I'll mention you when I'm done. $\endgroup$ – DanZimm Jun 8 '14 at 14:09
  • $\begingroup$ @AlonsoQuesada ok, I have edited the post. It's no wonder you didn't understand the triangle example, I had it wrong! :P $\endgroup$ – DanZimm Jun 8 '14 at 14:19

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.