Introductioin to Computational Geometry

Computational Geometry

               

Do you ever wonder how can games object interact each other? Player in game shoot the bullet to fight gaming villain, First case is player hit the villain and blood level of villain decreased. Second possibility is player miss the target. Here, how computer can decide if bullet is missed or hit the target? First let consider the case how we can decide the aim? It’s simple, just point the gun in the direction of target.. In technical speaking make sure straight line from gun reach the target. Now, IN terms of computer, same can be implemented if target location is in the straight line from gun then hit the target otherwise not. For that we can use Screen as two dimensional graph and every pixel on screen take as point on screen. Efficiently doing stuff on screen there are many algorithms and these are called geometric algorithms.

                Computational geometry is the branch of computer science that studies Algorithms for solving geometric problems. It has numerous applications in many fields such as robotics, VLSI design, Computer graphics, metallurgy, textile layout, forestry and molecular modelling.

Collinear Points Algorithm

                Two geometric points A=(x1,y1) and B=(x2,y2) are given.  If we draw separate lines from origin O = (0,0) to each point, then line OA is in clockwise from line OB or OA is in counter-clockwise from OB ? Third possibility is that points O, A and B are collinear.

                We can find out solution with the help of cross product of two vector OA and OB. Cross product of these two vector give us area of parallelogram formed by the points O,A,B and A+B = (x1+x2,y1+y2). If points are collinear then area must be zero. If cross product is positive that means OA is clockwise from OB. If cross product is negative that means OA is counter-clockwise from OB.

                OA x OB =  x1.y2 – x2.y1

                C++ code for above implementation.

	/*
	Function return
	0 if points are colinear with origin
	1 if first point vector is clockwise from second point vector
	2 if first point vector is Counter-clockwise from second point vector
	*/
	int direction(int x1,int y1,int x2,int y2)
	{
	// determinant
	int d = x1*y2 - x2*y1 ;
	//determinant is 0 .. points are colinear to origin
	if (d==0)
	return 0;
	//determinant > 0 .. OA is clockwise from OB
	if (d > 0)
	return 1;
	//determinant < 0 .. OA is counter-clockwise from OB
	return 2;
	}

view raw linear_pont.cpp hosted with ❤ by GitHub