coordinate geometry

Problem Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not. Example For example, consider the following program, the function should return true for P(10, 15) and false for P’(30, 15) B(10,30) / \\ / \\ / \\ / P \\ P' / \\ A(0,0) ----------- C(20,0) Solution Method 1 - Area of triangles made by point and other 2 vertices of triangle [Read More]

Problem Given a 2D point and a rectangle, determine if the point is inside the rectangle. Solution Method 1 - Calculate the area of triangles with 2 vertices of rectangle and point P(x,y), and rectangle A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4) Calculate the sum of areas of △APD,△DPC,△CPB,△PBA. If this sum is greater than the area of the rectangle, then P(x,y) is outside the rectangle. Else if this sum is equal to the area of the rectangle (observe that this sum can not be less than the later), if area of any of the triangle is 0, then P(x,y) is on the rectangle (in fact on that line corresponding to the triangle of area=0). [Read More]

Problem Given 3 points which are not colinear (all on the same line) those three points uniquely define a circle. But, how do you find the center and radius of that circle? Propose a simple algorithm for this. Solution 1. join two pairs of vertices. 2. Form the equations for the two lines. 3. Form the equations of the perpendicular bisectors of each of the equations obtained in step 2. [Read More]

Problem Given a two dimensional graph with points on it, find a line which passes the most number of points. Solution Method 1 - Naive solution This is the brute force solution. We take point 1, and then point 2 and make a line. Now in the third nested loop, check if point 3 is existing on the same line or not. Pseudocode Line findLineWithMaxPoint(Set points){ foreach Point p1 in points foreach Point p2 in (points - {p1}){ Line l = makeLine(p1,p2); int count = 2 //line contains p1 and p2 foreach(Point p3 in (points-{p1,p2})){ if(l. [Read More]

Problem:  Given two squares on a two dimensional plane, find a line that would cut these two squares in half. Solution: Any Line passing the centers of the two squares will cut them in halves. So, we have to connect the lines between the center of the 2 squares. The straight line that connects the two centers of the two squares will cut both of them into half. [Read More]

Problem Given two lines on a Cartesian plane, determine whether the two lines would intersect. Solution On a Cartesian plane, if two lines do not intersect, they must be parallel with each other. Hence, their slopes must be the same. If their slopes are different, they would intersect. A line is represented as ax+by+c=0 on a Cartesian plane and the slope is given by -\frac{a}{b}. Therefore if -\frac{a_{0}}{b_{0}} \neq -\frac{a_{1}}{b_{1}} for two lines, they will intersect. [Read More]