Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# triangle algorithm

Brandi Love
Ranch Hand
Posts: 133
I'm looking for an algorithm in java to determine if a given point (x , y) is located in an isoceles triangle. The only variable I have is the location of the triangle's center. Having a bit of trouble with this one, anyone know anything that might get me on my way to a solution?

Henry Wong
author
Marshal
Posts: 21122
78
I don't think there is a solution. A really small triangle, and a really large triangle, may have the same center. So almost any point can be in the triangle or not, depending on the size of the triangle. You don't know the size, only the center, so you can't tell if the point is in the triangle.

Henry

Brandi Love
Ranch Hand
Posts: 133
Oh my, I'm sorry. I do know the height and width of the triangle as well, the user inputs them. Maybe that changes things a bit

Layne Lund
Ranch Hand
Posts: 3061
I suggest that you step away from the computer and use a pencil and graph paper to see if you can figure this out by hand. Pick a simple example to start with: say a triangle with center at (0, 0), height of 2, and width of 2. Can you determine if the points (0, 0), (1, 1), and (10, 3) are inside this traingle or not? What techniques do you use? After using graph paper to deterimine this, can you find any mathematical equations to help with this problem? Since the computer can't just "look" at a graph to see that a point is inside a triangle, it might be easier to use such equations.

Also, the center, width, and height don't seem to be enough to uniquely determine a single triangle. For example, two triangles could have the same values for these three parameters when one of them is pointing up and the other is pointing down. Are you required to use the center of the traingle as part of the input? Can you find any other ways to represent a triangle? Or can you add any additional constraints to what you have so far to make sure the user can indicate only one triangle?

I hope some of my questions help you think of things that you can try. Please come back with more questions or just to sound off with your ideas.

Layne

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24211
35
Even that isn't enough, in general, as the triangle can be rotated about the center -- unless you specify a particular orientation.

Rusty Shackleford
Ranch Hand
Posts: 490
You don't know anything else? Such as where is point(0,0)? Or is the base on of the (at least) 2 equal sides? If you know point(0.0) it will be possible. If the base is on the x-axis and you know the center point, a ton of information can be extracted. With just a point, and nothing else, any other point can be inside the triangle if it is big enough.

edit: When you say width, I am assuming you mean the width of the base. Now you have something to work with, but you need to make assumptions, that the base is always on the bottom, and it never rotates. Assume the base is on the x-axis. It would be easier knowing if one of the 2 equal sides is not the base, but if using those assumptions are correct, you should be able easily figure if a point is inside the triangle.
[ March 22, 2006: Message edited by: Rusty Shackleford ]

Brandi Love
Ranch Hand
Posts: 133
The triangle's center would be at the origin and it points upward, like this:

so we are able to determine from the height where each of the three corners are located.
[ March 22, 2006: Message edited by: Brandi Love ]

Rusty Shackleford
Ranch Hand
Posts: 490
You have enough information to get the equations of the sides as lines, and you know the highest point. That is all you need. Split that tringle into 2 equal triangles and use trigonometery to get the angles, the length of the sides can be had by the pythagorean thereom. Although neither is really needed.

When you get a point, to test it, if the first value(absolute value) is greater then half the length of the base, you know it is outside the triangle and can return false with no further calculations. Same thing with the height and y-point. With both of those tests true, you know it might be inside the triangle. Now you have to check the y-value. To do that, get the y value of the side of the x-value of the point you are testing. If the point you are testing is less then or equal to the y(absolute value again) point on the triangle, then it is inside.

example: the triangles 2 points on the base are(-6,0) and (6,0), h=10. And the point you are looking at is (-7,6). |-7| > length/2, so that point is outside the triangle.

Same triangle but looking at point (3,5). 3 < 6 so you have to test the y values. 5 < height, so it might be inside. You know the points of the side, use the point slope formula: y-y1=m(x-x1), where m is the slope or you can use the slope intercept equation y=mx+b where b is the y-intersection(10 in this case). m = (10-0)/(0-6)=-5/3. So y = (-5/3)x + 10. Plug in 3 for x and you have 5. The point you are testing is (3,5) so compare that y-value with the point found with the slope intercept equation, which is 5 in this case, which is right on the line, and probably inside the triangle, depending on the requirements. This is assuming no math errors on my part, which is a rather large assumption.

To convert it to a suitable algorithm, do it yourself on paper a few times to get a feel for it, and then transfer each step to code.
[ March 22, 2006: Message edited by: Rusty Shackleford ]

Brandi Love
Ranch Hand
Posts: 133
Thanks for all of your help I've got the code working

Layne Lund
Ranch Hand
Posts: 3061
Another solution is to construct the equations of the lines for each side of the traingle and then take a point and determine which side of the line it is on. Repeat for all three lines.

One advantage is that this can be used for any triangle (e.g. it does not have to be equilateral). Also it can be scaled for use with any convex polygon. Of course, I'm probably starting to get beyond the scope of this beginner's forum.

Layne