Computational Geometry

Computational Geometry
Vincent Chiu
19 Mar, 2022
 Computational Geometry

Table of Contents
1. Points, Lines, Segments
2. Vectors
3. Polygons
4. Convex Hull
5. Precision Handling
6. More
 Computational Geometry

DSE Coordinate Geometry – Points

In Cartesian coordinate plane, each point is
defined by a pair of coordinates !, #
● We usually call the origin 0, 0 as %

For example,
● & −2, −1
● * 0, 3
● , 3, 2
 Computational Geometry

Points
How do we store the points in our C++ program?
● Is the following way good? sorry no syntax highlighting

double xa, ya, xb, yb, x[200], y[200];

double dist(double x1, double y1, double x2, double y2) {
// to be implemented...
}
cout << dist(xa, ya, x[87], y[87]) << endl;
 Computational Geometry

Points – struct
How do we store the points in our C++ program?
● We should use struct!

struct Point {
double x = 0, y = 0;
Point() {}
Point(double x, double y) : x(x), y(y) {}
}; // don’t forget the semi-colon ;
 Computational Geometry

Points – struct
How do we store the points in our C++ program?
● We should use struct!

double dist(Point p1, Point p2) {

// to be implemented...
}

Point a, b(5, 4), p[200];

cout << dist(a, p[87]) << endl;
 Computational Geometry

Output Points
● Operator overloading (see “Programming in C++” 2021 Slides P.54 - 60)

ostream& operator<<(ostream& os, const Point& p) {

os << p.x << " " << p.y;
return os;
}

cout << b << endl; // 5 4

 Computational Geometry

DSE Coordinate Geometry – Lines

● A straight line having infinite length
● Different ways to represent a line:
!"!! ! "!
○ Two-point form #"#!
= #" "#!
" !

○ Point-slope form " − "$ = $ % − %$

○ Slope-intercept form " = $% + '

○ General form (% + )" + * = 0
 Computational Geometry

DSE Coordinate Geometry – Lines

Two-point form
● Fix a line by two points: -! !! , #! and -" !" , #"
● Slope of the line . = %!$%"
# $#
! "

A point - !, # is on the line -! -" iff:

# − #! #" − #!
.&&" = .&"&! , 0. 2. = =.
! − !! !" − !!

In other words, -, -! , -" are collinear

 Computational Geometry

Collinear Points – Implementation

=
#$#" #!$#"
Three points are collinear iff
%$%" %!$%"
● To avoid division by zero, rearrange the terms:

# − #! !" − !! = #" − #! ! − !!

bool is_collinear(Point a, Point b, Point c) {

return (a.y-b.y)*(a.x-c.x) == (a.x-b.x)*(a.y-c.y);
}
 Computational Geometry

Collinear Points
=
#$#" #!$#"
Three points are collinear iff
%$%" %!$%"
● Further expanding the terms:

# − #! !" − !! = #" − #! ! − !!
!" # − !! # − !" #! + !! #! = !#" − !! #" − !#! + !! #!
!#! − !! # + !! #" − !" #! + !" # − !#" = 0

! #! − #" + # !" − !! + !! #" − !" #! = 0

 Computational Geometry

Collinear Points
First one: !#! − !! # + !! #" − !" #! + !" # − !#" = 0
● Any special meanings?

Second one: ! #! − #" + # !" − !! + !! #" − !" #! = 0

● Convert two-point form to general form
 Computational Geometry

DSE Coordinate Geometry – Lines

Point-slope form
● Slope between - !, # and -' !' , #' equals slope of the line .:

# − #'
=.
! − !'
# − #' = . ! − !'
 Computational Geometry

DSE Coordinate Geometry – Lines

Slope-intercept form
● Set !' = 0, i.e. choose -' 0, #' , then #' is the #-intercept of the line,
denoted by 4:

#−4 =. !−0

# = .! + 4
 Computational Geometry

DSE Coordinate Geometry – Lines

Rearrange point-slope form to get the #-intercept:

# − #' = . ! − !'

# = .! + #' − .!'

⇒ 4 = #' − .!'
 Computational Geometry

DSE Coordinate Geometry – Lines

General form &! + *# + , = 0
● To slope-intercept form: # = − !+ −
( *
) )

● Slope . = −
(
)

