P T H I N K F A ST S

Competitive Programming
From Problem 2 Solution in O(1)

Computational Geometry
Point and Vector

Mostafa Saad Ibrahim

PhD Student @ Simon Fraser University
Cartesian coordinate system

Src: https://www.ltcconline.net/greenl/courses/152a/functgraph/coord.8.gif
Cartesian coordinate system

Src: http://www.c-jump.com/bcc/common/Talk3/Math/Matrices/const_images/3d_coord_systems.png
 Polar coordinate system
The r and θ coordinates of a point P measure respectively the distance from P to
the origin O and the angle between the line OP and the polar axis.

Src: http://images.tutorvista.com/cms/images/67/polar-coordinate1.png https://upload.wikimedia.org/wikipedia/commons/thumb/7/78/Polar_to_cartesian.svg/250px-Polar_to_cartesian.svg.png

Cartesian ⇔ Polar Conversions

For examples: See

Src: http://www.kb6nu.com/wp-content/uploads/2012/08/rectangular-polar-coordinates.jpg
Vector

◼ Vector = Direction + Magnitude

◼ For example, the line segment from a = (1,3) to b = (5,1)
can be represented by the vector v = b - a = (4,-2)
◼ Magnitude = norm of the vector
◼ Given (x, y), we can find angle / magnitude

Src: http://www.dummies.com/how-to/content/how-to-find-a-vectors-magnitude-and-direction.html
 Linear independence of vectors
- a set of vectors is said to be linearly dependent if one of the vectors in the set can be
defined as a linear combination of the others
- e.v. u(1, 3) and v = (2, 6)...notice: v = 2 u (dependent)
- Recall cos(angle = 0) = 1

Src: https://en.wikipedia.org/wiki/Linear_independence http://i.stack.imgur.com/NKvYQ.gif

 Perpendicular Vectors
Two vectors are perpendicular if and only if their angle is a right angle

Src: https://dj1hlxw0wr920.cloudfront.net/userfiles/wyzfiles/3b4796bf-2911-46d8-8dad-9d1d96e6b389.gif
 Orthogonal vectors
Set of vectors is orthogonal if and only if they are pairwise perpendicular

Src: https://dj1hlxw0wr920.cloudfront.net/userfiles/wyzfiles/3b4796bf-2911-46d8-8dad-9d1d96e6b389.gif http://lolengine.net/raw-attachment/blog/2013/09/21/picking-orthogonal-vector-combing-coconuts/math-vector-ortho.png

 Normal Vector
The normal vector to a surface is a vector which is perpendicular to the surface at a given
point

Src: http://mathworld.wolfram.com/NormalVector.html https://en.wikipedia.org/wiki/Normal_(geometry)#/media/File:Surface_normal_illustration.svg

Vector Addition
if a = (a1, a2) and b (b1, b2), then a + b = (a1+b1, a2+b2)

Src: http://mathinsight.org/media/image/image/vector_2d_add.png http://community.topcoder.com/i/education/geometry01.png

Vector Subtraction

Src: http://hotmath.com/hotmath_help/topics/adding-and-subtracting-vectors.html
 Vector Dot/Scalar/Inner Product
Algebraically, sum of the products of the corresponding entries

Geometrically, the product of the Euclidean magnitudes of the two vectors and the cosine
of the angle between them
Vector Dot/Scalar/Inner Product
Scalar projection of a vector A in the direction of a Euclidean vector B

if A and B are orthogonal, then the angle between them is 90°

if they are codirectional, then the angle between them is 0°

Src: https://upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Dot_Product.svg/2000px-Dot_Product.svg.png http://mathinsight.org/media/image/image/dot_product_projection.png

Vector Dot/Scalar/Inner Product

Src: https://chortle.ccsu.edu/VectorLessons/vch07/acuteORobtuse.gif http://amsi.org.au/ESA_Senior_Years/SeniorTopic2/2d/2d_2content_6.html

Vector Dot/Scalar/Inner Product

If a ⋅ b = a ⋅ c and a ≠ 0, then we can write: a ⋅ (b − c) = 0

means that a is perpendicular to (b − c), and therefore b ≠ c.

 Cross/Vector Product
The cross product, a × b, is a vector that is perpendicular to both a and b and therefore
normal to the plane containing them.

Finding the direction of the cross product by the right-hand rule

Notice: A x B = vector…..But A.B = Scaler

Src: http://mathworld.wolfram.com/NormalVector.html https://en.wikipedia.org/wiki/Normal_(geometry)#/media/File:Surface_normal_illustration.svg

 Cross/Vector Product
The magnitude of the cross product can be interpreted as the positive area of the
parallelogram having a and b as sides

The triangle formed by a, b has half of the area of the parallelogram,

so we can calculate its area from the cross product

Given two unit vectors, their cross product has a magnitude of

- one if the two are perpendicular and a magnitude of zero if the two are parallel.
- The converse is true for the dot product of two unit vectors.
Src: https://en.wikipedia.org/wiki/Cross_product
 Cross/Vector Product
Compute the volume V of a parallelepiped having a, b and c as edges by using a
combination of a cross product and a dot product
Cross/Vector Product
Cross/Vector Product
Cross/Vector Product
 Standard basis
Set of unit vectors pointing in the direction of the axes of a Cartesian coordinate system
Cross Product and Standard basis
Geometric Operations

Src: http://homepages.inf.ed.ac.uk/rbf/HIPR2/figs/affhei.gif http://3.bp.blogspot.com/-wvk7fpfFUu0/U5NrFOYskEI/AAAAAAAAABg/PTJGVKOnEd4/s1600/art-affines.png

Euclidean Transformations

◼ A translation, a rotation, or a reflection

◼ Preserve length and angle measure.
◼ The shape of a geometric object will not
change.
◼ E.g. lines transform to lines, circles transform to circles
◼ See notes for affine
◼ Following notes from here
Euclidean: Translation
Add vector(h, k) to point (x, y)

Src: http://www.tutorialspoint.com/computer_graphics/2d_transformation.htm
Euclidean: Translation

◼ We can represent using equation or matrix

◼ Matrix 1 for translation, matrix 2 for undo
◼ Multiply M1 * M2 = = Identity
◼ Line Ax + By + C = 0 ⇒
◼ Ax' + By' + (-Ah - Bk + C) = 0.
Euclidean: Rotation
- If a point (x, y) is rotated an angle a about the coordinate origin to become a new
point (x', y')
- Please read how to get such equations

Src: http://www.tutorialspoint.com/computer_graphics/2d_transformation.htm
Euclidean: Rotation

◼ Line Ax + By + C = 0 ⇒
◼ (Acosa - Bsina)x' + (Asina + Bcosa)y' + C = 0
Euclidean: Reflection - Special

Src: http://slideplayer.com/slide/1398961/
Euclidean: Reflection - Special

Src: http://www.tutorialspoint.com/computer_graphics/2d_transformation.htm
Euclidean: Reflection
Generally, reflection across a line through the origin making an angle theta with the
x-axis, is equivalent to replacing every point with coordinates (x, y) by the point with
coordinates (x′,y′), where
Euclidean: Composition

◼ We can do several operations together.

◼ Just multiply their matrices
◼ Rotation around origin, then translation
 ‫ﺗﻢ ﺑﺤﻤﺪ ﷲ‬

‫ﻋﻠﻤﻜﻢ ﷲ ﻣﺎ ﯾﻨﻔﻌﻜﻢ‬

‫وﻧﻔﻌﻜﻢ ﺑﻤﺎ ﺗﻌﻠﻤﺘﻢ‬

‫وزادﻛﻢ ﻋﻠﻤﺎ ً‬