Finding Whether A Point is Within a Right-Angle Triangle

5
votes

I've always wondered the easiest way to figure out whether or not a point lies within a triangle, or in this instance, a rectangle cut into half diagonally.

Let's say I have a rectangle that is 64x64 pixels. With this rectangle, I want to return a TRUE value if a passed point is within the upper-left corner of the rectangle, and FALSE if it isn't.

-----
|  /|
| / |
|<__|

Horray for bad ASCII art.

Anyway, the hypothetical points for this triangle that would return TRUE would be (0,0) and (63,0) and (0, 63). If a point lands on a line (e.g., 50,0) it would return TRUE as well.

Assuming 0,0 is in the upper-left corner and increases downwards...

I've had a possible solution in my head, but it seems more complicated than it should be - taking the passed Y value, determining where it would be in the rectangle, and figuring out manually where the line would cut at that Y value. E.g, a passed Y value of 16 would be quarter height of the rectangle. And thus, depending on what side you were checking (left or right), the line would either be at 16px or 48px, depending on the direction of the line. In the example above, since we're testing the upper-left corner, at 16px height, the line would be at 48px width

There has to be a better way.

EDIT: The rectangle could also look like this as well

-----
|\  |
| \ |
|__>|

But I'm figuring in most cases the current answers already provided should still hold up...

5
mathgeometry
There is math.stackexchange.com where you ask this question also. One would suggest several solutions to your problem, but you did not tell what you need - speed, optimization for particular cases or just clear formulation. – Petr Gladkikh
Just clear formulation. I can typically come up with a solution, but it's hardly elegant and speed is an issue. I like seeing different ways of doing this, so I can think outside of what I'm already doing. It helps me remember basic math as well :[ – Jeffrey Kern

5 Answers

11
votes

Top-left/bottom-right triangles: For all points in the top-left triangle, x+y<=64. Points in the bottom-right triangle have x+y>64.

(for a rectangle of size (w,h) use w*y+h*x-w*h<0)

Top-right/bottom-left triangles: For all points in the bottom-left triangle, x<=y. Points in the top-right triangle have x>y.

(for a rectangle of size (w,h) use h*x-w*y<0)

How did we get there?

For a rectangle of dimensions (w,h) and TL/BR triangles, the equation of the diagonal is (try it out! assign x=0 and check that you get y==h, and assign y=0 and check that x==w)

h*x + w*y - w*h = 0

Points on one side of that line will have

h*x + w*y - w*h > 0

While points on the other will have

h*x + w*y - w*h < 0

Inserting 64 for both w and h, we get:

64x + 64y - 64*64 < 0

Dividing by 64 gets us:

x+y < 64

For TR/BL triangles, the line equation and the resulting inequalities are:

h*x - w*y = 0
h*x - w*y < 0
h*x - w*y > 0

Inserting 64 for w and h, we get

64x-64y < 0
=> x<y
3
votes

you can represent the triangle with three affine functions

take the unit triangle with corners at (0, 0), (1, 0) and (1, 1). the sides are represented by the three lines

  1. y = 0
  2. x = 1
  3. y = x

So the interior and boundry of the triangle are given as the intersection of the sets

  1. x >= 1
  2. y >= 0
  3. y <= x

so given a point, (x, y), you just need to verify that it satisfies those three inequalities.

You can of course generalize this to any triangle using the fact that any affine function (representing a line) can be written in the form y = mx + b.

0
votes

The equation for the line looks like this : 

y = mx + b

So, if you insert your x and y-Values into that equation, it will probably not hold anymore. Let's reformulate it:

mx + b - y = 0

Same thing, different look. Again, the result is probably not zero. But, the result will now tell you whether it's on the one side of the line or the other.

Now you just have to find out whether the point is inside your rectangle.

0
votes

Lets assume your right angled triangle has one corner at 0,0 and the diagonal corner at a,b.

So y=mx+c c=0 as we start at the origin.

m=b/a

So y=bx/a

To know which half of the triangle your point (c,d) falls in

if (d<=(bc/a)) {//point is in bottom half}

if (d>(bc/a)) {//point is in top half}

I think...

0
votes

A simple option is to use a ray casting algorithm. Whilst perhaps a little overkill for what you need, it does have the advantage that it will work with more complex triangles and polygons.

Loosely, the algorithm takes an imaginary point in a direction (infinitely off to the left, for example) and casts a ray to your test point; you then calculate whether each line of your triangle crosses that infinitely long line. If you get an odd number of crossings, your point is inside your triangle; even and you're out of your triangle