● #-intercept = − : Set ! = 0
*
)
● !-intercept = − (: Set # = 0
*
 Computational Geometry

DSE Coordinate Geometry – Lines

Compare different representations:
● Slope-intercept form and two-point form are more intuitive
● But need to handle the case . = ∞: (Vertical line)
○ Two-point form: %% = %&
○ Slope-intercept form: no "-intercept
● General form is good because it really is more “general” :)
● We have converted two-point form to general form:

! #! − #" + # !" − !! + !! #" − !" #! = 0

( ) *
 Computational Geometry

DSE Coordinate Geometry – Segments

● A straight line having infinite finite length
● We can represent a segment by
its two endpoints !! , #! and !" , #"
 Computational Geometry

DSE Coordinate Geometry – Distances

Distance between points !! , #! and !" , #" :
● Euclidean distance = !" − !! " + #" − #! "

● Manhattan distance = !" − !! + #" − #!

For example, for points & 1, 1 and * 5, 4 :

● Euclidean distance =
5 − 1 " + 4 − 1 " = 25 = 5
● Manhattan distance =
5−1 + 4−1 =4+3=7
 Computational Geometry

Distances – Implementation
Distance between points !! , #! and !" , #" :
● Euclidean distance = !" − !! " + #" − #! "

● Manhattan distance = !" − !! + #" − #!

double dist(Point p1, Point p2) {

double dx = p2.x – p1.x;
double dy = p2.y – p1.y;
return sqrt(dx * dx + dy * dy);
}
 Computational Geometry

DSE Coordinate System – Polar Coordinates

In polar coordinate plane, each point is
defined by a pair of coordinates :, ;
● %(0, ;) is called the pole.
● > is called the polar axis.

Notice the angle with arrow: it is measured

anti-clockwise, therefore signed
● +ve: counter-clockwise (CCW)
● -ve: clockwise (CW)
● e.g. 3, 60° = 3, 420° = 3, −300°
 Computational Geometry

DSE Coordinate System – Conversion

Convert polar coordinates to rectangular
coordinates:
● ! = : cos D
● # = : sin D

Convert rectangular coordinates to polar

coordinates:
● := !" + #"
● D = tan$!
#
%
 Computational Geometry

DSE Coordinate System – Trigonometric Functions

Extend the definition of trigonometric
functions beyond acute angles 0° < D < 90°:
● −: ≤ !, # ≤ :
● cos D = +
%

● sin D =
#
+
● tan D =%
#
 Computational Geometry

DSE Coordinate System – Trigonometric Functions

 Computational Geometry

Angle in Radians
● The radian (rad) is the SI unit for
measuring angles

● ; in radians = =
,+- ./0123 7
+,4567 +
● L rad = 180°
 Computational Geometry

Angle in Radians
● From now on, unless otherwise specified,
angles will be measured in radians:
1 L 1
sin 30° = ⇒ sin rad =
2 6 2

● We often don’t write the unit rad:

L 1
sin =
6 2
 Computational Geometry

Trigonometric Functions
● Why introduce radians? Because <cmath> uses radian measure!

const double PI = 4*atan(1);

int main() {
cout << PI << endl;
cout << sin(-5 * PI / 6) << endl; // -0.5
cout << acos(-0.5) * 180 / PI << endl; // 120
}
 Computational Geometry

Converting between Coordinate Systems

Convert rectangular coordinates to polar coordinates:
● := !" + #"
● D = tan$! ?
#
%

● atan ! = tan$! ! returns values in − ,

8 8
" "

● asin ! = sin$! ! returns values in − ,

8 8
" "
● acos ! = cos $!
! returns values in 0, L
● None of them seems to cover the whole circle…
 Computational Geometry

Converting between Coordinate Systems

Solution:
D = QRQS2 #, !

● QRQS2 #, ! returns values in −L, L

struct Point {
double len() const { return sqrt(x * x + y * y); }
double rad() const { return atan2(y, x); }
}
 Computational Geometry

Table of Contents
1. Points, Lines, Segments
2. Vectors
3. Polygons
4. Convex Hull
5. Precision Handling
6. More
 Computational Geometry

Vectors
● Don’t get confused with std::vector in C++
● Vector has magnitude (or length) and direction
● We usually represent a vector U⃗ as U% , U#
● They have no position, just “an arrow”
For example,
● &* = V = +4, +3
● ,W = U⃗ = +4, +3
● XY = Z = −4, −3
● V = U⃗ ≠ Z, while Z = −V
 Computational Geometry

