2-D Geometry introduction

A vector and a point in 2D consist of 2 numbers $ <i, j>, (x,y) $, and we can use $ std:pair $ or struct to implement their representation.

Basic Operations

1. Find squared length of a vector.
dbl len2(pt p){ return p.x*p.x + p.y*p.y; }

2. Find length of a vector.
dbl len(pt p){ return sqrt(len2(p)); }

3. Normalize the vector.
pt norm(pt p){ dbl lenp = len(p); return {p.x/lenp,p.y/lenp}; }

4 Rotate a vector.
pt rotate(pt p,dbl a){ return {cos(a)*p.x-sin(a)*p.y, cos(a)*p.y+sin(a)*p.x};} }

Properties of Dot(scalar) Product

$p.q = dot(p, q)= p.X*q.X + p.Y*q.Y=cos(pq)*|p|*|q|$

Return scalar, not vector

Equals 0 $iff$ vectors $p$ and $q$ are orthogonal.

Positive is angle is acute, negative angle is obtuse.

Signed length of projection of $p$ on $q$ is $|p|*cos(pq)$.

Symmetrical in nature: $dot(p,q) = dot(q,p)$.

Applications of Dot Product

You are given a segment $A(x_1, y_1)$ and $B(x_1, y_1)$ and a point $P(x_3, y_3)$. check if a point is orthogonal to segment $AB$.

Solution: - Calculate the vectors $AB$ and $AP$. Calculate the dot product of $AB$ and $AP$ and it will be positive $iff$ if the angle is acute. Check for similar case for B. It is important to check the same for B.

You are given a circle with center $O(p, q)$ and a point on the circle $A(x_1, y_1)$ and a point $P(x, y)$. You have to check whether you can see $P$ from $A$. Calculate $OA$ and $AP$ if the dot product is non-positive which means the angle is obtuse or right angle hence you can see A from B.

Re-calculation of point P on co-ordinate system of $A$ and $B$ vectors. Solution:- $$P = \alpha. A + \beta . B$$ and $\alpha = \frac{dot(P,A)}{|A|^2}$ and similar for $\beta$.

Calculate signed angle between vectors $p$ and $q$, $$cos(pq) = |p||q|/dot(p,q)$$

Calculate orthogonal vector from a vector $A$ in 2-D plane. $$ A = < b, a> $$ $$B = < -a, b>$$ $$C = < a, -b>$$.

$ p\times q = cross(p, q)= p.X*q.Y - p.Y*q.X = sin(pq)*|p|*|q| $

Properties of Cross Product

Returns scalar not a vector

Equals 0 $iff$ vectors are co-linear.

Absolute value of cross products is area of a parallelogram.

Positive $iff$ one should rotate $p$ counterclockwise (in shortest way)to make sure its in the same direction of $q$. same goes for clockwise. in one case vector p is on right side of vector q and in another case vector p is on left side.

Applications of Cross Product

Lines

Lines are defined by: $$ Ax +By+C = 0 $$ where A!=0 or/and B !=0.

Vector $ < A, B >$ is a normal vector. Also $ < -A, -B >$ is other normal vector.

Vector $<B, -A >$ is a directing vector, also $<-B, A >$ is a directing vector.

Distance from point to a line is $$D = \frac{|Ax+By+C|}{\sqrt{A^2 + B^2}}.$$ .

Sign matters as they give the side of a point with respect to the line.

Line-Line intersection

The first step to find the intersection is to find the situation , normally we don't have a intersection if lines are parallel or concise. Calculate the cross product of normal vectors of each line. if the $ cross( < A_1, B_1 >, < A_2, B_2 >) $ is $0$ then it is parallel or concise.

Next step is to find the point using Cramer's rule. $$ x = -\frac{det(C_1, B_1, C_2, B_2)}{det(A_1, B_1, A_2, B_2)} $$ and $$ y = -\frac{det(A_1, C_1, A_2, C_2)}{det(A_1, B_1, A_2, B_2)} $$

Remember, that Ax+By+C=0 is not always a line (it could be empty set or whole plane.)

Segment - Segment Intersection: Yes/No Algorithm

Segment and Segment intersect their bounding boxes should also intersect converse is not true. But its also possible that segments does not intersect but their bounding boxes intersect.

To check if the segments do not intersect only one of the conditions need to be true. $$ max(p1.X, q1.X) < min(p2.X, q2.X) $$ or $$ min(p1.X, q1.X) > max(p2.X, q2.X) $$

Check if the first segment is strictly left to the second one or to the strictly right. $$ max(p1.Y, q1.Y) < min(p2.Y, q2.Y) $$ or $$ min(p1.Y, q1.Y) > max(p2.Y, q2.Y) $$

Even if the bounding boxes intersect its possible that the segment do not intersect. Check if $$cross(p_1q_1, p_1q_2) \times cross(p_1q_1, p_1p_2) > 0$$ or $$cross(p_2q_2, p_2q_1) \times cross(p_2q_2, p_2q_2) > 0$$ then segments do not intersect. Otherwise they do intersect.}

Find the point of intersection of segment - segment intersection.

Given that the segments intersect, Find their point of intersection.

Find the $ cross( < A_1, B_1 >, < A_2, B_2 >) $ of normal vectors, if its zero then the segments must coincide. Check if the endpoints of the first segment lie on the second segment or vice-versa.

if $cross( < A_1, B_1 >, < A_2, B_2 >)$ not zero then construct lines $$ L_1 = (A_1, B_1, C_1) $$ $$ L_2 = (A_2, B_2, C_2) $$ and find their intersection using Cramer's Rule.