Geometry Basics - Summary


https://www.topcoder.com/community/competitive-programming/tutorials/geometry-concepts-basic-concepts/
Vectors
Vectors are the basis of a lot of methods for solving geometry problems. Formally, a vector is defined by a direction and a magnitude. In the case of two-dimension geometry, a vector can be represented as pair of numbers, x and y, which gives both a direction and a magnitude. For example, the line segment from (1,3) to (5,1) can be represented by the vector (4,-2). It’s important to understand, however, that the vector defines only the direction and magnitude of the segment in this case, and does not define the starting or ending locations of the vector.
Vector Addition
There are a number of mathematical operations that can be performed on vectors. The simplest of these is addition: you can add two vectors together and the result is a new vector. If you have two vectors (x1, y1) and (x2, y2), then the sum of the two vectors is simply (x1+x2, y1+y2). The image below shows the sum of four vectors. Note that it doesn’t matter which order you add them up in – just like regular addition. Throughout these articles, we will use plus and minus signs to denote vector addition and subtraction, where each is simply the piecewise addition or subtraction of the components of the vector.


Dot Product
The addition of vectors is relatively intuitive; a couple of less obvious vector operations are dot and cross products. The dot product of two vectors is simply the sum of the products of the corresponding elements. For example, the dot product of (x1, y1) and (x2, y2) is x1*x2 + y1*y2. Note that this is not a vector, but is simply a single number (called a scalar). The reason this is useful is that the dot product, A ⋅ B = |A||B|Cos(θ), where θ is the angle between the A and B. |A| is called the norm of the vector, and in a 2-D geometry problem is simply the length of the vector, sqrt(x2+y2). Therefore, we can calculate Cos(θ) = (A ⋅ B)/(|A||B|). By using the acos function, we can then find θ. It is useful to recall that Cos(90) = 0 and Cos(0) = 1, as this tells you that a dot product of 0 indicates two perpendicular lines, and that the dot product is greatest when the lines are parallel. A final note about dot products is that they are not limited to 2-D geometry. We can take dot products of vectors with any number of elements, and the above equality still holds.


Cross Product
An even more useful operation is the cross product. The cross product of two 2-D vectors is x1*y2 - y1*x2 Technically, the cross product is actually a vector, and has the magnitude given above, and is directed in the +z direction. Since we’re only working with 2-D geometry for now, we’ll ignore this fact, and use it like a scalar. Similar to the dot product, A x B = |A||B|Sin(θ). However, θ has a slightly different meaning in this case: |θ| is the angle between the two vectors, but θ is negative or positive based on the right-hand rule. In 2-D geometry this means that if A is less than 180 degrees clockwise from B, the value is positive. Another useful fact related to the cross product is that the absolute value of |A||B|Sin(θ) is equal to the area of the parallelogram with two of its sides formed by A and B. Furthermore, the triangle formed by A, B and the red line in the diagram has half of the area of the parallelogram, so we can calculate its area from the cross product also.





https://www.mathsisfun.com/algebra/vectors.html
This is a vector:
vector
A vector has magnitude (size) and direction:
vector magnitude and direction
The length of the line shows its magnitude and the arrowhead points in the direction.
We can add two vectors by joining them head-to-tail:
vector add a+b
And it doesn't matter which order we add them, we get the same result:
vector add b+a

Example: A plane is flying along, pointing North, but there is a wind coming from the North-West.

vector airplane, propellor and wind
The two vectors (the velocity caused by the propeller, and the velocity of the wind) result in a slightly slower ground speed heading a little East of North.
If you watched the plane from the ground it would seem to be slipping sideways a little.
vector airplane ahead and slightly sideways
Have you ever seen that happen? Maybe you have seen birds struggling against a strong wind that seem to fly sideways. Vectors help explain that

https://www.topcoder.com/community/competitive-programming/tutorials/geometry-concepts-basic-concepts/
Vectors
Vectors are the basis of a lot of methods for solving geometry problems. Formally, a vector is defined by a direction and a magnitude. In the case of two-dimension geometry, a vector can be represented as pair of numbers, x and y, which gives both a direction and a magnitude. For example, the line segment from (1,3) to (5,1) can be represented by the vector (4,-2). It’s important to understand, however, that the vector defines only the direction and magnitude of the segment in this case, and does not define the starting or ending locations of the vector.

Vectors are used to represent a quantity that has both a magnitude and a direction. The vector is normally visualized in a graph. A vector between A and B is written as
AB

The vectors standard position has its starting point in origin.
Magnitude
The component form of a vector is the ordered pair that describes the changes in the x- and y-values. In the graph above x1=0, y1=0 and x2=2, y2=5. The ordered pair that describes the changes is (x2- x1, y2- y1), in our example (2-0, 5-0) or (2,5).
Two vectors are equal if they have the same magnitude and direction. They are parallel if they have the same or opposite direction.
We can combine vectors by adding them, the sum of two vectors is called the resultant.
Adding Vector
In order to add two vectors, we add the corresponding components.
Add the two following vectors:
a=2,4,b1,6

We add the corresponding components
a+b=2+(1),4+6=1,10
X. Dot Product
https://www.mathsisfun.com/algebra/vectors-dot-product.html
Here are two vectors:
vectors
They can be multiplied using the "Dot Product" (also see Cross Product).

Calculating