Vectors
● Note that vectors only reflect the direction and magnitude (length) but
not the position
● Also, vector is not a description of coordinates
● But if we set the “tail” of the vector to be
the origin %,
● We can see how the endpoint/”head” of the
vector corresponds to the coordinates of the
head: coordinate vector
● So, treat them as the same at this stage :)
 Computational Geometry

Vector Operations – Basics

● Addition: V + U⃗ = V% + U% , V# + U#
● Subtraction: V − U⃗ = V% − U% , V# − U#

● Norm (Length): V = V%" + V#"

For example,
● V = +4, +2 , U⃗ = −1, +5
● Z = V + U⃗ = 4 − 1, 2 + 5 = +3, +7
● V = Z − U⃗ = Z + −U⃗
● V = 4" + 2" = 2 5, U⃗ = −1 " + 5" = 26
 Computational Geometry

Vector Operations – Basics – Implementation

#define Point Vector
struct Vector {
// ...
Vector(double x) : x(x), y(0) {} // conversion constructor
};
Vector operator+(const Vector& u, const Vector& v) {
return Vector(u.x + v.x, u.y + v.y);
}
Vector operator-(const Vector& u, const Vector& v) {
return Vector(u.x - v.x, u.y - v.y);
}
 Computational Geometry

Vector Operations – Basics – Implementation

Example:

Vector d(-10, 0), f(7, 3);

cout << d.rad() << endl; // 3.14159
cout << d.len() << endl; // 10
cout << d + f << endl; // -3 3
cout << d - f << endl; // -17 -3
cout << 0 - f << endl; // -7 -3
 Computational Geometry

Vector Operations – Products

Dot product: V · U⃗ = V% U% + V# U#
● V · U⃗ = V U⃗ cos ;
● where ; is the angle from ] to ^
● Since cos = 0, V and U⃗ are perpendicular
8
"
iff V · U⃗ = 0 for V, U⃗ ≠ 0
For example,
● V · _⃗ = V · R⃗ = 4 10 cos 108.43° = −4
● V · U⃗ = V · Z = 4 10 cos 71.57° = 4
 Computational Geometry

Vector Operations – Products

Cross product: V×U⃗ = V% U# − V# U%
(with a direction of a, not important right now)
● V×U⃗ = V U⃗ sin ;
● where ; is the angle from ] to ^
● Since sin 0 = sin L = 0, V and U⃗ are parallel
iff V×U⃗ = 0 for V, U⃗ ≠ 0
● Δarea = V×U⃗ (will be covered later)
!
"
 Computational Geometry

But Why?
Dot product: V · U⃗ = V% U% + V# U#
● V · U⃗ = V U⃗ cos ;

Cross product: V×U⃗ = V% U# − V# U%

● V×U⃗ = V U⃗ sin ;

V% U% + V# U# = V U⃗ cos ; , V% U# − V# U% = V U⃗ sin ; ???

 Computational Geometry

Table of Contents
1. Points, Lines, Segments
2. Vectors
Extra: Complex Numbers
3. Polygons
4. Convex Hull
5. Precision Handling
6. More
 Computational Geometry

DSE Complex Numbers – Basics

Complex number Q + c0 ∈ ℂ, where Q, c ∈ ℝ and 0 " = −1, i.e. −1
● Add/Subtract: Q + c0 ± 4 + h0 = Q ± 4 + c ± h 0
● Multiplication: Q + c0 4 + h0 = Q4 − ch + Qh + c4 0
● Division:
Q + c0 Q + c0 4 − h0 Q + c0 4 − h0 Q + c0 4 − h0
= · = =
4 + h0 4 + h0 4 − h0 4 " − h0 " 4 " + h"
 Computational Geometry

Complex Plane
Geometric representation of complex numbers!
● Real axis, Imaginary axis
● a = Q + c0 ⇒ Q, c = ℜ a , ℑ a
● : = a = Q" + c "
● Argument D
 Computational Geometry

Complex Number – Implementation

Now we can map complex numbers to coordinates (rectangular and polar)!
● Polar to complex: :, ; ⇒ : cos ; , : sin ; = : cos ; + 0 sin ;

#define Complex Vector

