**Homework 5 -- Due 2/28** **[ENGR 52 Spring 2020](index.html)** # 2D Polygon Offset Your task this week is to write a Python script, `polygon_offset.py` that should take three command line inputs: * the name of a single text file of points describing a CCW-wound convex polygon, * an offset radius $r$ that specifies the distance between the input and output polygons, * and a final argument `miter` or `round` that indicates whether to leave outer corners pointed or replace them with arc segments. The script should output an SVG file named `polygon.svg` that contains two paths: a filled red path for the offset polygon, and an unfilled black path for the input polygon. ## Example inputs and outputs I'm supplying you five different input files: * [`rect.txt`](homework5/rect.txt) * [`triangle.txt`](homework5/triangle.txt) * [`quad.txt`](homework5/quad.txt) * [`hexagon.txt`](homework5/hexagon.txt) * [`circle.txt`](homework5/circle.txt) **For simplicity's sake, I strongly suggest you begin with `rect.txt`, as it is quite amenable to print debugging.** It's also not a bad idea to try your own files. Here are some snapshots of SVG output when I run my solution code (command line arguments shown below each image): ![`hexagon.txt 4.0 miter`](homework5/hexagon_4_miter.png width="300px") ![`circle.txt 3.0 miter`](homework5/circle_3_miter.png width="300px") ![`quad.txt 5.0 round`](homework5/quad_5_round.png width="300 px") ![`triangle.txt 8.0 round`](homework5/triangle_8_round.png width="300 px") ![`hexagon.txt -5 miter`](homework5/hexagon_-5_miter.png width="300px") ![`circle.txt -3 miter`](homework5/circle_-3_miter.png width="300px") Note that your code should correctly handle a small negative offset radius for mitered polygons, as shown above. It need not report an error if edges collapse for large negative values, as shown here: ![`hexagon.txt -18.0 miter`](homework5/hexagon_-18_miter.png width="300px") It's also fine if your program output looks bizarre when computing rounded polygons with a negative offset radius: ![`quad.txt -8.0 round`](homework5/quad_-8_round.png width="300px") ## Pseudocode The pseudocode below may be helpful to complete the assignment. ### Mitered To construct a mitered (sharp-cornered) offset polygon, I suggest you follow this pseudocode: ~~~ None initialize lines array L = [] for each successive pair of points p0, p1 of the polygon P: construct the vector [a, b, c] of implicit coefficients for the line from p0 -> p1 append line [a, b, c + radius] to L initialize the offset polygon array Q = [] for each successive pair of line coefficents l0, l1 in L: construct the (x, y) coordinates of the intersection of these two lines append (x, y) to P ~~~ See the appendix below for review of the geometric/mathematical operations from class. ### Round You will want to read the [SVG documentation on arcs](https://www.w3.org/TR/SVG11/paths.html#PathDataEllipticalArcCommands) to figure out how to add rounded parts to your path. For the arcs we are outputting, it is sufficient to fix the following parameters for each arc: * *x-axis-rotation* should be 0 * *large-arc-flag* should be 0 * *sweep-flag* should be 1 Therefore, the only arc parameters you need to set from variables are the radius *rx* and *ry* (both equal to the offset radius) and the destination point *x* *y*. Here is pseudocode for outputting rounded offset paths: ~~~ None for each point p2 in polygon P: let p1 be the predecessor to p2 in P let n1 be the normal vector of the edge from p1 to p2 if no SVG path segments emitted yet: let p0 be the predecessor to p1 in P let n0 be the normal vector of the edge from p0 to p1 let q0 = p1 - radius * n0 output SVG command to move to q0 let q1 = p1 - radius * n1 output SVG arc command to arrive at q1 with given radius let q2 = p2 - radius * n1 output SVG line command to arrive at q2 ~~~ ## Python/numpy tips You may find the following code useful for handling command line arguments: ~~~ Python try: polygon_filename = sys.argv[1] radius = float(sys.argv[2]) ctype = sys.argv[3] assert ctype in 'miter, round' except: print('usage: python polygon_offset.py POLYGONFILE R (miter|round)') sys.exit(1) ~~~ Three functions you might find useful in completing this project: * [`numpy.dot`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.dot.html) computes the dot product between two vectors: ~~~ Python >>> p = np.array([3, 2]) >>> n = np.array([-4, 3]) >>> print(np.dot(p, n)) -6 ~~~ * [`numpy.cross`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.cross.html) computes the cross product between two vectors: ~~~ Python >>> x = np.array([1, 0, 0]) >>> y = np.array([0, 1, 0]) >>> print(np.cross(x, y)) [0, 0, 1] ~~~ * [`numpy.linalg.norm`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.norm.html) computes the length of a vector. You can also use it to normalize a vector: ~~~ Python >>> p1 = np.array([2, 3]) >>> p2 = np.array([5, 7]) >>> d = p2 - p1 >>> print(d) [3 4] >>> print(np.linalg.norm(d)) 5.0 >>> n = d / np.linalg.norm(d) >>> print(n) [0.6 0.8] ~~~ Feel free to ask questions on Piazza if you run into `numpy` or python issues. # Turn-in Submit a single `polygon_offset.py` file to the [course moodle](https://moodle.swarthmore.edu/mod/assign/view.php?id=386947). # Appendix: recap of class discussion ## Line representations ### Two points Specify a line or line segment by two points on it: $\mathbf{p}_0 = (x_0, y_0), \mathbf{p}_1 = (x_1, y_1)$. ### Point and tangent (parametric) Parametric, vector-based representation $$ \mathbf{p}(s) = \mathbf{p}_0 + s \mathbf{t} $$ where $\mathbf{p}_0$ is a point on the line and $\mathbf{t}$ is a tangent vector with $\| \mathbf{t} \| = 1$. ### Point and normal (implicit) Implicit vector-based representation $$ \mathbf{p} \cdot \mathbf{n} = \mathbf{p}_0 \cdot \mathbf{n} $$ where $\mathbf{p}_0$ is a point on the line and $\mathbf{n}$ is a normal vector with $\| \mathbf{n} \| = 1$. The constant $$\mathbf{p}_0 \cdot \mathbf{n}$$ corresponds to the distance along the normal vector to reach the line from the origin. In contrast to a parametric representation, which gives a recipe to compute a point $\mathbf{p}$ along the line, the implicit form merely tells you whether a particular point $\mathbf{p}$ is on the line or not -- i.e., whether the equality relationship above is satisfied or not. ### General implicit form Expanding the equation above, we see that $$ \begin{align*} \mathbf{p} \cdot \mathbf{n} & = \mathbf{p}_0 \cdot \mathbf{n} \\ x \cdot n_x + y \cdot n_y &= x_0 \cdot n_x + y_0 \cdot n_y \\ x \cdot n_x + y \cdot n_y - x_0 \cdot n_x - y_0 \cdot n_y &= 0. \end{align*} $$ We can can rewrite this as the equation $$ ax + by + c = 0 $$ where $a = n_x$, $b = n_y$, and $c = -x_0 n_x - y_0 n_y$. ## Converting between representations ### Tangent vector from two points Given $\mathbf{p}_0$ and $\mathbf{p}_1$, let $\mathbf{d} = \mathbf{p}_1 - \mathbf{p}_0$. Then $$ \mathbf{t} = \frac{\mathbf{d}}{\|\mathbf{d}\|} = \frac{1}{\sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2}} \left[ \begin{array}{cc} x_1 - x_0 \\ y_1 - y_0 \end{array}\right]_{\textstyle{.}} $$ ### Normal vector to/from tangent vector The normal vector is obtained by rotating the tangent vector counterclockwise by 90°: $$ \mathbf{n} = \left[ \begin{array}{c} n_x \\ n_y \end{array}\right] = \left[ \begin{array}{cr} 0 & -1 \\ 1 & 0 \end{array}\right] \left[ \begin{array}{c} t_x \\ t_y \end{array}\right] = \left[ \begin{array}{r} -t_y \\ t_x \end{array}\right]_{\textstyle{.}} $$ Going the other way: $$ \mathbf{t} = \left[ \begin{array}{c} t_x \\ t_y \end{array}\right] = \left[ \begin{array}{rc} 0 & 1 \\ -1 & 0 \end{array}\right] \left[ \begin{array}{c} n_x \\ n_y \end{array}\right] = \left[ \begin{array}{r} n_y \\ -n_x \end{array}\right]_{\textstyle{.}} $$ ### Implicit from two points We can compute the implicit formula of a line from two points using a two-step process. The first step is to compute the cross product $$ \mathbf{m} = \left[ \begin{array}{c} u \\ v \\ w \end{array}\right] = \left[ \begin{array}{c} x_0 \\ y_0 \\ 1 \end{array}\right] \times \left[ \begin{array}{c} x_1 \\ y_1 \\ 1 \end{array}\right]_{\textstyle{.}} $$ The next step is to normalize. Let $$ \mathbf{\ell} = \left[\begin{array}{c} a \\ b \\ c \end{array}\right] = \frac{1}{\sqrt{u^2 + v^2}} \left[\begin{array}{c} u \\ v \\ w \end{array}\right]_{\textstyle{.}} $$ Note that after this step, the unit-length normal of the line is given by $$ \mathbf{n} = \left[ \begin{array}{c} a \\ b \end{array}\right]_{\textstyle{.}} $$ ## Intersection of two lines in implicit form Given two lines whose implicit coefficients are $\mathbf{\ell}_0 = (a_0, b_0, c_0)$ and $\mathbf{\ell}_1 = (a_1, b_1, c_1)$, find the $(x, y)$ that satisifies both equations $a_0 x + b_0 y + c = 0$ and $a_1 x + b_1 y + c = 0$. As in the section above, we solve this using a cross product followed by a normalization step. Let $$ \mathbf{q} = \left[ \begin{array}{c} u \\ v \\ w \end{array}\right] = \left[ \begin{array}{c} a_0 \\ b_0 \\ c_0 \end{array}\right] \times \left[ \begin{array}{c} a_1 \\ b_1 \\ c_1 \end{array}\right]_{\textstyle{.}} $$ Then the final intersection coordinates are given by $x = u/w$ and $y = v/w$. In the event that the two lines are either exactly parallel or coincedent, then $w = 0$ and the intersection is undefined.