Interview Question
Software Engineer in TestsCountry: England
Interview Type: Phone Interview
By using slopes, we can tell whether given point is inside triangle or not .
1. Let us assume A,B,C are triangle points. P is given point to check whether it is inside traingle or not.
2. calculate Slopes AB,AC,AP . AP slope should be between AB and AC.
3. similarly calculate BA,BC,BP slopes. BP slppe should be between BA and BC .
4. similarly calculate CA,CB,CP slopes. CP slppe should be between CA and CB .
if 2,3,4 statements true, then we can say Point P is inside traingle .
We can think for generic polygon solution where take all the points in the side of the triangle, now see on the Y axis, how many points are there with the Point (to find) Y; if it is odd number of points then the point is inside the triangle, if there are even number of points then it not inside the triangle.
First rotate the trangle & given point such that one of the edge of the trangle should lie on X-axis.
Now compare the given point X-co-ordinate if it is +ve (or) ZERO(point lies on the trangle) increase count value.
Repeat the same for remaining two edges.
If count value is 3 then it lies inside if not it is out side.
Find minX, minY, maxX, maxY.
if minX is smaller than xToFind and maxX larger than xToFind and minY smaller than yToFind and maxY larger than yToFind the point (xToFind,yToFind) is inside the triangle
Find equations of all the three lines (using slope and intercept concept).
Then for each equation, if the 3rd point of triangle and given point are on same side, the given point in inside the triangle.
To check whether two points are on same side of the triangle, substitute x and y values of both points in the equation and if the result is same sign (positive or negative), they are on the same side of the line.
1. I would compute the area of the triangle..
- dorohanter April 17, 20122. and then create 3 triangles following the rule:
- take two points off the old triangle and
- put it with the new point and then
-compute the area.
3. check if the sum of the 3 new triangles =old sum