Complex operator*(const Complex& u, const Complex& v){

return Complex(u.x * v.x - u.y * v.y,
u.x * v.y + u.y * v.x);
}
 Computational Geometry

Complex Plane
Complex conjugate of a = Q + c0 = :, D :
a̅ = Q − c0 = :, −D
Properties:
● a ± Z = a̅ ± Z,l aZ = a̅ Z,
l a/Z = a/̅ Z
l
● a a̅ = a " = Q " + c "
= =
! 9̅ 9̅
●
9 9 9̅ 9!

Complex conjg(const Complex& z){

return Complex(z.x, -z.y);
}
 Computational Geometry

Know your calculator :)

 Computational Geometry

Know your calculator :)

 Computational Geometry

Know your calculator :)

● Try this in your calculator:

5∠50 × 3∠30 ▶ :∠;

5∠50 ÷ 3∠30 ▶ :∠;

 Computational Geometry

Know your calculator :)

● From calculator, we have this interesting fact:

:! ∠;! :" ∠;" = :! :" ∠ ;! + ;"

:! ∠;! :!
= ∠ ;! − ;"
:" ∠;" :"

● ⇒ Complex Multiplication = Rotate and Scale

 Computational Geometry

Euler’s Formula (skip)

● Euler’s Formula:

2 5; = cos D + 0 sin D
⇒ a = Q + c0 = :2 5;

● Euler’s Identity:

2 58 = cos L + 0 sin L = −1
2 58 + 1 = 0
 Computational Geometry

Euler’s Formula – Proof (skip)

● Taylor Series:

! !" !< !=
2% =1+ + + + +⋯
1! 2! 3! 4!
!" !=
cos ! = 1 − + −⋯
2! 4!
!< !>
sin ! = ! − + −⋯
3! 5!
 Computational Geometry

Euler’s Formula – Proof (skip)

0; 0; " 0; < 0; =
2 5? =1+ + + + +⋯
1! 2! 3! 4!
; " 0; < ; =
= 1 + 0; − − + −⋯
2! 3! 4!
;" ;= ;<
= 1− + −⋯ +0 ;− +⋯
2! 4! 3!
= cos ; + 0 sin ;
 Computational Geometry

Euler’s Formula – Properties (skip)

Now that the angle becomes the exponent, it explains our observation:
● Multiplication: :! 2 5?" · :" 2 5?! = :! :" 2 5 ?"@?!
+"/ #$"
= 25
+" ?"$?!
● Division:
+!/ #$! +!
● Exponentiation: :2 5? 0
= : 0 2 50? (De Moivre’s formula)
 Computational Geometry

Complex Multiplication
a! = Q + c0 = :! ∠;! , a" = 4 + h0 = :" ∠;"

a" a!̅ = 4 + h0 Q − c0
= Q4 + ch + Qh − c4 0

a" a!̅ = :" ∠;" :! ∠ −;!

= :! :" ∠ ;" − ;!

⇒ Q4 + ch = :! :" cos ;" − ;! , Qh − c4 = :! :" sin ;" − ;!

 Computational Geometry

Compound Angle Formula (skip)

● We can also obtain some intuition on some of
the trigonometric identities:

cos r ± s = cos r cos s ∓ sin r sin s

sin r ± s = sin r cos s ± cos r sin s

 Computational Geometry

Table of Contents
1. Points, Lines, Segments
2. Vectors (cont.)
3. Polygons
4. Convex Hull
5. Precision Handling
6. More
 Computational Geometry

Vector Operations – Products

Dot product: V · U⃗ = V% U% + V# U#
● V · U⃗ = V U⃗ cos ;
● where ; is the angle from ] to ^
● Since cos = 0, V and U⃗ are perpendicular
8
"
iff V · U⃗ = 0 for V, U⃗ ≠ 0
For example,
● V · _⃗ = V · R⃗ = 4 10 cos 108.43° = −4
● V · U⃗ = V · Z = 4 10 cos 71.57° = 4
 Computational Geometry

Vector Operations – Products

Cross product: V×U⃗ = V% U# − V# U%
(with a direction of a, not important right now)
● V×U⃗ = V U⃗ sin ;
● where ; is the angle from ] to ^
● Since sin 0 = sin L = 0, V and U⃗ are parallel
iff V×U⃗ = 0 for V, U⃗ ≠ 0
● Δarea = V×U⃗ (will be covered later)
!
"
 Computational Geometry

Vector Operations – Products – Implementation

double dot(const Vector& u, const Vector& v) {
return u.x * v.x + u.y * v.y; // version1
return (v * conjg(u)).x; // version2
}

double cross(const Vector& u, const Vector& v) {

return u.x * v.y - u.y * v.x; // version1
return (v * conjg(u)).y; // version2
}
 Computational Geometry

Vector Operations – Products – Implementation

Example:

Vector f(7, 3), g(-5, 4);

cout << f * g << endl; // -47 13 !!!
// complex multiplication
cout << dot(f, g) << endl; // -23
cout << cross(f, g) << endl; // 43
 Computational Geometry

Vector Operations – Products – Properties

● Since cos −; = cos ; and sin −; = − sin ;,

● V · U⃗ = V U⃗ cos ; V×U⃗ = V U⃗ sin ;

● V · U⃗ = U⃗ · V V×U⃗ = − U×V
⃗
● V · U⃗ + Z = V · U⃗ + V · Z V× U⃗ + Z = V×U⃗ + V×Z
● uV · U⃗ = V · uU⃗ = u V · U⃗ uV×U⃗ = V×uU⃗ = u V×U⃗
● V·V = V " V×V = 0
 Computational Geometry

Short Break
 Computational Geometry

Vector Operations – Transformations

● Scalar multiplication: uV = uV% , uV#
● Rotation (by ; CCW):
cos ; − sin ; V% V% cos ; − V# sin ;
sin ; cos ; V# = V% sin ; + V# cos ;
 Computational Geometry

Vector Operations – Transformations – Implement

● Recall: Complex Multiplication = Rotate and Scale!
● Previously implemented:

struct Vector {
// ...
Vector(double x) : x(x), y(0) {} // conversion constructor
};
Complex operator*(const Complex& u, const Complex& v){
return Complex(u.x * v.x - u.y * v.y,
u.x * v.y + u.y * v.x);
}
 Computational Geometry

Vector Operations – Transformations – Implement

● Scalar multiplication: because of the conversion constructor, complex
multiplication supports double as input.
● Rotation:

Vector rotate(const Vector& u, double rad) {

return u * Vector(cos(rad), sin(rad));
}
Vector rotate(const Vector& u, double rad, const Vector& p) {
return p + rotate(u - p, rad); // rotate u about p
}
 Computational Geometry

Vector Operations – Transformations – Implement

Example:

Vector f(7, 3);

cout << 2 * f << endl; // 14 6
cout << f * -3 << endl; // -21 -9
cout << rotate(f, PI / 3) << endl; // 0.901924 7.56218
cout << rotate(f, PI / 3, g) << endl;
// 1.86603 13.8923
 Computational Geometry

Vectors Usage – Collinearity

● V and U⃗ are parallel iff V×U⃗ = 0
● New implementation of is_collinear:

bool is_collinear(Point a, Point b, Point c) {

return cross(b - a, c - a) == 0;
}
 Computational Geometry

Vectors Usage – On Segment

bool on_segment(Point P, Point E1, Point E2) {
return (cross(E1 - P, E2 - P) == 0)
&& (dot(E1 - P, E2 - P) <= 0);
}
For example,
Point X(5, 4), Y(3, 0), Z(6, 6);
cout << is_collinear(X, Y, Z) << endl; //1
cout << on_segment(X, Y, Z) << endl; //1
cout << on_segment(Y, Z, X) << endl; //0
cout << on_segment(Y, Y, Z) << endl; //1
 Computational Geometry

Vectors Usage – CW or CCW

● V×U⃗ = V U⃗ sin ;

V×U⃗ > 0

V×U⃗ < 0
 Computational Geometry

Vectors Usage – Sorting the points by CCW