The Dot Product gives a number as an answer (a "scalar", not a vector).
The Dot Product is written using a central dot:
a · b
This means the Dot Product of a and b
We can calculate the Dot Product of two vectors this way:
dot product magnitudes and angle
a · b = |a| × |b| × cos(θ)
Where:
|a| is the magnitude (length) of vector a
|b| is the magnitude (length) of vector bθ is the angle between a and b
So we multiply the length of a times the length of b, then multiply by the cosine of the angle between a and b

OR we can calculate it this way:
dot product components
a · b = ax × bx + ay × by
So we multiply the x's, multiply the y's, then add.
Both methods work!

Example: Calculate the dot product of vectors a and b:

dot product example
a · b = |a| × |b| × cos(θ)
a · b = 10 × 13 × cos(59.5°)
a · b = 10 × 13 × 0.5075...
a · b = 65.98... = 66 (rounded)
or we can calculate it this way:
a · b = ax × bx + ay × by
a · b = -6 × 5 + 8 × 12
a · b = -30 + 96
a · b = 66
Both methods came up with the same result (after rounding)
Also note that we used minus 6 for ax (it is heading in the negative x-direction)

Why cos(θ) ?

OK, to multiply two vectors it makes sense to multiply their lengths together but only when they point in the same direction.
So we make one "point in the same direction" as the other by multiplying by cos(θ):
dot product |a| cos(theta) dot product shine light
We take the component of a
that lies alongside b
 Like shining a light to see
where the shadow lies
THEN we multiply !
It works exactly the same if we "projected" b alongside a then multiplied:
Because it doesn't matter which order we do the multiplication:
|a| × |b| × cos(θ) = |a| × cos(θ) × |b|
dot product |b| cos(theta)

Right Angles

When two vectors are at right angles to each other the dot product is zero.

Example: Sam has measured the end-points of two poles, and wants to know the angle between them:

dot product 3d
We have 3 dimensions, so don't forget the z-components:
a · b = ax × bx + ay × by + az × bz
a · b = 9 × 4 + 2 × 8 + 7 × 10
a · b = 36 + 16 + 70
a · b = 122

Now for the other formula:
a · b = |a| × |b| × cos(θ)
But what is |a| ? It is the magnitude, or length, of the vector a. We can use Pythagoras:
  • |a| = √(42 + 82 + 102)
  • |a| = √(16 + 64 + 100)
  • |a| = √180
Likewise for |b|:
  • |b| = √(92 + 22 + 72)
  • |b| = √(81 + 4 + 49)
  • |b| = √134
And we know from the calculation above that a · b = 122, so:
a · b = |a| × |b| × cos(θ)
122 = √180 × √134 × cos(θ)
cos(θ) = 122 / (√180 × √134)
cos(θ) = 0.7855...
θ = cos-1(0.7855...) = 38.2...°

The Dot Product gives a scalar (ordinary number) answer, and is sometimes called the scalar product.
But there is also the Cross Product which gives a vector as an answer, and is sometimes called the vector product.

https://www.mathsisfun.com/algebra/vectors-cross-product.html
Two vectors can be multiplied using the "Cross Product(also see Dot Product)
vectors a and b
The Cross Product a × b of two vectors is another vector that is at right angles to both:
cross product

And it all happens in 3 dimensions!

Calculating

We can calculate the Cross Product this way:

cross product with angle and unit vector
a × b = |a| |b| sin(θ) n
  • |a| is the magnitude (length) of vector a
  • |b| is the magnitude (length) of vector b
  • θ is the angle between a and b
  • n is the unit vector at right angles to both a and b
So the length is: the length of a times the length of b times the sine of the angle between a and b,
Then we multiply by the vector n to make sure it heads in the right direction (at right angles to both a and b).

OR we can calculate it this way:

cross product components
When a and b start at the origin point (0,0,0), the Cross Product will end at:
  • cx = aybz − azby
  • cy = azbx − axbz
  • cz = axby − aybx

Example: The cross product of a = (2,3,4) and b = (5,6,7)

  • cx = aybz − azby = 3×7 − 4×6 = −3
  • cy = azbx − axbz = 4×5 − 2×7 = 6
  • cz = axby − aybx = 2×6 − 3×5 = −3
Answer: a × b = (−3,6,−3)

right hand rule

Which Direction?

The cross product could point in the completely opposite direction and still be at right angles to the two other vectors, so we have the:
"Right Hand Rule"
With your right-hand, point your index finger along vector a, and point your middle finger along vector b: the cross product goes in the direction of your thumb.

Cartesian coordinate system
笛卡儿坐标系Cartesian coordinate system),也称直角坐标系,是一种正交坐标系。参阅图1,二维的直角坐标系是由两条相互垂直、0点重合的数轴构成的。在平面内,任何一点的坐标是根据数轴上对应的点的坐标设定的。

Polar coordinate system
极坐标系是一个二维坐标系统。该坐标系统中任意位置可由一个和一段相对原点—极点的距离来表示。
极坐标系也有两个坐标轴:r(半径坐标)和\theta(角坐标、极角或方位角,有时也表示为\phit)。r坐标表示与极点的距离,\theta坐标表示按逆时针方向坐标距离0°射线(有时也称作极轴)的角度,极轴就是在平面直角坐标系中的x轴正方向


Polar angle
PolarAngle

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts