{ "cells": [ { "cell_type": "markdown", "id": "geometry-000", "metadata": {}, "source": [ "# Seminar 6: Classes and OOP\n", "\n", "We will work with **2D objects**: points, vectors, lines, segments, rays, and polygons.\n", "\n", "We want to construct these objects, move them along vectors, find intersections, and draw the result.\n", "We will introduce classes, constructors, dataclasses, magic methods, and inheritance as we need them.\n", "\n", "All calculations use Cartesian coordinates: x increases to the right, y increases upwards.\n" ] }, { "cell_type": "markdown", "id": "geometry-001", "metadata": {}, "source": [ "## Points and classes\n", "\n", "A point has two coordinates. We could store them in a tuple or a dictionary,\n", "but we also want operations such as finding the distance between two points.\n", "\n", "A **class** describes the data and operations of a kind of object.\n", "An **instance** is a particular object created from that class.\n" ] }, { "cell_type": "code", "id": "geometry-002", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:48:56.978820Z", "start_time": "2026-10-21T21:48:56.975509Z" } }, "source": [ "class Point:\n", " def __init__(self, x, y):\n", " self.x = x\n", " self.y = y\n", "\n", "\n", "p = Point(3, 4)\n", "q = Point(0, 0)\n", "print(p.x, p.y)\n", "print(p is q)\n", "print(p)\n" ], "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3 4\n", "False\n", "<__main__.Point object at 0x70ba08777b80>\n" ] } ], "execution_count": 2 }, { "cell_type": "markdown", "id": "geometry-003", "metadata": {}, "source": [ "`Point(3, 4)` creates an instance and calls `__init__` to initialize it.\n", "`self` refers to that instance. Assigning `self.x` and `self.y` stores its coordinates.\n", "\n", "`__init__` is often called the constructor, although object creation itself is handled by `__new__`.\n", "An initializer must return `None`.\n", "\n", "A method is a function accessed through an object. For our class, `p.distance_to(q)` passes `p`\n", "as the first argument, just like `Point.distance_to(p, q)`.\n" ] }, { "cell_type": "markdown", "id": "geometry-004", "metadata": {}, "source": [ "## Exercise 1: Distance between points\n", "\n", "Extend Point:\n", "\n", "- `distance_to(other)` returns the Euclidean distance to another point.\n", "- `__str__()` returns a readable pair of coordinates: `\"(3, 4)\"`.\n", "- `__repr__()` returns `\"Point(x=3, y=4)\"` for debugging. Use `!r` to represent each coordinate.\n", "\n", "For points (0, 0) and (3, 4), the distance is 5.\n", "\n", "What will `print(p)` show? What about `[p, q]`?\n" ] }, { "cell_type": "code", "id": "geometry-005", "metadata": { "tags": [ "exercise" ], "ExecuteTime": { "end_time": "2026-10-21T21:49:01.331711Z", "start_time": "2026-10-21T21:49:01.328797Z" } }, "source": [ "from math import hypot, isclose\n", "\n", "\n", "class Point:\n", " def __init__(self, x, y):\n", " self.x = x\n", " self.y = y\n", "\n", " def distance_to(self, other):\n", " pass\n", "\n", " def __str__(self):\n", " pass\n", "\n", " def __repr__(self):\n", " pass\n" ], "outputs": [], "execution_count": 3 }, { "cell_type": "code", "id": "geometry-006", "metadata": { "tags": [ "checks" ], "ExecuteTime": { "end_time": "2026-10-21T21:49:04.556135Z", "start_time": "2026-10-21T21:49:04.553279Z" } }, "source": [ "def check_points():\n", " p = Point(3, 4)\n", " q = Point(0, 0)\n", " assert isclose(p.distance_to(q), 5)\n", " assert isclose(q.distance_to(p), 5)\n", " assert p.distance_to(p) == 0\n", " assert str(p) == \"(3, 4)\"\n", " assert repr(p) == \"Point(x=3, y=4)\"\n", "\n", "\n", "# check_points()\n" ], "outputs": [], "execution_count": 4 }, { "cell_type": "markdown", "id": "geometry-007", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-008", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:49:06.349827Z", "start_time": "2026-10-21T21:49:06.345977Z" } }, "source": [ "class Point:\n", " def __init__(self, x, y):\n", " self.x = x\n", " self.y = y\n", "\n", " def distance_to(self, other):\n", " return hypot(self.x - other.x, self.y - other.y)\n", "\n", " def __str__(self):\n", " return f\"({self.x}, {self.y})\"\n", "\n", " def __repr__(self):\n", " return f\"Point(x={self.x!r}, y={self.y!r})\"\n", "\n", "\n", "check_points()\n", "print(Point(3, 4))\n", "print([Point(3, 4), Point(0, 0)])\n" ], "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(3, 4)\n", "[Point(x=3, y=4), Point(x=0, y=0)]\n" ] } ], "execution_count": 5 }, { "cell_type": "markdown", "id": "geometry-009", "metadata": {}, "source": [ "### Instance and class attributes\n", "\n", "What will this print? Why does changing one drawing affect the other?\n" ] }, { "cell_type": "code", "id": "geometry-010", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:49:37.072316Z", "start_time": "2026-10-21T21:49:37.069169Z" } }, "source": [ "class Drawing:\n", " points = []\n", "\n", "\n", "first = Drawing()\n", "second = Drawing()\n", "first.points.append(Point(1, 2))\n", "print(first.points)\n", "print(second.points)\n", "print(first.points is second.points)\n" ], "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[Point(x=1, y=2)]\n", "[Point(x=1, y=2)]\n", "True\n" ] } ], "execution_count": 6 }, { "cell_type": "markdown", "id": "geometry-011", "metadata": {}, "source": [ "`points` is a **class attribute**: both drawings find the same list on the class.\n", "For separate collections, create `self.points = []` inside `__init__`.\n", "Class attributes are useful for shared constants; coordinates and collections belonging to one object should be instance attributes.\n", "\n", "Rewrite Drawing so each instance has its own list, then check the example again.\n" ] }, { "cell_type": "code", "id": "geometry-012", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:49:42.318311Z", "start_time": "2026-10-21T21:49:42.315379Z" } }, "source": [ "class Drawing:\n", " def __init__(self):\n", " self.points = []\n", "\n", "\n", "first = Drawing()\n", "second = Drawing()\n", "first.points.append(Point(1, 2))\n", "assert second.points == []\n" ], "outputs": [], "execution_count": 7 }, { "cell_type": "markdown", "id": "geometry-013", "metadata": {}, "source": [ "## Dataclasses\n", "\n", "Point contains repetitive code: assign fields, represent them, and compare their values.\n", "`@dataclass` can generate `__init__`, `__repr__`, and `__eq__` from annotated fields.\n", "It does not generate our custom `__str__` or `distance_to`.\n", "\n", "With `frozen=True`, normal field assignment is rejected. We will make our geometry objects immutable:\n", "translating a point produces a new point, leaving the original in place.\n", "\n", "Annotations describe intended types; dataclasses do not enforce them at runtime.\n", "Generated equality compares field values and requires the same concrete class.\n" ] }, { "cell_type": "code", "id": "geometry-014", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:49:50.639141Z", "start_time": "2026-10-21T21:49:50.634962Z" } }, "source": [ "from dataclasses import dataclass, field, FrozenInstanceError\n", "\n", "\n", "@dataclass(frozen=True)\n", "class Point:\n", " x: float\n", " y: float\n", "\n", " def distance_to(self, other):\n", " return hypot(self.x - other.x, self.y - other.y)\n", "\n", " def __str__(self):\n", " return f\"({self.x}, {self.y})\"\n", "\n", "\n", "check_points()\n", "a = Point(3, 4)\n", "b = Point(3, 4)\n", "print(a == b)\n", "print(a is b)\n", "\n", "try:\n", " a.x = 10\n", "except FrozenInstanceError as error:\n", " print(error)\n" ], "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True\n", "False\n", "cannot assign to field 'x'\n" ] } ], "execution_count": 8 }, { "cell_type": "markdown", "id": "geometry-015", "metadata": {}, "source": [ "A frozen dataclass prevents field reassignment, but does not freeze mutable objects stored inside its fields.\n", "We will use immutable points and tuples of vertices for geometric objects.\n", "\n", "For a mutable collection such as Drawing, `field(default_factory=list)` creates a separate list per instance.\n", "A mutable list written directly as a dataclass field default is rejected.\n" ] }, { "cell_type": "code", "id": "geometry-016", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:49:54.601119Z", "start_time": "2026-10-21T21:49:54.598018Z" } }, "source": [ "@dataclass\n", "class Drawing:\n", " points: list[Point] = field(default_factory=list)\n", "\n", "\n", "first = Drawing()\n", "second = Drawing()\n", "first.points.append(Point(1, 2))\n", "assert second.points == []\n" ], "outputs": [], "execution_count": 9 }, { "cell_type": "markdown", "id": "geometry-017", "metadata": {}, "source": [ "## Vectors and magic methods\n", "\n", "A point is a location; a vector is a displacement. Subtracting two points gives a vector.\n", "Adding a vector to a point moves it.\n", "\n", "Python calls **special methods**, also called magic or dunder methods, for operators:\n", "\n", "| Expression | Method | Result in our library |\n", "|---|---|---|\n", "| `p + v` | `Point.__add__` | A translated Point |\n", "| `p2 - p1` | `Point.__sub__` | A Vector |\n", "| `v1 + v2` | `Vector.__add__` | A Vector |\n", "| `v1 - v2` | `Vector.__sub__` | A Vector |\n", "| `-v` | `Vector.__neg__` | The opposite Vector |\n", "| `v * k` | `Vector.__mul__` | A scaled Vector |\n", "| `k * v` | `Vector.__rmul__` | A scaled Vector |\n", "| `abs(v)` | `Vector.__abs__` | Vector length |\n", "\n", "For an unsupported operand, return `NotImplemented`. Python can try the other operand's implementation,\n", "and raises `TypeError` if neither supports the operation. This differs from raising `NotImplementedError`.\n" ] }, { "cell_type": "markdown", "id": "geometry-018", "metadata": {}, "source": [ "## Exercise 2: Vector arithmetic and translating points\n", "\n", "Create a frozen Vector dataclass with `dx` and `dy` fields. Implement the vector operators above.\n", "Allow integer and floating-point scalars for multiplication.\n", "\n", "Add two methods:\n", "\n", "- `dot(other)` returns `dx * other.dx + dy * other.dy`.\n", "- `cross(other)` returns the 2D signed cross product `dx * other.dy - dy * other.dx`.\n", "\n", "Extend the Point dataclass with addition of a Vector and subtraction of another Point.\n", "Do not define addition of two points: it has no meaning in this library.\n", "Keep `distance_to` and `__str__`.\n", "\n", "For `Vector(3, 4)`, length is 5. For `Point(1, 2) + Vector(3, 4)`, the result is `Point(4, 6)`.\n", "\n", "What does the sign of `Vector(1, 0).cross(v)` tell us about v?\n" ] }, { "cell_type": "code", "id": "geometry-019", "metadata": { "tags": [ "exercise" ], "ExecuteTime": { "end_time": "2026-10-21T21:50:09.688239Z", "start_time": "2026-10-21T21:50:09.684550Z" } }, "source": [ "@dataclass(frozen=True)\n", "class Vector:\n", " dx: float\n", " dy: float\n", "\n", " def __add__(self, other):\n", " pass\n", "\n", " def __sub__(self, other):\n", " pass\n", "\n", " def __neg__(self):\n", " pass\n", "\n", " def __mul__(self, scalar):\n", " pass\n", "\n", " def __rmul__(self, scalar):\n", " pass\n", "\n", " def __abs__(self):\n", " pass\n", "\n", " def dot(self, other):\n", " pass\n", "\n", " def cross(self, other):\n", " pass\n", "\n", "\n", "# Redefine Point here, adding __add__ and __sub__ to the dataclass above.\n" ], "outputs": [], "execution_count": 10 }, { "cell_type": "code", "id": "geometry-020", "metadata": { "tags": [ "checks" ], "ExecuteTime": { "end_time": "2026-10-21T21:50:14.208295Z", "start_time": "2026-10-21T21:50:14.204081Z" } }, "source": [ "def expect_error(error_type, operation):\n", " try:\n", " operation()\n", " except error_type:\n", " return\n", " raise AssertionError(f\"Expected {error_type}\")\n", "\n", "\n", "def check_vectors():\n", " v = Vector(3, 4)\n", " assert abs(v) == 5\n", " assert v + Vector(1, -1) == Vector(4, 3)\n", " assert v - Vector(1, -1) == Vector(2, 5)\n", " assert -v == Vector(-3, -4)\n", " assert v * 2 == 2 * v == Vector(6, 8)\n", " assert v * 0.5 == Vector(1.5, 2)\n", " assert v.dot(Vector(4, -3)) == 0\n", " assert Vector(1, 0).cross(Vector(0, 1)) == 1\n", " p = Point(1, 2)\n", " assert p + v == Point(4, 6)\n", " assert Point(4, 6) - p == v\n", " assert p == Point(1, 2)\n", " expect_error(TypeError, lambda: p + Point(3, 4))\n", " expect_error(TypeError, lambda: v * \"two\")\n", " expect_error(FrozenInstanceError, lambda: setattr(v, \"dx\", 99))\n", " check_points()\n", "\n", "\n", "# check_vectors()\n" ], "outputs": [], "execution_count": 11 }, { "cell_type": "markdown", "id": "geometry-021", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-022", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:50:22.959056Z", "start_time": "2026-10-21T21:50:22.952698Z" } }, "source": [ "@dataclass(frozen=True)\n", "class Vector:\n", " dx: float\n", " dy: float\n", "\n", " def __add__(self, other):\n", " if not isinstance(other, Vector):\n", " return NotImplemented\n", " return Vector(self.dx + other.dx, self.dy + other.dy)\n", "\n", " def __sub__(self, other):\n", " if not isinstance(other, Vector):\n", " return NotImplemented\n", " return Vector(self.dx - other.dx, self.dy - other.dy)\n", "\n", " def __neg__(self):\n", " return Vector(-self.dx, -self.dy)\n", "\n", " def __mul__(self, scalar):\n", " if not isinstance(scalar, (int, float)):\n", " return NotImplemented\n", " return Vector(self.dx * scalar, self.dy * scalar)\n", "\n", " def __rmul__(self, scalar):\n", " return self * scalar\n", "\n", " def __abs__(self):\n", " return hypot(self.dx, self.dy)\n", "\n", " def dot(self, other):\n", " return self.dx * other.dx + self.dy * other.dy\n", "\n", " def cross(self, other):\n", " return self.dx * other.dy - self.dy * other.dx\n", "\n", "\n", "@dataclass(frozen=True)\n", "class Point:\n", " x: float\n", " y: float\n", "\n", " def distance_to(self, other):\n", " return hypot(self.x - other.x, self.y - other.y)\n", "\n", " def __str__(self):\n", " return f\"({self.x}, {self.y})\"\n", "\n", " def __add__(self, other):\n", " if not isinstance(other, Vector):\n", " return NotImplemented\n", " return Point(self.x + other.dx, self.y + other.dy)\n", "\n", " def __sub__(self, other):\n", " if not isinstance(other, Point):\n", " return NotImplemented\n", " return Vector(self.x - other.x, self.y - other.y)\n", "\n", "\n", "check_vectors()\n" ], "outputs": [], "execution_count": 12 }, { "cell_type": "markdown", "id": "geometry-023", "metadata": {}, "source": [ "## Lines and alternative constructors\n", "\n", "An infinite line has the equation **Ax + By + C = 0**, where A and B cannot both be zero.\n", "We want two ways to construct it:\n", "\n", "```python\n", "Line(1, -1, 0) # x - y = 0\n", "Line.from_points(Point(0, 0), Point(2, 2))\n", "```\n", "\n", "Python does not choose between several `__init__` definitions by their argument types.\n", "We will use one initializer for coefficients and an alternative constructor for two points.\n", "\n", "A `@classmethod` receives the class as `cls` instead of an instance as `self`.\n", "Returning `cls(...)` constructs an instance of whichever class received the call.\n", "A `@staticmethod` receives neither automatically; it is useful for a related utility that needs no object or class state.\n" ] }, { "cell_type": "markdown", "id": "geometry-024", "metadata": {}, "source": [ "## Exercise 3: Construct, move, and intersect lines\n", "\n", "Create a frozen Line dataclass with fields `A`, `B`, `C`. Implement:\n", "\n", "1. `__post_init__`: reject A = B = 0 with `ValueError`. Dataclasses call this after generated initialization.\n", "2. `from_points(p, q)`: reject identical points. Use A = p.y - q.y, B = q.x - p.x,\n", " C = p.x*q.y - q.x*p.y. Return `cls(A, B, C)`.\n", "3. `contains(point)`: check whether the point satisfies the equation within `EPS`.\n", "4. `line + vector`: return a new Line. Derive its coefficients by replacing x with x - dx and y with y - dy.\n", "5. `intersection(other)`: return the unique intersection Point, or `None` for distinct parallel lines.\n", " Coincident lines have no unique intersection: raise `ValueError`.\n", "6. `line & other`: delegate to `intersection` through `__and__`.\n", "\n", "For intersections, let D = A1*B2 - A2*B1. If D is nonzero:\n", "\n", "- x = (B1*C2 - B2*C1) / D\n", "- y = (C1*A2 - C2*A1) / D\n", "\n", "Equivalent equations such as `Line(1, -1, 0)` and `Line(2, -2, 0)` describe the same line.\n", "Normalize A, B, C by `hypot(A, B)` in `contains` and `intersection` before numerical comparisons.\n", "For parallel lines, pick a point on one line and check whether the other contains it.\n", "\n", "Use `EPS = 1e-9` for these exercises. Assume finite coordinates of moderate size;\n", "robust geometry at extreme scales needs more careful numerical methods.\n", "Dataclass equality still compares coefficients, not geometric equivalence.\n" ] }, { "cell_type": "code", "id": "geometry-025", "metadata": { "tags": [ "exercise" ], "ExecuteTime": { "end_time": "2026-10-21T21:51:04.670799Z", "start_time": "2026-10-21T21:51:04.666952Z" } }, "source": [ "EPS = 1e-9\n", "\n", "\n", "@dataclass(frozen=True)\n", "class Line:\n", " A: float\n", " B: float\n", " C: float\n", "\n", " def __post_init__(self):\n", " pass\n", "\n", " @classmethod\n", " def from_points(cls, p, q):\n", " pass\n", "\n", " def contains(self, point):\n", " pass\n", "\n", " def __add__(self, vector):\n", " pass\n", "\n", " def intersection(self, other):\n", " pass\n", "\n", " def __and__(self, other):\n", " pass\n" ], "outputs": [], "execution_count": 13 }, { "cell_type": "code", "id": "geometry-026", "metadata": { "tags": [ "checks" ], "ExecuteTime": { "end_time": "2026-10-21T21:51:06.421898Z", "start_time": "2026-10-21T21:51:06.417288Z" } }, "source": [ "def check_lines():\n", " diagonal = Line.from_points(Point(0, 0), Point(2, 2))\n", " assert diagonal.contains(Point(3, 3))\n", " assert not diagonal.contains(Point(3, 4))\n", " vertical = Line(1, 0, -2)\n", " point = diagonal & vertical\n", " assert point.distance_to(Point(2, 2)) < EPS\n", " assert (vertical & Line(0, 1, -3)).distance_to(Point(2, 3)) < EPS\n", " assert vertical.intersection(Line(2, 0, -6)) is None\n", " expect_error(ValueError, lambda: vertical & Line(2, 0, -4))\n", " expect_error(ValueError, lambda: Line(0, 0, 1))\n", " expect_error(ValueError, lambda: Line.from_points(Point(1, 1), Point(1, 1)))\n", " moved = vertical + Vector(3, 7)\n", " assert moved.contains(Point(5, 100))\n", " assert vertical.contains(Point(2, 100)) # Original unchanged.\n", " assert Line(1e-12, 0, -2e-12).contains(Point(2, 9))\n", " expect_error(TypeError, lambda: vertical + Point(1, 2))\n", "\n", "\n", "# check_lines()\n" ], "outputs": [], "execution_count": 14 }, { "cell_type": "markdown", "id": "geometry-027", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-028", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:51:22.200123Z", "start_time": "2026-10-21T21:51:22.193327Z" } }, "source": [ "@dataclass(frozen=True)\n", "class Line:\n", " A: float\n", " B: float\n", " C: float\n", "\n", " def __post_init__(self):\n", " if self.A == 0 and self.B == 0:\n", " raise ValueError(\"A and B cannot both be zero\")\n", "\n", " @classmethod\n", " def from_points(cls, p, q):\n", " if p == q:\n", " raise ValueError(\"two distinct points are required\")\n", " return cls(p.y - q.y, q.x - p.x, p.x * q.y - q.x * p.y)\n", "\n", " def contains(self, point):\n", " scale = hypot(self.A, self.B)\n", " return abs((self.A / scale) * point.x + (self.B / scale) * point.y + self.C / scale) <= EPS\n", "\n", " def __add__(self, vector):\n", " if not isinstance(vector, Vector):\n", " return NotImplemented\n", " return Line(self.A, self.B, self.C - self.A * vector.dx - self.B * vector.dy)\n", "\n", " def intersection(self, other):\n", " s1, s2 = hypot(self.A, self.B), hypot(other.A, other.B)\n", " a1, b1, c1 = self.A / s1, self.B / s1, self.C / s1\n", " a2, b2, c2 = other.A / s2, other.B / s2, other.C / s2\n", " determinant = a1 * b2 - a2 * b1\n", " if abs(determinant) <= EPS:\n", " point = Point(-c1 / a1, 0) if abs(a1) >= abs(b1) else Point(0, -c1 / b1)\n", " if other.contains(point):\n", " raise ValueError(\"coincident lines have no unique intersection\")\n", " return None\n", " return Point((b1 * c2 - b2 * c1) / determinant,\n", " (c1 * a2 - c2 * a1) / determinant)\n", "\n", " def __and__(self, other):\n", " if not isinstance(other, Line):\n", " return NotImplemented\n", " return self.intersection(other)\n", "\n", "\n", "check_lines()\n", "print(Line(1, -1, 0) & Line(1, 0, -2))\n" ], "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(2.0, 2.0)\n" ] } ], "execution_count": 15 }, { "cell_type": "markdown", "id": "geometry-029", "metadata": {}, "source": [ "## Exercise 4: Segments and rays\n", "\n", "A segment has two endpoints. A ray has an origin and continues in one direction indefinitely.\n", "Both have a supporting line, but their sets of points are different.\n", "We will use **composition**: each can construct a Line rather than inherit from it.\n", "\n", "Implement frozen dataclasses:\n", "\n", "- `Segment(start, end)`: reject identical endpoints; provide `length()`, `contains(point)`, and translation with `+ Vector`.\n", "- `Ray(origin, through)`: the second point fixes its direction; reject identical points;\n", " provide `contains(point)` and translation with `+ Vector`.\n", "\n", "For containment, first check the supporting line. Then use dot products:\n", "\n", "- Segment: `(point - start).dot(point - end) <= EPS`.\n", "- Ray: `(point - origin).dot(through - origin) >= -EPS`.\n", "\n", "Include endpoints in both cases. Translations return new objects of the same kind.\n", "\n", "Why is a ray's second point not an endpoint?\n" ] }, { "cell_type": "code", "id": "geometry-030", "metadata": { "tags": [ "exercise" ] }, "source": [ "# Implement Segment and Ray using @dataclass(frozen=True).\n", "# Line.from_points(...) provides their supporting lines.\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "code", "id": "geometry-031", "metadata": { "tags": [ "checks" ], "ExecuteTime": { "end_time": "2026-10-21T21:51:37.960421Z", "start_time": "2026-10-21T21:51:37.956279Z" } }, "source": [ "def check_segments_and_rays():\n", " segment = Segment(Point(0, 0), Point(4, 0))\n", " ray = Ray(Point(0, 0), Point(4, 0))\n", " assert segment.length() == 4\n", " for point in [Point(0, 0), Point(2, 0), Point(4, 0)]:\n", " assert segment.contains(point) and ray.contains(point)\n", " assert not segment.contains(Point(5, 0)) and ray.contains(Point(5, 0))\n", " assert not ray.contains(Point(-1, 0))\n", " assert not segment.contains(Point(2, 1)) and not ray.contains(Point(2, 1))\n", " shift = Vector(1, 2)\n", " assert (segment + shift).contains(Point(3, 2))\n", " assert (ray + shift).contains(Point(10, 2))\n", " expect_error(ValueError, lambda: Segment(Point(0, 0), Point(0, 0)))\n", " expect_error(ValueError, lambda: Ray(Point(0, 0), Point(0, 0)))\n", "\n", "\n", "# check_segments_and_rays()\n" ], "outputs": [], "execution_count": 16 }, { "cell_type": "markdown", "id": "geometry-032", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-033", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:51:59.831732Z", "start_time": "2026-10-21T21:51:59.826318Z" } }, "source": [ "@dataclass(frozen=True)\n", "class Segment:\n", " start: Point\n", " end: Point\n", "\n", " def __post_init__(self):\n", " if self.start == self.end:\n", " raise ValueError(\"segment endpoints must differ\")\n", "\n", " def length(self):\n", " return self.start.distance_to(self.end)\n", "\n", " def contains(self, point):\n", " return (Line.from_points(self.start, self.end).contains(point)\n", " and (point - self.start).dot(point - self.end) <= EPS)\n", "\n", " def __add__(self, vector):\n", " if not isinstance(vector, Vector):\n", " return NotImplemented\n", " return Segment(self.start + vector, self.end + vector)\n", "\n", "\n", "@dataclass(frozen=True)\n", "class Ray:\n", " origin: Point\n", " through: Point\n", "\n", " def __post_init__(self):\n", " if self.origin == self.through:\n", " raise ValueError(\"a ray needs a direction\")\n", "\n", " def contains(self, point):\n", " return (Line.from_points(self.origin, self.through).contains(point)\n", " and (point - self.origin).dot(self.through - self.origin) >= -EPS)\n", "\n", " def __add__(self, vector):\n", " if not isinstance(vector, Vector):\n", " return NotImplemented\n", " return Ray(self.origin + vector, self.through + vector)\n", "\n", "\n", "check_segments_and_rays()\n" ], "outputs": [], "execution_count": 17 }, { "cell_type": "markdown", "id": "geometry-034", "metadata": {}, "source": [ "## Polygons\n", "\n", "A polygon is described by its vertices in boundary order. The last vertex connects back to the first;\n", "we do not repeat the first vertex in the input.\n", "\n", "For this seminar, polygons must be **strictly convex**: every interior angle is less than 180 degrees.\n", "Vertices must follow the boundary without crossing. This keeps containment and intersection manageable.\n", "\n", "The setup below stores vertices as a tuple and validates them. Clockwise input is reversed to counterclockwise,\n", "keeping the first vertex in place. For each directed edge, all other vertices must lie strictly to its left.\n", "That also rejects repeated vertices, collinear corners, and self-intersections.\n", "\n", "`object.__setattr__` is used only during initialization to store the normalized tuple in a frozen dataclass.\n" ] }, { "cell_type": "code", "id": "geometry-035", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:52:19.042418Z", "start_time": "2026-10-21T21:52:19.038835Z" } }, "source": [ "def signed_double_area(vertices):\n", " return sum(p.x * q.y - q.x * p.y\n", " for p, q in zip(vertices, vertices[1:] + vertices[:1]))\n", "\n", "\n", "def validated_vertices(vertices):\n", " points = tuple(vertices)\n", " if len(points) < 3:\n", " raise ValueError(\"a polygon needs at least three vertices\")\n", " if signed_double_area(points) < 0:\n", " points = (points[0],) + tuple(reversed(points[1:]))\n", " for i, p in enumerate(points):\n", " q = points[(i + 1) % len(points)]\n", " for j, r in enumerate(points):\n", " if j not in (i, (i + 1) % len(points)):\n", " if (q - p).cross(r - p) <= EPS:\n", " raise ValueError(\"vertices must form a strictly convex polygon in boundary order\")\n", " return points\n" ], "outputs": [], "execution_count": 18 }, { "cell_type": "markdown", "id": "geometry-036", "metadata": {}, "source": [ "## Exercise 5: Polygon operations\n", "\n", "Create a frozen Polygon dataclass with one field, `vertices: tuple[Point, ...]`.\n", "Use `validated_vertices` in `__post_init__` to normalize and validate the input.\n", "\n", "Implement:\n", "\n", "- `len(polygon)` through `__len__`: the number of vertices.\n", "- Iteration through `__iter__`: yield vertices in boundary order.\n", "- `area()`: half the absolute value of `signed_double_area(vertices)` (the shoelace formula).\n", "- `perimeter()`: sum distances along all edges, including the closing edge.\n", "- `contains(point)`: for every counterclockwise edge p → q, `(q - p).cross(point - p) >= -EPS`.\n", " Boundary points count as inside.\n", "- `translated(vector)`: return a Polygon with each vertex moved along the vector.\n", "- `polygon + vector`: delegate to `translated` through `__add__`.\n", "\n", "Does translation change area or perimeter? How can you check that the original polygon stayed in place?\n" ] }, { "cell_type": "code", "id": "geometry-037", "metadata": { "tags": [ "exercise" ], "ExecuteTime": { "end_time": "2026-10-21T21:52:32.840079Z", "start_time": "2026-10-21T21:52:32.835952Z" } }, "source": [ "@dataclass(frozen=True)\n", "class Polygon:\n", " vertices: tuple[Point, ...]\n", "\n", " def __post_init__(self):\n", " object.__setattr__(self, \"vertices\", validated_vertices(self.vertices))\n", "\n", " def __len__(self):\n", " pass\n", "\n", " def __iter__(self):\n", " pass\n", "\n", " def area(self):\n", " pass\n", "\n", " def perimeter(self):\n", " pass\n", "\n", " def contains(self, point):\n", " pass\n", "\n", " def translated(self, vector):\n", " pass\n", "\n", " def __add__(self, vector):\n", " pass\n", "\n", " # The clipping function is implemented in the advanced intersection exercise.\n", " def intersection(self, other):\n", " return polygon_intersection(self, other)\n", "\n", " def __and__(self, other):\n", " if not isinstance(other, Polygon):\n", " return NotImplemented\n", " return self.intersection(other)\n" ], "outputs": [], "execution_count": 19 }, { "cell_type": "code", "id": "geometry-038", "metadata": { "tags": [ "checks" ], "ExecuteTime": { "end_time": "2026-10-21T21:52:34.998675Z", "start_time": "2026-10-21T21:52:34.994373Z" } }, "source": [ "def check_polygons():\n", " polygon = Polygon((Point(0, 0), Point(4, 0), Point(4, 3), Point(0, 3)))\n", " assert len(polygon) == 4 and list(polygon) == list(polygon.vertices)\n", " assert polygon.area() == 12 and polygon.perimeter() == 14\n", " assert polygon.contains(Point(2, 1))\n", " assert polygon.contains(Point(4, 1))\n", " assert not polygon.contains(Point(5, 1))\n", " moved = polygon + Vector(10, -2)\n", " assert moved.contains(Point(12, -1))\n", " assert moved.area() == polygon.area()\n", " assert moved.perimeter() == polygon.perimeter()\n", " assert polygon.vertices[0] == Point(0, 0)\n", " assert Polygon(tuple(reversed(polygon.vertices))).area() == 12\n", " expect_error(ValueError, lambda: Polygon((Point(0, 0), Point(1, 0), Point(2, 0))))\n", " expect_error(ValueError, lambda: Polygon((Point(0, 0), Point(2, 2), Point(0, 2), Point(2, 0))))\n", " expect_error(FrozenInstanceError, lambda: setattr(polygon, \"vertices\", ()))\n", "\n", "\n", "# check_polygons()\n" ], "outputs": [], "execution_count": 20 }, { "cell_type": "markdown", "id": "geometry-039", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-040", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:52:35.590509Z", "start_time": "2026-10-21T21:52:35.584590Z" } }, "source": [ "@dataclass(frozen=True)\n", "class Polygon:\n", " vertices: tuple[Point, ...]\n", "\n", " def __post_init__(self):\n", " object.__setattr__(self, \"vertices\", validated_vertices(self.vertices))\n", "\n", " def __len__(self):\n", " return len(self.vertices)\n", "\n", " def __iter__(self):\n", " return iter(self.vertices)\n", "\n", " def area(self):\n", " return abs(signed_double_area(self.vertices)) / 2\n", "\n", " def perimeter(self):\n", " points = self.vertices\n", " return sum(p.distance_to(q) for p, q in zip(points, points[1:] + points[:1]))\n", "\n", " def contains(self, point):\n", " points = self.vertices\n", " return all((q - p).cross(point - p) >= -EPS\n", " for p, q in zip(points, points[1:] + points[:1]))\n", "\n", " def translated(self, vector):\n", " return Polygon(tuple(point + vector for point in self.vertices))\n", "\n", " def __add__(self, vector):\n", " if not isinstance(vector, Vector):\n", " return NotImplemented\n", " return self.translated(vector)\n", "\n", " # The clipping function is implemented in the advanced intersection exercise.\n", " def intersection(self, other):\n", " return polygon_intersection(self, other)\n", "\n", " def __and__(self, other):\n", " if not isinstance(other, Polygon):\n", " return NotImplemented\n", " return self.intersection(other)\n", "\n", "\n", "check_polygons()\n" ], "outputs": [], "execution_count": 21 }, { "cell_type": "markdown", "id": "geometry-041", "metadata": {}, "source": [ "## Inheritance and `super()`\n", "\n", "A triangle is a polygon. A rectangle is a polygon with right angles; a square is a rectangle with equal sides.\n", "We can express these relationships through inheritance:\n", "\n", "```text\n", "Polygon\n", "├── Triangle\n", "└── Rectangle\n", " └── Square\n", "```\n", "\n", "A subclass inherits methods from its base class and can **override** selected methods.\n", "`super()` continues to the next class in the method resolution order. With single inheritance, that is the parent.\n", "\n", "We will keep these objects immutable. A square has no independent width and height setters that could turn it into a nonsquare.\n", "Translations return new objects and preserve their concrete shape type.\n", "\n", "For custom constructors on frozen dataclass subclasses, use `@dataclass(frozen=True, init=False)`.\n", "It keeps generated representation and equality while letting us write our own `__init__`.\n" ] }, { "cell_type": "markdown", "id": "geometry-042", "metadata": {}, "source": [ "## Exercise 6: Triangle, Rectangle, Square\n", "\n", "Implement these subclasses:\n", "\n", "1. `Triangle(Polygon)` takes three points and passes their tuple to `super().__init__`.\n", "2. `Rectangle(Polygon)` takes `origin`, `width`, and `height`. Reject nonpositive dimensions.\n", " The origin is the bottom-left corner; rectangles are axis-aligned.\n", " Construct the four vertices and let Polygon validate them.\n", "3. `Square(Rectangle)` takes `origin` and `side`. Initialize it through `super()` with equal width and height.\n", "4. Override `translated(vector)` in each subclass so translating a Square returns a Square, and likewise for Rectangle and Triangle.\n", " Reuse the inherited `__add__`, containment, and perimeter methods.\n", "5. Override `Rectangle.area()` to use width * height. Square can inherit it.\n", "\n", "Use read-only `@property` methods to expose Rectangle's `origin`, `width`, and `height` from its vertices.\n", "A property is accessed as `rectangle.width`, without parentheses. No setters are needed.\n", "\n", "Why should Square call Rectangle's initializer instead of rebuilding the vertices itself?\n", "Which `translated` method does the inherited `Polygon.__add__` call for a Square?\n" ] }, { "cell_type": "code", "id": "geometry-043", "metadata": { "tags": [ "exercise" ], "ExecuteTime": { "end_time": "2026-10-21T21:52:44.824717Z", "start_time": "2026-10-21T21:52:44.820130Z" } }, "source": [ "@dataclass(frozen=True, init=False)\n", "class Triangle(Polygon):\n", " def __init__(self, a, b, c):\n", " pass\n", "\n", " def translated(self, vector):\n", " pass\n", "\n", "\n", "@dataclass(frozen=True, init=False)\n", "class Rectangle(Polygon):\n", " def __init__(self, origin, width, height):\n", " pass\n", "\n", " @property\n", " def origin(self):\n", " pass\n", "\n", " @property\n", " def width(self):\n", " pass\n", "\n", " @property\n", " def height(self):\n", " pass\n", "\n", " def area(self):\n", " pass\n", "\n", " def translated(self, vector):\n", " pass\n", "\n", "\n", "@dataclass(frozen=True, init=False)\n", "class Square(Rectangle):\n", " def __init__(self, origin, side):\n", " pass\n", "\n", " def translated(self, vector):\n", " pass\n" ], "outputs": [], "execution_count": 22 }, { "cell_type": "code", "id": "geometry-044", "metadata": { "tags": [ "checks" ], "ExecuteTime": { "end_time": "2026-10-21T21:52:44.970769Z", "start_time": "2026-10-21T21:52:44.966055Z" } }, "source": [ "def check_inheritance():\n", " triangle = Triangle(Point(0, 0), Point(4, 0), Point(0, 3))\n", " rectangle = Rectangle(Point(1, 2), 4, 3)\n", " square = Square(Point(1, 2), 3)\n", " assert triangle.area() == 6 and triangle.perimeter() == 12\n", " assert rectangle.area() == 12 and rectangle.perimeter() == 14\n", " assert square.area() == 9 and square.perimeter() == 12\n", " assert isinstance(square, Rectangle) and isinstance(square, Polygon)\n", " assert square.width == square.height == 3\n", " for shape in [triangle, rectangle, square]:\n", " moved = shape + Vector(10, -2)\n", " assert type(moved) is type(shape)\n", " assert isclose(moved.area(), shape.area())\n", " assert moved.vertices[0] == shape.vertices[0] + Vector(10, -2)\n", " expect_error(ValueError, lambda: Rectangle(Point(0, 0), 0, 3))\n", " expect_error(ValueError, lambda: Square(Point(0, 0), -1))\n", " expect_error(ValueError, lambda: Triangle(Point(0, 0), Point(1, 0), Point(2, 0)))\n", " expect_error((FrozenInstanceError, AttributeError), lambda: setattr(square, \"width\", 5))\n", "\n", "\n", "# check_inheritance()\n" ], "outputs": [], "execution_count": 23 }, { "cell_type": "markdown", "id": "geometry-045", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-046", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:52:46.978267Z", "start_time": "2026-10-21T21:52:46.971542Z" } }, "source": [ "@dataclass(frozen=True, init=False)\n", "class Triangle(Polygon):\n", " def __init__(self, a, b, c):\n", " super().__init__((a, b, c))\n", "\n", " def translated(self, vector):\n", " return Triangle(*(point + vector for point in self.vertices))\n", "\n", "\n", "@dataclass(frozen=True, init=False)\n", "class Rectangle(Polygon):\n", " def __init__(self, origin, width, height):\n", " if width <= 0 or height <= 0:\n", " raise ValueError(\"width and height must be positive\")\n", " super().__init__((origin, origin + Vector(width, 0),\n", " origin + Vector(width, height), origin + Vector(0, height)))\n", "\n", " @property\n", " def origin(self):\n", " return self.vertices[0]\n", "\n", " @property\n", " def width(self):\n", " return self.vertices[1].x - self.vertices[0].x\n", "\n", " @property\n", " def height(self):\n", " return self.vertices[3].y - self.vertices[0].y\n", "\n", " def area(self):\n", " return self.width * self.height\n", "\n", " def translated(self, vector):\n", " return Rectangle(self.origin + vector, self.width, self.height)\n", "\n", "\n", "@dataclass(frozen=True, init=False)\n", "class Square(Rectangle):\n", " def __init__(self, origin, side):\n", " super().__init__(origin, side, side)\n", "\n", " def translated(self, vector):\n", " return Square(self.origin + vector, self.width)\n", "\n", "\n", "check_inheritance()\n" ], "outputs": [], "execution_count": 24 }, { "cell_type": "markdown", "id": "geometry-047", "metadata": {}, "source": [ "## Polymorphism (Advanced)\n", "\n", "Polygon's `__add__` calls `self.translated(vector)`. A Square supplies its own implementation;\n", "a Triangle supplies another. The caller can use the same operation on different concrete objects.\n", "This is **polymorphism**.\n", "\n", "Shared inheritance is not required for every common operation. Point, Line, Segment, and Polygon\n", "all support `+ Vector` independently. A function can use that operation without checking their types:\n", "this is **duck typing**.\n" ] }, { "cell_type": "code", "id": "geometry-048", "metadata": {}, "source": [ "def translate_all(objects, vector):\n", " return [obj + vector for obj in objects]\n", "\n", "\n", "objects = [Point(0, 0), Line(1, 0, 0), Segment(Point(0, 0), Point(1, 0)),\n", " Triangle(Point(0, 0), Point(2, 0), Point(0, 2)), Square(Point(0, 0), 2)]\n", "for original, moved in zip(objects, translate_all(objects, Vector(3, 1))):\n", " print(type(original).__name__, \"->\", moved)\n" ], "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "id": "geometry-049", "metadata": {}, "source": [ "### Exercise\n", "\n", "Add `total_area(polygons)` and `containing(polygons, point)` without branching on Triangle, Rectangle, or Square.\n", "The first returns the sum of areas; the second returns shapes containing the point.\n", "\n", "If another Polygon subclass is added, should either function need to change?\n" ] }, { "cell_type": "code", "id": "geometry-050", "metadata": { "tags": [ "exercise", "advanced" ], "ExecuteTime": { "end_time": "2026-10-21T21:53:41.690229Z", "start_time": "2026-10-21T21:53:41.687708Z" } }, "source": [ "def total_area(polygons):\n", " pass\n", "\n", "\n", "def containing(polygons, point):\n", " pass\n" ], "outputs": [], "execution_count": 25 }, { "cell_type": "markdown", "id": "geometry-051", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-052", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:53:46.586924Z", "start_time": "2026-10-21T21:53:46.583422Z" } }, "source": [ "def total_area(polygons):\n", " return sum(shape.area() for shape in polygons)\n", "\n", "\n", "def containing(polygons, point):\n", " return [shape for shape in polygons if shape.contains(point)]\n", "\n", "\n", "shapes = [Square(Point(0, 0), 2), Rectangle(Point(10, 0), 3, 2)]\n", "assert total_area(shapes) == 10\n", "assert containing(shapes, Point(1, 1)) == [shapes[0]]\n" ], "outputs": [], "execution_count": 26 }, { "cell_type": "markdown", "id": "geometry-053", "metadata": {}, "source": [ "## Polygon intersection (Advanced)\n", "\n", "Two arbitrary polygons can overlap in disconnected regions. Even convex polygons can meet only at an edge or a point.\n", "Our operation has a narrower contract:\n", "\n", "- Inputs are the strictly convex polygons defined above.\n", "- Return a Polygon for overlap with area greater than EPS.\n", "- Return `None` for disjoint polygons or contact with no positive area.\n", "- The result is a general Polygon, even when both inputs are Rectangles or Squares.\n", "\n", "We will use **Sutherland–Hodgman clipping**. Each directed edge of the second polygon defines an inside half-plane\n", "on its left. Start with the first polygon's vertices and clip against these half-planes one by one.\n" ] }, { "cell_type": "markdown", "id": "geometry-054", "metadata": {}, "source": [ "## Exercise 7: Clip a polygon\n", "\n", "Implement `polygon_intersection(first, second)`.\n", "For each clipping edge a → b, walk the current vertices as edges start → end:\n", "\n", "| Start | End | Append to the new vertex list |\n", "|---|---|---|\n", "| Inside | Inside | end |\n", "| Inside | Outside | Crossing point |\n", "| Outside | Inside | Crossing point, then end |\n", "| Outside | Outside | Nothing |\n", "\n", "A point p is inside when `(b - a).cross(p - a) >= -EPS`.\n", "Find a crossing using the two supporting lines and the Line intersection method.\n", "If fewer than three vertices remain, there is no positive-area overlap.\n", "\n", "The helper below removes duplicate and collinear vertices introduced by clipping.\n", "Use it to construct the final result. It also handles edge and point contact.\n", "\n", "Polygon's `intersection` and `__and__` methods above delegate to this function.\n", "Once the function is implemented, both `polygon.intersection(other)` and `polygon & other` work.\n", "The method body looks up the function when called, so the function can be defined later in the notebook.\n" ] }, { "cell_type": "code", "id": "geometry-055", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:54:07.106196Z", "start_time": "2026-10-21T21:54:07.102384Z" } }, "source": [ "def polygon_or_none(vertices):\n", " points = []\n", " for point in vertices:\n", " if not points or point.distance_to(points[-1]) > EPS:\n", " points.append(point)\n", " if len(points) > 1 and points[0].distance_to(points[-1]) <= EPS:\n", " points.pop()\n", " changed = True\n", " while changed and len(points) >= 3:\n", " changed = False\n", " for i in range(len(points)):\n", " previous, current, following = points[i - 1], points[i], points[(i + 1) % len(points)]\n", " if abs((current - previous).cross(following - current)) <= EPS:\n", " points.pop(i)\n", " changed = True\n", " break\n", " if len(points) < 3 or abs(signed_double_area(tuple(points))) / 2 <= EPS:\n", " return None\n", " return Polygon(tuple(points))\n" ], "outputs": [], "execution_count": 27 }, { "cell_type": "code", "id": "geometry-056", "metadata": { "tags": [ "exercise", "advanced" ], "ExecuteTime": { "end_time": "2026-10-21T21:54:07.473997Z", "start_time": "2026-10-21T21:54:07.471805Z" } }, "source": [ "def polygon_intersection(first, second):\n", " # Clip list(first.vertices) against every edge of second.\n", " # Return polygon_or_none(...) for the final vertices.\n", " pass\n" ], "outputs": [], "execution_count": 28 }, { "cell_type": "code", "id": "geometry-057", "metadata": { "tags": [ "checks", "advanced" ], "ExecuteTime": { "end_time": "2026-10-21T21:54:10.298823Z", "start_time": "2026-10-21T21:54:10.294456Z" } }, "source": [ "def check_polygon_intersection():\n", " first = Square(Point(0, 0), 3)\n", " second = Square(Point(2, 1), 3)\n", " overlap = polygon_intersection(first, second)\n", " assert overlap is not None and isclose(overlap.area(), 2)\n", " assert overlap.contains(Point(2.5, 2))\n", " assert all(first.contains(p) and second.contains(p) for p in overlap)\n", " assert isclose(polygon_intersection(second, first).area(), overlap.area())\n", " assert isclose(polygon_intersection(first, first).area(), first.area())\n", " assert polygon_intersection(first, Square(Point(10, 10), 1)) is None\n", " assert polygon_intersection(first, Square(Point(3, 0), 1)) is None # Edge contact.\n", " assert polygon_intersection(first, Square(Point(3, 3), 1)) is None # Point contact.\n", " inner = Square(Point(1, 1), 1)\n", " assert isclose(polygon_intersection(first, inner).area(), 1)\n", " triangle = Triangle(Point(0, 0), Point(4, 0), Point(0, 4))\n", " assert isclose(polygon_intersection(triangle, Square(Point(0, 0), 2)).area(), 4)\n", "\n", "\n", "# check_polygon_intersection()\n" ], "outputs": [], "execution_count": 29 }, { "cell_type": "markdown", "id": "geometry-058", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-059", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:54:15.650398Z", "start_time": "2026-10-21T21:54:15.645557Z" } }, "source": [ "def polygon_intersection(first, second):\n", " output = list(first.vertices)\n", " clip = second.vertices\n", " for a, b in zip(clip, clip[1:] + clip[:1]):\n", " if not output:\n", " return None\n", " source, output = output, []\n", " edge = b - a\n", " start = source[-1]\n", " start_inside = edge.cross(start - a) >= -EPS\n", " for end in source:\n", " end_inside = edge.cross(end - a) >= -EPS\n", " if start_inside != end_inside:\n", " crossing = Line.from_points(start, end).intersection(Line.from_points(a, b))\n", " if crossing is None:\n", " raise ValueError(\"numerically unstable clipping intersection\")\n", " output.append(crossing)\n", " if end_inside:\n", " output.append(end)\n", " start, start_inside = end, end_inside\n", " cleaned = polygon_or_none(output)\n", " if cleaned is None:\n", " return None\n", " output = list(cleaned.vertices)\n", " return polygon_or_none(output)\n", "\n", "\n", "check_polygon_intersection()\n" ], "outputs": [], "execution_count": 30 }, { "cell_type": "code", "id": "geometry-060", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:54:15.789400Z", "start_time": "2026-10-21T21:54:15.786168Z" } }, "source": [ "first = Square(Point(0, 0), 3)\n", "second = Square(Point(2, 1), 3)\n", "assert isclose((first & second).area(), 2)\n", "print(first & second)\n" ], "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Polygon(vertices=(Point(x=2.0, y=1.0), Point(x=3.0, y=1.0), Point(x=3, y=3), Point(x=2.0, y=3.0)))\n" ] } ], "execution_count": 31 }, { "cell_type": "markdown", "id": "geometry-061", "metadata": {}, "source": [ "## Multiple inheritance (Advanced)\n", "\n", "A class can combine more than one base class. Small **mixins** add focused behavior without redefining the shape itself.\n", "For example, we can add bounding boxes and SVG output to a Rectangle.\n", "\n", "Python searches methods using the **method resolution order** (MRO), visible through `SomeClass.mro()`.\n", "`super()` continues after the current class in the MRO of the actual instance. It can reach another mixin,\n", "not just the class written as the current class's parent.\n", "\n", "If multiple methods cooperate through `super()`, they need compatible arguments and a clear stopping point.\n", "Explicitly calling a particular base class can skip the rest of that chain.\n" ] }, { "cell_type": "markdown", "id": "geometry-062", "metadata": {}, "source": [ "## Exercise 8: Draw polygons with mixins\n", "\n", "Implement two mixins that expect a `vertices` attribute:\n", "\n", "- `BoundsMixin.bounds()` returns `(min_x, min_y, max_x, max_y)`.\n", "- `SvgMixin.to_svg()` returns one SVG `` element. Use `\"x,-y\"` coordinate pairs because SVG's y axis points downwards.\n", " Read the style from `self.svg_style()`.\n", "- `SvgMixin.svg_style()` returns `\"fill:none;stroke:steelblue;stroke-width:0.06\"`.\n", "\n", "Combine them with Rectangle in `DrawableRectangle(BoundsMixin, SvgMixin, Rectangle)`.\n", "No new initializer is needed. This exercise adds drawing methods; inherited translation still returns a Rectangle.\n", "Preserving drawing capabilities through transformations would be a separate extension.\n", "\n", "Then implement `DashedMixin.svg_style()` as `super().svg_style() + \";stroke-dasharray:0.15 0.1\"`.\n", "Combine it in `DashedRectangle(DashedMixin, DrawableRectangle)`.\n", "\n", "What does `super()` in DashedMixin call? What happens if you reverse the order of those two bases?\n", "Print both MROs to explain the difference.\n" ] }, { "cell_type": "code", "id": "geometry-063", "metadata": { "tags": [ "exercise", "advanced" ], "ExecuteTime": { "end_time": "2026-10-21T21:54:42.417471Z", "start_time": "2026-10-21T21:54:42.413748Z" } }, "source": [ "class BoundsMixin:\n", " def bounds(self):\n", " pass\n", "\n", "\n", "class SvgMixin:\n", " def svg_style(self):\n", " return \"fill:none;stroke:steelblue;stroke-width:0.06\"\n", "\n", " def to_svg(self):\n", " pass\n", "\n", "\n", "class DrawableRectangle(BoundsMixin, SvgMixin, Rectangle):\n", " pass\n", "\n", "\n", "class DashedMixin:\n", " def svg_style(self):\n", " pass\n", "\n", "\n", "class DashedRectangle(DashedMixin, DrawableRectangle):\n", " pass\n" ], "outputs": [], "execution_count": 32 }, { "cell_type": "markdown", "id": "geometry-064", "metadata": {}, "source": [ "### Solution\n" ] }, { "cell_type": "code", "id": "geometry-065", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:54:44.997511Z", "start_time": "2026-10-21T21:54:44.992648Z" } }, "source": [ "class BoundsMixin:\n", " def bounds(self):\n", " xs = [p.x for p in self.vertices]\n", " ys = [p.y for p in self.vertices]\n", " return min(xs), min(ys), max(xs), max(ys)\n", "\n", "\n", "class SvgMixin:\n", " def svg_style(self):\n", " return \"fill:none;stroke:steelblue;stroke-width:0.06\"\n", "\n", " def to_svg(self):\n", " points = \" \".join(f\"{p.x},{-p.y}\" for p in self.vertices)\n", " return f''\n", "\n", "\n", "class DrawableRectangle(BoundsMixin, SvgMixin, Rectangle):\n", " pass\n", "\n", "\n", "class DashedMixin:\n", " def svg_style(self):\n", " return super().svg_style() + \";stroke-dasharray:0.15 0.1\"\n", "\n", "\n", "class DashedRectangle(DashedMixin, DrawableRectangle):\n", " pass\n", "\n", "\n", "class ReversedRectangle(DrawableRectangle, DashedMixin):\n", " pass\n", "\n", "\n", "shape = DashedRectangle(Point(1, 2), 4, 3)\n", "assert shape.bounds() == (1, 2, 5, 5)\n", "assert \"stroke-dasharray\" in shape.to_svg()\n", "assert \"stroke-dasharray\" not in ReversedRectangle(Point(1, 2), 4, 3).to_svg()\n", "for cls in [DashedRectangle, ReversedRectangle]:\n", " print([base.__name__ for base in cls.mro()])\n" ], "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['DashedRectangle', 'DashedMixin', 'DrawableRectangle', 'BoundsMixin', 'SvgMixin', 'Rectangle', 'Polygon', 'object']\n", "['ReversedRectangle', 'DrawableRectangle', 'BoundsMixin', 'SvgMixin', 'Rectangle', 'Polygon', 'DashedMixin', 'object']\n" ] } ], "execution_count": 33 }, { "cell_type": "markdown", "id": "geometry-066", "metadata": {}, "source": [ "### Example: draw the intersection\n", "\n", "The helper below combines SVG elements into a drawing. It uses only the standard library;\n", "a notebook can display the resulting SVG directly. If IPython is unavailable, it prints the SVG text.\n", "\n", "Add a translated polygon to the drawing. Does the original stay where it was?\n" ] }, { "cell_type": "code", "id": "geometry-067", "metadata": { "ExecuteTime": { "end_time": "2026-10-21T21:55:12.492502Z", "start_time": "2026-10-21T21:55:12.487028Z" } }, "source": [ "class DrawablePolygon(BoundsMixin, SvgMixin, Polygon):\n", " pass\n", "\n", "\n", "def svg_document(shapes):\n", " shapes = list(shapes)\n", " if not shapes:\n", " return ''\n", " bounds = [shape.bounds() for shape in shapes]\n", " left = min(b[0] for b in bounds) - 0.5\n", " bottom = min(b[1] for b in bounds) - 0.5\n", " right = max(b[2] for b in bounds) + 0.5\n", " top = max(b[3] for b in bounds) + 0.5\n", " content = \"\".join(shape.to_svg() for shape in shapes)\n", " return (f'{content}')\n", "\n", "\n", "first = DrawableRectangle(Point(0, 0), 3, 3)\n", "second = DashedRectangle(Point(2, 1), 3, 3)\n", "overlap = first & second\n", "picture = svg_document([first, second, DrawablePolygon(overlap.vertices)])\n", "try:\n", " from IPython.display import SVG, display\n", "except ImportError:\n", " print(picture)\n", "else:\n", " display(SVG(picture))\n" ], "outputs": [ { "data": { "text/plain": [ "" ], "image/svg+xml": "" }, "metadata": {}, "output_type": "display_data" } ], "execution_count": 35 }, { "cell_type": "markdown", "id": "geometry-068", "metadata": {}, "source": [ "## Exercise: Add another shape\n", "\n", "Add `RegularPolygon(Polygon)` constructed from a center, radius, and number of vertices.\n", "Use `sin` and `cos` to place equally spaced vertices on a circle. Reject nonpositive radii and fewer than three vertices.\n", "\n", "Check that its area, perimeter, translation, and intersection work with the existing code.\n", "Decide whether translation should return a RegularPolygon, then implement the required override.\n", "\n", "How much behavior did you inherit? Which methods did you actually need to write?\n" ] }, { "cell_type": "markdown", "id": "geometry-069", "metadata": {}, "source": [ "### Solution\n", "\n", "Store the construction parameters so translation can create another RegularPolygon with the same radius\n", "and vertex count. The vertices start at angle zero and proceed counterclockwise.\n", "\n", "The initializer passes the vertices to Polygon for validation. Since the dataclass is frozen,\n", "`object.__setattr__` initializes the additional fields. Ordinary assignment remains disabled afterward.\n", "Area, perimeter, containment, and intersection are inherited; only construction and translation need new implementations.\n" ] }, { "cell_type": "code", "id": "geometry-070", "metadata": { "tags": [ "solution" ], "ExecuteTime": { "end_time": "2026-10-21T21:57:31.133097Z", "start_time": "2026-10-21T21:57:31.122538Z" } }, "source": [ "from math import sin, cos, pi\n", "\n", "\n", "@dataclass(frozen=True, init=False)\n", "class RegularPolygon(Polygon):\n", " center: Point\n", " radius: float\n", " vertex_count: int\n", "\n", " def __init__(self, center, radius, vertex_count):\n", " if not isinstance(vertex_count, int) or isinstance(vertex_count, bool):\n", " raise TypeError(\"vertex count must be an integer\")\n", " if radius <= 0:\n", " raise ValueError(\"radius must be positive\")\n", " if vertex_count < 3:\n", " raise ValueError(\"at least three vertices are required\")\n", " vertices = tuple(\n", " center + Vector(radius * cos(2 * pi * i / vertex_count),\n", " radius * sin(2 * pi * i / vertex_count))\n", " for i in range(vertex_count)\n", " )\n", " super().__init__(vertices)\n", " object.__setattr__(self, \"center\", center)\n", " object.__setattr__(self, \"radius\", radius)\n", " object.__setattr__(self, \"vertex_count\", vertex_count)\n", "\n", " def translated(self, vector):\n", " return RegularPolygon(self.center + vector, self.radius, self.vertex_count)\n", "\n", "\n", "def check_regular_polygon():\n", " for count in (3, 4, 6):\n", " center, radius = Point(1, 2), 2\n", " shape = RegularPolygon(center, radius, count)\n", " assert len(shape) == count\n", " assert all(isclose(point.distance_to(center), radius) for point in shape)\n", " assert isclose(shape.area(), count * radius ** 2 * sin(2 * pi / count) / 2)\n", " assert isclose(shape.perimeter(), 2 * count * radius * sin(pi / count))\n", " assert shape.contains(center)\n", " moved = shape + Vector(10, -3)\n", " assert type(moved) is RegularPolygon\n", " assert moved.center == Point(11, -1)\n", " assert moved.radius == radius and moved.vertex_count == count\n", " assert isclose(moved.area(), shape.area())\n", " assert isclose(moved.perimeter(), shape.perimeter())\n", " assert shape.center == center\n", " assert (shape & moved) is None\n", " assert isclose((shape & shape).area(), shape.area())\n", " overlap = shape & (shape + Vector(0.5, 0))\n", " assert overlap is not None and 0 < overlap.area() < shape.area()\n", " expect_error(FrozenInstanceError, lambda: setattr(shape, \"radius\", 5))\n", " expect_error(ValueError, lambda: RegularPolygon(Point(0, 0), 0, 6))\n", " expect_error(ValueError, lambda: RegularPolygon(Point(0, 0), -1, 6))\n", " expect_error(ValueError, lambda: RegularPolygon(Point(0, 0), 1, 2))\n", " expect_error(TypeError, lambda: RegularPolygon(Point(0, 0), 1, 3.5))\n", "\n", "\n", "check_regular_polygon()\n", "hexagon = RegularPolygon(Point(0, 0), 2, 6)\n", "print(\"Area:\", hexagon.area())\n", "print(\"Perimeter:\", hexagon.perimeter())\n", "print(\"Translated center:\", (hexagon + Vector(3, 1)).center)\n" ], "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Area: 10.392304845413264\n", "Perimeter: 12.0\n", "Translated center: (3, 1)\n" ] } ], "execution_count": 36 }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": "", "id": "76bc1a43abeb9517" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.10" } }, "nbformat": 4, "nbformat_minor": 5 }