Qualcomm Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
how we will compute the area of three triangles and the bigger one?
do we already know the base and height of original and new triangles?
to rodex:
find length of the 3 sides using distance formula..
then use heron's formula ......to find area
join the point to all vertices (by 3 ray),
calculate the angles between above 3 rays.
if all angle < 180 di ==> point in side.
any angle = 180 di ==> point is on the line.
any angle > 180 di ==> point is outside
if there is only 2 possible ray the point is on a vertex.
public class Point {
private double x;
private double y;
// getters, setters, constructors, etc.
public boolean includedInTriangle(Point p1, Point p2, Point p3) {
// based on triangles rotation
double direction = (p1.getX() - p3.getX()) * (p2.getY() - p3.getY())
- (p1.getY() - p3.getY()) * (p2.getX() - p3.getX());
double direction1 = (p1.getX() - this.getX())
* (p2.getY() - this.getY()) - (p1.getY() - this.getY())
* (p2.getX() - this.getX());
double direction2 = (p2.getX() - this.getX())
* (p3.getY() - this.getY()) - (p2.getY() - this.getY())
* (p3.getX() - this.getX());
double direction3 = (p3.getX() - this.getX())
* (p1.getY() - this.getY()) - (p3.getY() - this.getY())
* (p1.getX() - this.getX());
return (direction >= 0 && direction1 >= 0 && direction2 >= 0 && direction3 >= 0) ||
(direction < 0 && direction1 < 0 && direction2 < 0 && direction3 < 0);
}
public boolean isAnEdgeOfTriangle(Point p1, Point p2, Point p3) {
//y = xM + b and y value is included in the range;
return (this.getY() == p1.getM(p2) * this.getX() + p1.getB(p2) &&
this.getY() <= Math.max(p1.getY(), p2.getY()) && this.getY() >= Math.min(p1.getY(), p2.getY())) ||
(this.getY() == p1.getM(p3) * this.getX() + p1.getB(p3) &&
this.getY() <= Math.max(p1.getY(), p3.getY()) && this.getY() >= Math.min(p1.getY(), p3.getY())) ||
this.getY() == p2.getM(p3) * this.getX() + p2.getB(p3) &&
this.getY() <= Math.max(p2.getY(), p3.getY()) && this.getY() >= Math.min(p2.getY(), p3.getY());
}
public boolean isAVertexOfTriangle(Point p1, Point p2, Point p3){
//simple comparison of components
return (this.getX() == p1.getX() && this.getY() == p1.getY()) ||
(this.getX() == p2.getX() && this.getY() == p2.getY()) ||
(this.getX() == p3.getX() && this.getY() == p3.getY());
}
private double getM(Point other) {
return (this.getY() - other.getY()) / (this.getX() - other.getX());
}
private double getB(Point other) {
return this.getY() - this.getM(other) * this.getX();
}
}
another simple algo would be..
1) Draw a unidirectional ray cutting the triangle.
2) if no of intersection points is 2 then it is outside of the triangle
3) if no of intersection point is just 1 then it could be inside the circle or one of the edges..
the case of edge can be eliminated using the slope equation.
Let the give yn point be (x,y). The vertices be (x1,y1), (x2,y2), (x3,y3)
xmax = max(x1,x2,x3)
ymax = max(y1,y2,y3)
if xmin <= x <= xmax && ymin <= y <= ymax then the point is inside.
if both conditions are violated, the point is outside.
To find if it lies on the edges, compare the slope of edges and that of lines formed by the point and one vertex. if the slope is same, then it lies on that edge.
One simple approach could be to find equations of the three lines forming the triangle. If given point satisfies any 1 of those 3 lines then it is on the edge. Then we can check if the point is equal to one of the triangle points.
Else put the (x,y) coordinates of the given point in to each of the line equation and find out if it yields positive or negative value. Positive value indicates point lies to the right of the line, negative indicates it lies to the left. For the point to be inside the triangle, it must lie to the right of the 2 lines and to he left of the remaining line. Else it lies outside the triangle.
it's too simple just check the distance from the each point of triangle to that point ...
like let A(a,b) B(c,d) C(e,f) these are the points of the triangle .... and D(p ,q) are the point to be found then do nothing just find the distance between each point like AB , AC, BC if it greater than any distance means it's out of the triangle .... i will post code here thanx
it could be smaller than those distances and still outside the circle. think as the perpendicular distance from each point of the triangle (A,B,C) to the front side line is less than the edges of the triangle from that point to the other points (Pythagoras theorem) there is a region that the distance is still less than the edges but outside the circle. so it will not work.
I have developed this code to the
import java.util.*;
import java.lang.Math.*;
public class Triangle
{
public static void main (String [] args)
{
Scanner cs = new Scanner(System.in);
double ax = cs.nextInt();
double ay = cs.nextInt();
double bx = cs.nextInt();
double by = cs.nextInt();
double cx = cs.nextInt();
double cy = cs.nextInt();
double dx = cs.nextInt();
double dy = cs.nextInt();
//double arr[] = new flaot[6];
double ab = dist(ax,ay,bx,by);
double bc = dist(bx,by,cx,cy);
double ac = dist(ax,ay,cx,cy);
double ad = dist(ax,ay,dx,dy);
double bd = dist(dx,dy,bx,by);
double cd = dist(cx,cy,dx,dy);
if(((ad < ab) && (ad < ac)) && ((bd < ab) && (bd < bc)) && ((cd < ac) && (cd < bc)) )
System.out.println("Point it inside the triangle ");
else
System.out.println("Point is out side of the triangle");
ontheline(ax,ay,bx,by , dx, dy);
ontheline(ax,ay,cx,cy , dx, dy);
ontheline(bx,by,cx,cy , dx, dy);
if((ax == dx ) && (ay == dy ))
System.out.println("\n Point d is in the Point"+ax+":"+ay);
if((bx == dx ) && (by == dy ))
System.out.println("\n Point d is in the Point"+bx+":"+by);
if((cx == dx ) && (cy == dy ))
System.out.println("\n Point d is in the Point"+cx+":"+cy);
}
static void ontheline(double x1 , double y1 , double x2 , double y2 , double x3, double y3)
{
double a = ((y2-y1) / (x2-x1));
double b = (y1 - (a*x1));
if(b == (y3 - (a*x3)))
System.out.println("on the line in points "+x1+ ":"+y1+"::"+x2+ ":"+y2);
}
static double dist(double x1 , double y1 , double x2 , double y2 )
{
double distance=Math.sqrt(((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)));
return distance;
}
}
this code is CC to Arun Kumar Gupta
Here is C implementation to check whether a point lies inside a triangle or not.
Let the coordinates of three corners be (x1, y1), (x2, y2) and (x3, y3). And coordinates of the given point P be (x, y)
1) Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram. Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2
2) Calculate area of the triangle PAB. We can use the same formula for this. Let this area be A1.
3) Calculate area of the triangle PBC. Let this area be A2.
4) Calculate area of the triangle PAC. Let this area be A3.
5) If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.
#include <stdio.h>
#include <stdlib.h>
/* A utility function to calculate area of triangle formed by (x1, y1),
(x2, y2) and (x3, y3) */
float area(int x1, int y1, int x2, int y2, int x3, int y3)
{
return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);
}
/* A function to check whether point P(x, y) lies inside the triangle formed
by A(x1, y1), B(x2, y2) and C(x3, y3) */
bool isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{
/* Calculate area of triangle ABC */
float A = area (x1, y1, x2, y2, x3, y3);
/* Calculate area of triangle PBC */
float A1 = area (x, y, x2, y2, x3, y3);
/* Calculate area of triangle PAC */
float A2 = area (x1, y1, x, y, x3, y3);
/* Calculate area of triangle PAB */
float A3 = area (x1, y1, x2, y2, x, y);
/* Check if sum of A1, A2 and A3 is same as A */
return (A == A1 + A2 + A3);
}
int main()
{
/* Let us check whether the point P(10, 15) lies inside the triangle
formed by A(0, 0), B(20, 0) and C(10, 30) */
if (isInside(0, 0, 20, 0, 10, 30, 10, 15))
printf ("Inside");
else
printf ("Not Inside");
return 0;
}
This can be done in a better mathematical way like this:
Input:
1.We are given a Point
2.We are given a triangle with 3 points
First compute the equations of the 3 lines using 2 point formula i.e if two points (x1,y1), (x2,y2) are there,the equation of line passing through them is (x-x1)/(x2-x1)=(y-y1)/(y2-y1)
a.Now we have 3 equations..take any of those 3 equations and let f(x,y)=ax+by+c be that equation(for simplicity..u can substitute the values of a,b,c here).
To find the point (x4,y4) lies on the triangle or not,if u find f(x4,y4)=0 for any equation,that point lies on triangle..otherwise not.
If the point doesn't lie on triangle,then:
To know whether the point lies inside or outside the triangle:
1.The point should lie to the left of one line of triangle and to the right of another line of that triangle.To get this:
b.Now take origin i.e (0,0) and substitute and calculate f(x,y)..so now f(0,0)=0*x+0*y+c=c(c can be +ve or -ve) .If c is +ve,it means origin is right side of that line and if its -ve ,it means origin is left side of that line
c.Now calculate f(x4,y4) where (x4,y4) is the given point .if sign(f(x4,y4))==sign(c)..then they both are on the same side of the line..so if f(x4,y4) and c are both +ve..tehy are on right..if both -ve,they are on left,if c +ve and f(x4,y4) -ve,the point is on the left...
d.if u find the point is left/right of this line,then do this for other 2 lines also
e.if u find the same point is on right/left(respectively) of another line..then its inside the Triangle otherwise its outside the triangle
I think this is also a solution to this problem. Join the point to all the vertices of the triangle.
1) if a point lies inside the triangle then you can see three triangles formed by union of the points.
2) If a point lies outside the triangle then you will see a polygon or four sided figure.
3) if it lies on the side of triangle then you see only 2 triangles.
4) If it is coinciding with the point then you can see only 1 triangle formed.
Hey a simple algo for this would be as follows.
Draw a line from the point to all the three vertices of the triangle.
1) if you see 3 triangles formed then it will be a point inside the triangle.
2) if you see a four sided figure after joining then it will be point outside the triangle.
3) If you see only two triangles then it is on one of the sides of a triangle.
4) if you just see one triangle then it is on the vertex.
join the given point with 3 vertex of the triangle and calculate the area of the three sub triangles thus formed. Now sum those 3 area values and compare it with the area of the original big triangle. If its equal then the point lies inside else outside.
- ud October 27, 2011