Summary - Geometry
- Algorithms course
- Expert
- Lesson 24/41
- 4 min
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.
Practice 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)).
Starter code
def cross_product(ax, ay, bx, by, cx, cy):
# Cross productSample 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))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Which method builds the convex hull?
- Monotone chain Correct answer
- Depth-first search
- Linear scan
- Dynamic programming
Explanation: The monotone chain (Andrew) method is used.
2 cross product value
# A=(0,0), B=(2,0), C=(0,3)
# cross_product(A, B, C) = ____# A=(0,0), B=(2,0), C=(0,3)
# cross_product(A, B, C) = 6Explanation: (2)*(3) - (0)*(0) = 6, left turn.
3 Algorithm-tool
| Term | Meaning |
|---|---|
convex hull |
Monotone chain |
intersection |
Orientation test |
closest pair |
Divide and conquer |
point in polygon |
Ray casting |