struct Vector {
// ...
int quadrant() const {
if (x >= 0 && y >= 0)
return 1;
else if ( //... V×U⃗ > 0
}
}
bool cmp(Point A, Point B) {
if (A.quadrant() == B.quadrant())
return cross(A, B) > 0;
return A.quadrant() < B.quadrant();
}

V×U⃗ < 0
 Computational Geometry

Vectors Usage – Identifying right turn

bool is_right_turn(Point A, Point B, Point C) {
return cross(B - A, C - B) < 0;
}
For example,
Point P0(0, 0), P1(0, 3);
cout << is_right_turn(P0, P1, Point(-1, 5))
<< endl; // 0
cout << is_right_turn(P0, P1, Point(0, 5))
<< endl; // 0
cout << is_right_turn(P0, P1, Point(1, 5))
<< endl; // 1
 Computational Geometry

Table of Contents
1. Points, Lines, Segments
2. Vectors
3. Polygons
4. Convex Hull
5. Precision Handling
6. More
 Computational Geometry

DSE Trigonometry
● Area of triangle = " Qℎ = " Qc sin ,
! !

● Sine formula:
Qc4 Q c 4
= = = = W = 2x
2×Q:2Q sin & sin * sin ,

● Cosine formula:
4 " = Q − c cos , " + c sin , "

= Q" + c " − 2Qc cos ,

 Computational Geometry

DSE Trigonometry
● Heron’s formula:
Combine and expand

1
&:2Q = Qc sin ,
2
sin , = 1 − cos " ,
Q" + c " − 4 "
cos , =
2Qc
 Computational Geometry

Area of Triangle – Cross Product

V×U⃗ = V U⃗ sin ;
⇒ Δarea = V×U⃗
!
"

Signed area = V×U⃗

!
"
 Computational Geometry

Polygons
Let’s follow the nice tutorial prepared by Percy in 2019!
 'SQTYXEXMSREP +ISQIXV]

'SRXIRX
 3RLQWV /LQHV 6HJPHQWV

 9HFWRUV

 3RO\JRQV

