Summary - Geometry

Print the orientation of three points in a mini task.

Summary - Geometry

In this group we covered the core tools of computational geometry: cross product, convex hull, line intersection, closest pair and point in polygon.

The cross product underlies all these algorithms; a single computation gives orientation and signed area. The other algorithms build on this foundation.

We will now revisit the cross product with a small task.

Exercise cross_product mini task

Write cross_product(ax, ay, bx, by, cx, cy). Return the cross product of three points. Print 1 with print(cross_product(0, 0, 1, 0, 0, 1)).

Show example solution

def cross_product(ax, ay, bx, by, cx, cy):
    # Cross product
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
print(cross_product(0, 0, 1, 0, 0, 1))

Test yourself

Which method builds the convex hull?
- Monotone chain
- Depth-first search
- Linear scan
- Dynamic programming
Show answer

Monotone chain — The monotone chain (Andrew) method is used.

cross product value

# A=(0,0), B=(2,0), C=(0,3)
# cross_product(A, B, C) = ____

Show answer

# A=(0,0), B=(2,0), C=(0,3)
# cross_product(A, B, C) = 6

Algorithm-tool

convex hull

Monotone chain
intersection

Orientation test
closest pair

Divide and conquer
point in polygon

Ray casting

Next lesson: Flow network

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies