## Contents

- Geometry and Computational Geometry References
- Area of Polygon
- Equation of a Line
- Is a Point ona Line?
- Intersecton of Two Lines
- Intersection of a Line and a Circle
- Points clockwise, colinear or countr clockwise

### Geometry and Computational Geometry References

- Brief summary of Geometry stuff (3 pages) by Eugene Fink
- Competitive Programmerâ€™s Handbook by Antti Laaksonen (see pages 265-280)
- Introduction to Algorithms by Cormen, ... (Computational Geometry Section)

Return to Top of Page

### Area of a Polygon

Taken from Competitive Programmerâ€™s Handbook Page 266.

- assume you have N points
`area = (x`_{1}*y_{2}- x_{2}*y_{1}+ x_{2}*y_{3}- x_{3}y_{2}... + x_{n}*y_{1}- x_{1}-y_{n}) / 2

Return to Top of Page

### Equation of a Line

#### What is equation for a line given 2 points?

Given 2 points: (xif (x_{1},y_{1}) (x_{2},y_{2})_{1}== x_{2}) then line is vertical and slope is undefined x = x_{1}else m = (y_{2}- y_{1}) / (x_{2}- x_{1}) b = y_{2}- m*x_{2}y = m*x + b ==> y = ((y_{2}-y_{1})/(x_{2}-x_{1}))*x + (y_{2}- ((y_{2}-y_{1})/(x_{2}-x_{1}))*x_{2}) fi

#### What is equation of a line given a point and the slope?

Given a slope and a point: m (xb = y_{1}, y_{1})_{1 - m*x1 y = m*x + b ==> y = m*x + y1 - m*x1 }

Return to Top of Page

### Is a point on a line?

Given a line and a point: y = mx + b (xif (y_{1},y_{1})_{1}== (m*x_{1}+ b)) then the point is on the line else if (y_{1}< (m*x_{1}+ b)) then the point is below the line else the point is above the line fi fi

Return to Top of Page

### Given two lines, what is their intersection point?

Given two lines: y = mIf the lines have the same slopes, they do not intersect unless they are the same line. if (m_{1}*x + b_{1}y = m_{2}*x + b_{2}_{1}== m_{2}) then if (b_{1}== b_{2}) then they are same line -- they intersect at all points else they have same slope but do not ever intersect fi else m_{1}*x + b_{1}= m_{2}*x + b_{2}m_{1}*x - m_{2}*x = b_{2}- b_{1}(m_{1}- m_{2}) * x = b_{2}- b_{1}x = (b_{2}- b_{1}) / (m_{1}- m_{2}) y = m_{1}*x + b_{1}fi

Return to Top of Page

### Intersection of a Line and a Circle

Wolfram Circle line IntersectionReturn to Top of Page

### Points clockwise, colinear or countr clockwise

Consider two points: P_{1}, P_{2}. If you consider these points as vectors anchored at the
origin, the P_{2} must be counter clockwise, colinear or clockwise of P_{1}. Two questions
should spring to your mind:

- Why do we care?
- How do we figure it out?

The why is because it is useful for numerouse reasons (some of which will be shown shortly).

The how is a lot easier than it might seem. You use cross product:

(X_{1}* Y_{2}) - (X_{2}* Y_{1})

- If the result is positive, then P
_{2}is counter-clockwise of P_{1}. - If the result is zero, then P
_{2}is colinear with P_{1}. - If the result is negative, then P
_{2}is clockwise of P_{1}.

- (0, 0)
- P
_{1} - P
_{1}+ P_{2} - P
_{2}

_{1}+ P

_{2}(X

_{1}+ X

_{2}, Y

_{1}+ Y

_{2}). The cross product of P

_{1}* P

_{2}is the area of the quadrilateral. The sign of the result is ignored when calculating the area. But knowing the sign tells the direction of turn from P

_{1}to P

_{2}.

One really useful place for this is in finding the smallest (in area) convex polygon that contains all the points in a list.

Return to Top of Page