 &RQYH[ +XOO

 3UHFLVLRQ +DQGOLQJ

 0RUH

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW
• 6LPSOH SRO\JRQ QR VHOILQWHUVHFWLRQ H[FHSW DW YHUWLFHV FRQQHFWLQJ
QHLJKERULQJ OLQH VHJPHQWV
• &RQYH[ SRO\JRQ $ VLPSOH SRO\JRQ ZLWK HYHU\ LQWHULRU DQJOH QR PRUH
WKDQ π RU r
• 6WUFLWO\ FRQYH[ SRO\JRQ $ VLPSOH SRO\JRQ ZLWK HYHU\ LQWHULRU DQJOH OHVV
WKDQ π RU r

榀㸖曢免⥎㝾⌠Ⅎ䫝峤 1RQVLPSOH &RQFDYH SRO\JRQ &RQYH[ SRO\JRQ

+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
SRO\JRQ
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  -QTPIQIRXEXMSR
• +RZ GR ZH UHSUHVHQW D SRO\JRQ"
• $V D OLVW RI SRLQWV p0 , p1 , . . . , pN −1
• $ OLQH VHJPHQW FRQQHFWLQJ
• pi DQG pi+1 IRU DOO 0 ≤ i < N − 1
• pN −1 DQG p0
bi`m+i SQHv;QM &
p2+iQ`ISQBMi= Tc
SQHv;QMUV &'
SQHv;QMUp2+iQ`ISQBMi= TV , TUTV &'
'c

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  -QTPIQIRXEXMSR
([DPSOH
SQHv;QM TQHv 4 SQHv;QMU&SQBMiUy- yV- SQBMiU9- yV- SQBMiU9- jV'Vc
+Qmi II ]7B`bi TQBMi 4 ] II TQHvXT(y)Xt II ] ] II TQHvXT(y)Xv II 2M/Hc
7Q` USQBMi Ti , TQHvXTV &
+Qmi II TiXt II ] ] II TiXv II 2M/Hc
'

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
5HFDOOLQJ WKDW WKH DUHD RI WULDQJOH IRUPHG E\ "u DQG "v LV
1
VLJQHG DUHD ("u × "v )
2
ΖQ RWKHU ZRUGV
• LI "u WR "v LV LQ &&: GLUHFWLRQ  GLUHFWLRQ  DUHD ! 
• LI "u WR "v LV LQ &: GLUHFWLRQ  GLUHFWLRQ  DUHD  

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
)RU D FRQYH[ SRO\JRQ ZH FDQ GLYLGH WKH DUHD LQWR N − 2 WULDQJOHV
∆p0 p1 p2 , ∆p0 p2 p3 , . . . , ∆p0 pN −2 pN −1

!
N −2
1 ! −−→ −−−−→
N −2
7KH DUHD RI WKH SRO\JRQ Area(∆p0 pi pi+1 ) = p0 pi × p0 pi+1
2
i=1 i=1

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE  -QTPIQIRXEXMSR

!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1
bi`m+i SQHv;QM &
ff XXX
/Qm#H2 `2UV +QMbi & ff bB;M2/ `2
/Qm#H2 bmK 4 yc
7Q` UBMi B 4 Rc B I4 TXbBx2UV @ kc BYYV
bmK Y4 UT(B) @ T(y)VX+`QbbUT(B Y R) @ T(y)Vc
`2im`M yX8 bmKc
'
'c

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1
$FWXDOO\ WKLV IRUPXOD ZRUNV RQ DQ\ VLPSOH SRO\JRQ ERWK FRQYH[ DQG FRQFDYH 
:K\" EHFDXVH WKH FURVV SURGXFW LV VLJQHG

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 'SQTYXEXMSREP +ISQIXV]

4SP]KSRW  %VIE
!
N −2
$UHD 1 −
p−→ −−−−→
2 0 pi × p0 pi+1
i=1
7KLV '2(6 127 ZRUN RQ QRQVLPSOH SRO\JRQ

榀㸖曢免⥎㝾⌠Ⅎ䫝峤
+RQJ .RQJ 2O\PSLDG LQ ΖQIRUPDWLFV
 Computational Geometry

Polygons – Area – Remarks

● In Percy’s tutorial, we calculated the
area of the polygon in this way:

B$"
1
&:2Q = y -' -5 ×-' -5@!
2
5A!
 Computational Geometry

Polygons – Area – Remarks

● In fact, the area can also be calculated
in this way: -' = -B

B$!
1
&:2Q = y %-5 ×%-5@!
2
5A'
 Computational Geometry

Polygons – Area – Remarks

● In fact, the area can also be calculated
in this way: -' = -B

B$!
1
&:2Q = y %-5 ×%-5@!
2
5A'

● In CCW direction, positive area:

 Computational Geometry

Polygons – Area – Remarks

● In fact, the area can also be calculated
in this way: -' = -B

B$!
1
&:2Q = y %-5 ×%-5@!
2
5A'

● In CCW direction, negative area:

 Computational Geometry

Collinear Points – Recall

Points -, -! , -" are collinear iff

!#! − !! # + !! #" − !" #! + !" # − !#" = 0

● Any special meanings?

● ⇒ &:2Q z{ Δ--! -" = 0
 Computational Geometry

Table of Contents
1. Points, Lines, Segments
2. Vectors
3. Polygons
4. Convex Hull
5. Precision Handling
6. More
 Computational Geometry

Convex Hull
A convex hull is the smallest convex polygon that contains all the given points
 Computational Geometry

Convex Hull
Let’s follow the nice tutorial prepared by Alex Tung in 2017!
<Finding convex hull>
• Given ¨ points |[ , |] , … , |Æ on plane, now we want to find a
smallest convex polygon H which contains all ¨ points
• Fact: we can always choose the vertices of H to be a subset of
{|[ , |] , … , |Æ } (why?)

• Next question: which of the points belong to H?

• Example
• Our convex hull is ∑£∏¢íπ∑
• An O(n log n) algorithm exists
• The best deterministic algorithm one can produce is Ω(n log n) (as
a function of n only), since finding convex hull can be reduced to
sorting

• See O(n log h) algorithms (h := |H|) here:

https://en.wikipedia.org/wiki/Convex_hull_algorithms
• O(n log n) in worst case, but in random cases we expect ℎ << º
<Andrew’s algorithm>
• Based on Graham scan
• O(n log n) for sorting points (in a certain order)
• The rest is O(n)
• Step 1: sort points by x then by y
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=1
STACK = [|[ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=2
STACK = [|[ , |] ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=3
STACK = [|[ , |] , |Ü ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=4
STACK = [|[ , |] , |Ü , |à ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=4
STACK = [|[ , |] , |Ü , |à ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=4
STACK = [|[ , |] , |à ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=5
STACK = [|[ , |] , |à , |æ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=6
STACK = [|[ , |] , |à , |æ , |ø ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=6
STACK = [|[ , |] , |à , |æ , |ø ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=6
STACK = [|[ , |] , |à , |ø ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=7
STACK = [|[ , |] , |à , |ø , |¿ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=7
STACK = [|[ , |] , |à , |ø , |¿ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=7
STACK = [|[ , |] , |à , |¿ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=8
STACK = [|[ , |] , |à , |¿ , |¡ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=9
STACK = [|[ , |] , |à , |¿ , |¡ , |¬ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=9
STACK = [|[ , |] , |à , |¿ , |¡ , |¬ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=9
STACK = [|[ , |] , |à , |¿ , |¬ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=9
STACK = [|[ , |] , |à , |¿ , |¬ ]
• Step 2: Start with an empty stack.
Maintain the stack s.t. every turn is
a right turn

i=9
STACK = [|[ , |] , |à , |¬ ]

(Step 2 gives us the “upper hull” of

the points)
• Step 3: Similar to step 2, but
process points in reverse order

i=9
STACK = [|[ , |] , |à , |¬ ]
• Step 3: Similar to step 2, but
process points in reverse order

i=8
STACK = [|[ , |] , |à , |¬ , |¡ ]
• Step 3: Similar to step 2, but
process points in reverse order

i=7
STACK = [|[ , |] , |à , |¬ , |¡ , |¿ ]
• Step 3: Similar to step 2, but
process points in reverse order

i=6
STACK = [|[ , |] , |à , |¬ , |¡ , |¿ , |ø ]
• Step 3: Similar to step 2, but
process points in reverse order

i=6
STACK = [|[ , |] , |à , |¬ , |¡ , |¿ , |ø ]
• Step 3: Similar to step 2, but
process points in reverse order

i=6
STACK = [|[ , |] , |à , |¬ , |¡ , |ø ]
• Step 3: Similar to step 2, but
process points in reverse order

i=5
STACK = [|[ , |] , |à , |¬ , |¡ , |ø , |æ ]
• Step 3: Similar to step 2, but
process points in reverse order

i=5
STACK = [|[ , |] , |à , |¬ , |¡ , |ø , |æ ]
• Step 3: Similar to step 2, but
process points in reverse order

i=5
STACK = [|[ , |] , |à , |¬ , |¡ , |æ ]
• Step 3: Similar to step 2, but
process points in reverse order

i=4
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |à ]

Don’t worry about |à ; it will be fixed

automatically :)
• Step 3: Similar to step 2, but
process points in reverse order

i=3
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |à , |Ü ]
• Step 3: Similar to step 2, but
process points in reverse order

i=3
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |à , |Ü ]
• Step 3: Similar to step 2, but
process points in reverse order

i=3
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |Ü ]
• Step 3: Similar to step 2, but
process points in reverse order

i=2
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |Ü , |] ]
• Step 3: Similar to step 2, but
process points in reverse order

i=2
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |Ü , |] ]
• Step 3: Similar to step 2, but
process points in reverse order

i=2
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |] ]
• Step 3: Similar to step 2, but
process points in reverse order

i=1
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |] , |[ ]
• Step 3: Similar to step 2, but
process points in reverse order

i=1
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |] , |[ ]
• Step 3: Similar to step 2, but
process points in reverse order

i=1
STACK = [|[ , |] , |à , |¬ , |¡ , |æ , |[ ]
• Done :)
• I haven’t told you how to check if a
turn is a right turn

• Talk about it in 2.2 – Vectors

 Computational Geometry

Table of Contents
1. Points, Lines, Segments
2. Vectors
3. Polygons
4. Convex Hull
5. Precision Handling
6. More
 Computational Geometry

Precision Handling
If the problem allows, try to use int or long long to avoid precision errors!

Otherwise, handle the precision errors carefully, usually by using | (EPS):

● we usually set const double EPS = 1e-9 (or 1e-6)
● a == b à fabs(a – b) < EPS
● a < b à a + EPS < b
● a <= b à a < b + EPS

operator==(const Vector& T) const {

return fabs(x – T.x) < EPS && fabs(y - T.y) < EPS;
}
 Computational Geometry

Table of Contents
1. Points, Lines, Segments
2. Vectors
3. Polygons
4. Convex Hull
5. Precision Handling
6. More
 Computational Geometry

More
There are still many other interesting tricks to learn!
● distance to line
● distance to segment
● intersection
● …]
However, probably you won’t see these stuffs in secondary school level OI
competitions…
● To practice, one simple way is Codeforces (tag = geometry)
Still, it’s important to learn how to code nicely :)
 Computational Geometry

Questions?