31:T5d0,md` __Disclaimer__: I am not an expert in all of this, so if you find mistakes please tell me about it either via an suggestion (click on the three dots in the left of this cell) or via [twitter](https://twitter.com/_timhau) I recently found [this paper by Ralph Morrison](https://arxiv.org/pdf/1908.07012.pdf), which i definitly recommend reading as it is really nicely written and also contains much more details than my naive writing. Turns out [tropical geometry](https://en.wikipedia.org/wiki/Tropical_geometry) has nothing to do with palms and sun... it's actually named to honour the work of the brazilian mathematician [Imre Simon](https://en.wikipedia.org/wiki/Imre_Simon). Tropical geometry is subbranch of [algebraic geometry](https://en.wikipedia.org/wiki/Algebraic_geometry), which simply put, studies the geometric shapes that arise from polynomial equations. Tropical geometry does the same, except that it redefines the operations addition and multiplication. In tropical geometry addition is replaced with taking the maximum and multiplication is replaced by addition. Also the notation is slightly different to indicate that the operations aren't the same. Tropical addition uses the symbol ${tex`\oplus`} and tropical multiplication the symbol ${tex`\odot`}. (Small aside, there is also a variation of tropical geometry where addition is replaced by taking the minimum instead of the maximum. But you have to pick one and i decided to go with the maximum convention).`32:T49a,md`the arrows indicate that the line goes on up to infinity. We want to call lines like this rays. We can also see that the ray that goes to the left corresponds to all solutions where ${tex`y = 0`}, the ray that goes to the bottom corresponds to all solutions where ${tex`x = 0`} and the diagonal ray corresponds to the solutions where ${tex`x = y`}. We call this figure the * tropical curve * of the polynomial ${tex`p = 0 \oplus x \oplus y`} and we will write it as ${tex`\mathscr{T(p)}`}. For a much more satisfying definition I want to refer again to the [original paper](https://arxiv.org/pdf/1908.07012.pdf). But how do we find the tropical curve of a tropical polynomial? ## Newton Polygon and Triangulation If we plot the set of all tuples of exponents that appear in the tropical polynomial (recall this is the set ${tex`S \in \Z^2`} we used earlier in our definition for the tropical polynomial), we will see that they form a set of Points in ${tex`\R^2`}. The Newton Polygon is defined as the [convex hull](https://observablehq.com/@timhau/convex-hull) of those points. More formally it is defined as (see [original paper ](https://arxiv.org/pdf/1908.07012.pdf))`33:T5a4,md`But how do we get an tropical curve from the Newton Polygon? First we have to subdivide the Newton Polygon into triangles where each lattice point is a point of some triangle. In other words we have to triangulate the Newton Polygon. There are several ways to triangulate, but we want to determine a tropical curve based on our triangulation. So the way to do this is actually really nice (in my opinion). We start by assigning each lattice point of the Newton triangle a height. Remember that each lattice point corresponds to a pair of exponents. So a "natural" height to use is the constant term. So for example if we have a term like this ${tex`3 \odot x^1 \odot y^2`} in our polynomial then the corresponding lattice point would be ${tex`(1, 2)`} and it would have the height ${tex`3`}. Now we can use this height information as our third coordinate and draw the resulting points in ${tex`\R^3`}. So now we have a set of points in ${tex`\R^3`}. We continue by taking the convex hull (3D) of those points and get an polytope. Which is the 3D shape that consists of points, lines connecting those points and faces between those lines. The triangulation we are looking for are exactly those faces that are visible if we look from above straight down. Here is the triangulation in shorter words: - project points in 3D (using constant term as height) - take convex hull of those points - faces visible from above are the triangulation`34:T4ad,function gauss(A, x) { // thanks to https://github.com/itsravenous/gaussian-elimination/blob/master/gauss.js var i, k, j; // Just make a single matrix for (i = 0; i < A.length; i++) { A[i].push(x[i]); } var n = A.length; for (i = 0; i < n; i++) { // Search for maximum in this column var maxEl = abs(A[i][i]), maxRow = i; for (k = i + 1; k < n; k++) { if (abs(A[k][i]) > maxEl) { maxEl = abs(A[k][i]); maxRow = k; } } // Swap maximum row with current row (column by column) for (k = i; k < n + 1; k++) { var tmp = A[maxRow][k]; A[maxRow][k] = A[i][k]; A[i][k] = tmp; } // Make all rows below this one 0 in current column for (k = i + 1; k < n; k++) { var c = -A[k][i] / A[i][i]; for (j = i; j < n + 1; j++) { if (i === j) { A[k][j] = 0; } else { A[k][j] += c * A[i][j]; } } } } // Solve equation Ax=b for an upper triangular matrix A x = array_fill(0, n, 0); for (i = n - 1; i > -1; i--) { x[i] = A[i][n] / A[i][i]; for (k = i - 1; k > -1; k--) { A[k][n] -= A[k][i] * x[i]; } } return x; }35:[] 2f:{"title":"Introduction to tropical geometry","cells":[{"id":4643,"value":"md`# Introduction to tropical geometry`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4653,"value":"display = header()","pinned":false,"hidden":false,"mode":"ojs"},{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":904,"value":"md`**_example (1):_** \\ \nHere is an example of an expression in tropical notation and what it represents in conventional notation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":929,"value":"tex`(2 \\odot x) \\oplus (3 \\odot y^2) \\oplus -7 \\quad \\Leftrightarrow \\quad \\max\\{ 2 + x,\\; 3 + 2y,\\; -7 \\}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":941,"value":"md`Note that ${tex`y^2 = y \\odot y \\Leftrightarrow y + y = 2y`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":946,"value":"md`## tropical polynomials in 2 variables\n\nTo make it simpler we will look at tropical polynomials in 2 variables, which we name ${tex`x,y`}. A tropical polynomial is an expression of the following form, where ${tex`S`} is the set of all ${tex`(i,j) \\in \\Z`} which appear as exponents.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":952,"value":"md`${tex`\\underset{(i,j)\\in S}{\\bigoplus} (c_{i,j} \\odot x^{i} \\odot y^{j}) \\quad`} where ${tex`x,y,c \\in \\R,\\quad c \\neq -\\infty`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":969,"value":"md`which might look daunting at first but if you break it down it is not. The weird symbol ${tex`\\underset{(i,j)\\in S}{\\bigoplus} `} simply means the tropical sum over all tuples ${tex`(i,j)`} in the whole numbers. The expressions that get (tropical) summed are a (tropical) product of some coefficient ${tex`c_{i,j} \\in \\R`} and two variables. `","pinned":false,"hidden":false,"mode":"ojs"},{"id":985,"value":"html`\n

\n example (2):\n Here are some examples of polynomials and its translation into conventional notation.\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":988,"value":"tex`\n\\begin{aligned}\n0 \\oplus x \\oplus y \\quad &\\Leftrightarrow \\quad \\max\\{ x,\\; y,\\; 0\\} \\\\\n(3 \\odot y) \\oplus x \\oplus (-5 \\odot x^3) \\quad &\\Leftrightarrow \\quad \\max\\{ 3 + y,\\; x,\\; -5 + 3x\\} \\\\\n(0 \\odot x \\odot y) \\oplus (3 \\odot x^2) \\oplus (5 \\odot x^3 \\odot y^2) \\quad &\\Leftrightarrow \\quad \\max\\{ x + y,\\; 3 + 2x,\\; 5 + 3x + 2y \\}\n\\end{aligned}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1000,"value":"md`One Question we might ask is when the maximum will be achieved. If we take the first polynomial from the example above ${tex`0 \\oplus x \\oplus y`} we can see that the maximum is achieved when ${tex`x = y, \\; x = 0 \\text{ or } y = 0`}. If we would draw it in a 2-dimensional coordinate system it would look as follows:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1012,"value":"drawExamplePolynomialCurve()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1082,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":3007,"value":"tex`Newt(p) = conv(\\{ (i,j) \\in \\Z^2 \\mid x^i \\odot y^i \\text{ appears in } p(x,y) \\text{ with } c_{i,j} \\neq - \\infty \\})`","pinned":false,"hidden":false,"mode":"ojs"},{"id":3017,"value":"md`Where ${tex`conv`} denotes the convex hull and ${tex`p(x,y)`} is the tropical polynomial in 2 variables.\n\n**_example(3)_**: \\t\nhere is an example of the convex hull / the Newton Polygon.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":3021,"value":"{\n const height = 500;\n const context = DOM.context2d(width, height);\n context.translate(width / 2 - 10, height / 2 + 10);\n context.scale(1, -1);\n const gridStep = 55;\n drawGrid2D(context, gridStep);\n\n const pointsScaled = points.map(v => {\n const p = [v[0] * gridStep, v[1] * gridStep];\n circle([...p, 3], context);\n return p;\n });\n const hull2D = convexHull2D(pointsScaled);\n\n const hl = hull2D.length;\n context.beginPath();\n context.moveTo(...hull2D[0]);\n for (let i = 1; i < hl; ++i) {\n context.lineTo(...hull2D[i]);\n }\n context.fillStyle = \"rgba(180,180,180,0.5)\";\n context.fill();\n\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3071,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":3451,"value":"html`

Note:

Click on a polynom in the box below to change the view (only one is selected)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2932,"value":"viewof currentPolynom = select({\n description: \"Select a polynom to display\",\n options: [polynom1, polynom2, polynom3, polynom4, polynom5, headerPolynom],\n multiple: true,\n value: polynom4\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":4596,"value":"html`

Note:

click and drag to navigate`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"{\n const renderer = new THREE.WebGLRenderer({ antialias: true });\n renderer.shadowMap.enabled = true;\n renderer.shadowMap.type = THREE.PCFSoftShadowMap;\n const controls = new THREE.OrbitControls(camera, renderer.domElement);\n invalidation.then(() => (controls.dispose(), renderer.dispose()));\n\n renderer.setSize(width, width);\n renderer.setPixelRatio(devicePixelRatio);\n controls.addEventListener(\"change\", () => renderer.render(scene, camera));\n renderer.render(scene, camera);\n\n yield renderer.domElement;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":4056,"value":"md`*Small aside*: calculting this took me some time but was actually really fun. I start by looking at the normal vectors of each face. I use a buildin function from three.js but you could also use the cross product of two vectors from the face to figure it out. Then I look at the angle between the normal vector and one axis. If the angle is bigger than ${tex`\\frac{\\pi}{2}`} i know that the face is visible from above. If you find a mistake in my reasoning or an even better solution to this just send me an suggestion (clicking on the three dots to the left of this cell and the comment)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4069,"value":"md`So now we know the triangulation of our Newton polygon. To find the tropical curve corresponding to the polynomial we now have to look at the equations. Each vertex of a smaller triangle in the triangulation corresponds to a term in the polynomial. This gives us exactly three terms per triangle. We know want to find the \"root\" of those terms. The root of a tropical polynomial is a point where the maximum is realised at least two times (again [original paper for a correct definition](https://arxiv.org/pdf/1908.07012.pdf))`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4079,"value":"md`**_example(4):_** \\t\nthree such terms could be ${tex`2 \\odot x^2 \\odot y, \\; 1 \\odot x, \\; y`} which is ${tex`2 + 2x + y, \\; 1 + x, \\; y`} in conventional notation. To find the tropical root we have to find a point ${tex`(x,y) \\in \\R^2`} where ${tex`2 + 2x + y = 1 + x = y`}. After rearraning the terms we can obtain a system of two equations in two variables which can be solved using the [famous gauss algorihm](https://en.wikipedia.org/wiki/Gaussian_elimination). \n\nNote that sometimes multiple equations can have the same solution. In those cases the points of the tropical line collide.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":802,"value":"{\n const context = DOM.context2d(width, width);\n context.translate(width / 2 + 30, width / 2 - 30);\n context.scale(1, -1);\n drawGrid2D(context, 40);\n\n const gridStep = 40;\n const triangulation = newtonTriangulation2D(points, { gridStep });\n drawNewtonTriangulation2D(triangulation, context, { gridStep });\n\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":4612,"value":"md`So we can now calulate a tropical root for all equations that correspond to a triangle in the subdivision. If the roots not collide it can be seen that every point of the tropical curve is dual to a face of the triangulation and that every solution of the polynomial lies either on a line connecting two such points or on a ray that is emited by a point. A ray on the other hand is dual to an bounding edge of the triangulation and a connecting line between two points is dual to the line of a triangle that connects two faces (it is actually perpendicular to that line). Now we can calulate the neighbors and the corresponding angles in our triangulation and are now able to draw the tropical curve.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2316,"value":"{\n const context = DOM.context2d(width, width);\n context.translate(width / 2 + 30, width / 2 - 30);\n context.scale(1, -1);\n\n const triangulation = findNewtonTriangulation(points);\n drawTropicalCurve(triangulation, poly, context, { gridStep: 50 });\n\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":4627,"value":"md`## Motivation\n\n**So we do people care about tropical geometry?** \\t\n\nI care because it was a fun challenge with beatiful shapes and for me that is motivation enough. But as I understood it has also other applications. First due to the nature of the equations you could use this kind of reasoning for some optimization tasks. On the other hand and probably more important you could use the much simpler world of linear equations to study general algebraic geometry. As it turns out a lot of theorems that hold in algebraic geometry are also true in tropical geometry and the other way around. If you want to know more about those and a lot other topics I did not touch on check out the papers below.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1151,"value":"md`### Further reading:\n\n[The original Paper that inspired me by Ralph Morrison](https://arxiv.org/pdf/0808.2383.pdf)\n[This paper by Erwan Brugallé and Kristin Shaw](https://arxiv.org/pdf/1311.2360.pdf) \\t\n\nworth noting:\n\nIf you are looking for actually calculating, this tool might help: [polymake](https://polymake.org/doku.php)\n\n---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4163,"value":"md`# Code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4170,"value":"md`## example polynomials`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2672,"value":"polynom1 = \"3 + 2*x + 2*y + 3*x*y + x^2 + y^2\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":2961,"value":"polynom2 = \"1 * x^2 + 1 * y^2 + 2 * x * y + 2 * x + 2 * y + 1\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":2706,"value":"polynom3 =\n \"5 + (5 * x) + (6 * y) + (6 * x * y) + (4 * x^2) + (4 * y^2) + (4 * x^2 * y) + (1 * x^3) + (1 * y^3) + (3 * x * y^2)\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":2939,"value":"polynom4 =\n \"11 + (10 * x) + (10 * y) + (10 * x * y) + (7 * x^2) + (7 * y^2) + (10 * x^-1) + (10 * y^-1) + (10 * x^-1 * y^-1) + (9 * x * y^-1) + (9 * x^-1 * y) + (7 * x^-2) + (7 * y^-2) + (4 * x^2 * y^-2) + (6 * x^-2 * y^-2) + (4 * x^-2 * y^2) + (6 * x^2 * y^2) + (3 * x^3) + (3 * x^-3) + (3 * y^3) + (3 * y^-3)\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":2969,"value":"polynom5 =\n \"11 + (5 * x) + (10 * y) + (10 * x * y) + (8 * x^2) + (8 * y^2) + (8 * x^2 * y) + (5 * x^3) + (5 * y^3) + (7 * x * y^2) + (5 * x^-1) + (9 * y^-1) + (10 * x^-1 * y^1) + (8 * x^-1 * y^2) + (8 * x^-2) + (8 * x^-2 * y) + (5 * x^-3) + (7 * x^-1 * y^-1) + (5 * x^-2 * y^-1) + (7 * x * y^-1) + (5 * x^2 * y^-1) + (5 * y^-2) + (2 * y^-3) + (4 * x * y^-2) + (4 * x^-1 * y^-2)\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":3081,"value":"headerPolynom =\n \"(14.5 * x^2 * y^-1) + (14.65 * x * y) + (12.1 * y^2) + (15 * x) + (13.9 * y) + 1 + (3.9 * x^2 * y^2) + (12.4 * x^-1) + (14 * y^-1) + (4.5 * x^4 * y^2) + (8.5 * x^5 * y^-1) + (14.4 * x^3 * y) + (8.8 * x * y^3) + (-1.8 * x^-4 * y^3) + (7 * x^-2 * y^2) + (10 * x^2 * y^-3) + (12.7 * y^-2) + (14.5 * x^3) + (8 * x^-3) + (7.9 * x^-1 * y^3) + (9 * x^4 * y^-3) + (10.4 * x^-2 * y^-1) + (4.9 * x^-4 * y) + (10.3 * x^-2 * y) + (-0.2 * x^-2 * y^4) + (2 * x^-4 * y^-1) + (-2 * x^7) + (8.6 * x^-2 * y^-3) + (12.5 * x^4) + (10 * x^3 * y^3) + (8 * x^5 * y) + (1 * x^3 * y^5) + (-7 * x^-5) + (5.5 * y^-4) + (-6 * x^-5 * y^3) + (-3 * x^-5 * y^2) + (-3.5 * x^-4 * y^-3) + (-2 * y^5)\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":2937,"value":"poly = buildPoly(...currentPolynom)","pinned":false,"hidden":false,"mode":"ojs"},{"id":4167,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1909,"value":"md`## solving equations\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4227,"value":"md`First parse the terms, meaning strip all the variables and just use the coefficients. The Format is [x,y,c] where x is the x coefficient, y the y coefficient and c the constant term.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1926,"value":"function solveEquation(terms) {\n const parsed = terms\n .slice()\n .sort()\n .map(t => parseTerm(t));\n\n const [x1, y1, c1] = parsed[0];\n const [x2, y2, c2] = parsed[1];\n const [x3, y3, c3] = parsed[2];\n\n return gauss([[x2 - x1, y2 - y1], [x3 - x2, y3 - y2]], [c1 - c2, c2 - c3]);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2417,"value":"md`gauss algorithm is borrowed from [here](https://github.com/itsravenous/gaussian-elimination/blob/master/gauss.js). For more information i recommend a introduction book about linear algebra.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2414,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":2411,"value":"function array_fill(i, n, v) {\n var a = [];\n for (; i < n; i++) {\n a.push(v);\n }\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1936,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4115,"value":"md`## draw functions`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4231,"value":"md`Draw a 2D representation of the newton triangulation in 3D space. It is drawn 0.5 steps above the highest coefficient to make the connection between 3D convex hull and triangulation clear.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":747,"value":"function drawNewtonTriangulation3D(triangulation, scene) {\n triangulation.forEach(face => {\n const projectedUp = face.map(v =>\n v.map((k, i) => (i === 2 ? maxCoeff + 0.5 : k))\n );\n addFace(projectedUp, scene, { wireframe: true });\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":4234,"value":"md`Draw the triangulation to an 2D canvas context.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1944,"value":"function drawNewtonTriangulation2D(triangulation, context, options) {\n const opts = Object.assign({ gridStep: gridStep }, options);\n\n for (let i = 0; i < triangulation.length; ++i) {\n const t = triangulation[i];\n triangle(t, context, { color: \"gray\", lineWidth: 3 });\n }\n\n points.forEach(p =>\n circle([p[0] * opts.gridStep, p[1] * opts.gridStep, 4], context)\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":4218,"value":"md`*known Issue*: \n\nI connect the \"inner\" points more than once. If a is a neighbor of b i connect a with b and b with a.\n\nFirst find all points, all the neighbors for each face and meassure the angle for each line in each face. Then draw the points and connect the neighbors with corresponding angles. If no neighbor is present use an big step to draw a ray. `","pinned":false,"hidden":false,"mode":"ojs"},{"id":3479,"value":"function drawTropicalCurve(triangulation, polynom, context, options) {\n const opts = Object.assign({ gridStep: gridStep, r: 4 }, options);\n const tropicalPoints = findTropicalPoints(\n triangulation,\n polynom,\n opts.gridStep\n );\n const angles = findAngles(triangulation);\n const neighbors = findNeighbors(triangulation);\n\n tropicalPoints.forEach((p, i) => {\n circle([...p, opts.r], context);\n\n neighbors[i].forEach((n, j) => {\n if (n !== 0 && !n) {\n const inf = coordsFromDeg(angles[i][j] - 90, 1000, p);\n line(p, inf, context);\n } else {\n const neigbor = tropicalPoints[n];\n line(p, neigbor, context);\n }\n });\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":789,"value":"function draw3DHull(hull, scene) {\n\n for (let [i1, i2, i3] of hull) {\n const face = [points[i1], points[i2], points[i3]];\n const color = randomColor();\n addFace(face, scene, { color });\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":859,"value":"function drawGrid2D(context, gs = gridStep) {\n for (let i = -gridSize; i < gridSize; ++i) {\n for (let j = -gridSize; j < gridSize; ++j) {\n const color = \"rgba(200, 200, 200, 1)\";\n line([i * gs, 0], [i * gs, j * gs], context, { color });\n line([0, i * gs], [j * gs, i * gs], context, { color });\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1006,"value":"function drawExamplePolynomialCurve() {\n const context = DOM.context2d(300, 300);\n context.translate(150, 150);\n\n circle([0, 0, 3], context);\n textAt([5, 15], \"(0,0)\", 11, context);\n line([0, 0], [-300, 0], context);\n line([0, 0], [0, 300], context);\n line([0, 0], [300, -300], context);\n\n // arrows\n context.moveTo(-149, 0);\n context.lineTo(-139, 5);\n context.lineTo(-139, -5);\n context.fill();\n\n context.moveTo(0, 149);\n context.lineTo(5, 139);\n context.lineTo(-5, 139);\n context.fill();\n\n context.moveTo(149, -149);\n context.lineTo(135, -141);\n context.lineTo(142, -133);\n context.fill();\n\n return context.canvas;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":4137,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4140,"value":"md`## find stuff`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1649,"value":"function findNeighbor([l1, l2], faceIndex, triangulation) {\n let neighbor = false;\n\n for (let i = 0; i < triangulation.length; ++i) {\n if (i === faceIndex) continue;\n\n const [p1, p2, p3] = triangulation[i];\n const lines = [[p1, p2], [p2, p3], [p3, p1]];\n lines.forEach(([p1, p2]) => {\n const p1Match = dist2D(p1, l1) === 0 || dist2D(p1, l2) === 0;\n const p2Match = dist2D(p2, l1) === 0 || dist2D(p2, l2) === 0;\n if (p1Match && p2Match) {\n neighbor = i;\n }\n });\n }\n\n return neighbor;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2333,"value":"function findAngles(triangulation) {\n const res = [];\n\n triangulation.forEach(([p1, p2, p3]) => {\n res.push([\n getAlphaBetweenPoints(p1, p2),\n getAlphaBetweenPoints(p2, p3),\n getAlphaBetweenPoints(p3, p1)\n ]);\n });\n\n return res;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2452,"value":"function findNeighbors(triangulation) {\n const res = [];\n\n for (let i = 0; i < triangulation.length; ++i) {\n const [p1, p2, p3] = triangulation[i];\n const lines = [[p1, p2], [p2, p3], [p3, p1]];\n\n const neighbors = [];\n for (let l of lines) {\n neighbors.push(findNeighbor(l, i, triangulation));\n }\n res.push(neighbors);\n }\n\n return res;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2307,"value":"function findTropicalPoints(triangulation, poly, gs = gridStep) {\n const res = [];\n\n triangulation.forEach((t, i) => {\n const term = findTermsFromPoints(t, poly);\n const p = solveEquation(term).map(v => v * gs);\n res.push(p);\n });\n\n return res;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2007,"value":"function findTermsFromPoints(points, poly) {\n const res = [];\n\n for (let [x, y, z] of points) {\n poly.forEach(({ point, term }, i) => {\n const [px, py, pz] = point;\n if (px === x && py === y && pz === z) res.push(term);\n });\n }\n\n return res;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":4125,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1951,"value":"md`## triangulation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":727,"value":"function findNewtonTriangulation(p) {\n const hull = qh3D(p);\n const hullUpperFaces = [];\n\n for (let [i1, i2, i3] of hull) {\n const face = [p[i1], p[i2], p[i3]];\n const [f, _] = makeFace(face);\n const normals = f.normal;\n const isUpper = normals.angleTo(new THREE.Vector3(0, 1, 0)) >= Math.PI / 2;\n const areaNotNull = areaTriangle(...face) > 0;\n if (isUpper && areaNotNull) {\n hullUpperFaces.push(face);\n }\n }\n\n return hullUpperFaces;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":873,"value":"function newtonTriangulation2D(points, options) {\n const opts = Object.assign({ gridStep: gridStep }, options);\n\n const triangulation = findNewtonTriangulation(points);\n const projected = projectTo2D(triangulation, opts);\n\n // filter triangles that are colinear\n const res = [];\n for (let i = 0; i < projected.length; ++i) {\n if (areaTriangle(...projected[i]) > 0) {\n res.push(projected[i]);\n }\n }\n\n return res;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":845,"value":"function projectTo2D(faces, options) {\n const opts = Object.assign({ gridStep: gridStep }, options);\n return faces.map(f =>\n f.map(v => [v[0] * opts.gridStep, v[1] * opts.gridStep])\n );\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":4122,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1932,"value":"md`## three.js helpers`","pinned":false,"hidden":false,"mode":"ojs"},{"id":46,"value":"function addCube([x, z, y], scene, options) {\n const opts = Object.assign({ color: 0x000000, r: 2 }, options);\n\n const geometry = new THREE.BoxBufferGeometry(opts.r, opts.r, opts.r);\n const material = new THREE.MeshBasicMaterial({ color: opts.color });\n const cube = new THREE.Mesh(geometry, material);\n cube.position.set(x * gridStep, y * gridStep, z * gridStep);\n scene.add(cube);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":84,"value":"function addLine([[x1, z1, y1], [x2, z2, y2]], scene, options) {\n const opts = Object.assign(\n { color: \"rgba(100,100,100,1)\", linewidth: 2 },\n options\n );\n\n const geometry = new THREE.Geometry();\n geometry.vertices.push(\n new THREE.Vector3(x1 * gridStep, y1 * gridStep, z1 * gridStep),\n new THREE.Vector3(x2 * gridStep, y2 * gridStep, z2 * gridStep)\n );\n const material = new THREE.LineBasicMaterial({\n color: opts.color,\n linewidth: opts.linewidth\n });\n const line = new THREE.Line(geometry, material);\n\n scene.add(line);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":289,"value":"function addPolygon(p, scene) {\n const points = p.slice().sort(([x1, y1], [x2, y2]) => x1 - x2);\n const geometry = new THREE.Geometry();\n\n // const pl = points.length;\n for (let i = 0; i < points.length; ++i) {\n const [x, z, y] = points[i];\n geometry.vertices.push(\n new THREE.Vector3(x * gridStep, y * gridStep, z * gridStep)\n );\n if (i >= 2) {\n geometry.faces.push(new THREE.Face3(i - 2, i - 1, i));\n }\n }\n\n const material = new THREE.MeshBasicMaterial({\n color: \"rgba(200, 200, 200, 1)\",\n side: THREE.DoubleSide\n });\n const mesh = new THREE.Mesh(geometry, material);\n scene.add(mesh);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":491,"value":"function addFace(points, scene, options) {\n const opts = Object.assign({ color: 0x000000, wireframe: false }, options);\n\n const [face, geometry] = makeFace(points);\n\n const material = new THREE.MeshBasicMaterial({\n color: opts.color,\n wireframe: opts.wireframe,\n side: THREE.DoubleSide\n });\n\n const mesh = new THREE.Mesh(geometry, material);\n\n scene.add(mesh);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":31,"value":"function addGrid([x, y], scene, options) {\n const opts = Object.assign({ color: 0x000000 }, options);\n const points = [];\n\n let counter = 0;\n for (let i = -x; i < x; ++i) {\n for (let j = -y; j < y; ++j) {\n const c = [i, j, 0];\n points.push(c);\n\n if (points.length > 1 && j !== -x) {\n addLine([points[counter - 1], c], scene);\n }\n counter += 1;\n\n if (i > -x) {\n addLine([points[counter - 1], points[counter - y - x - 1]], scene);\n }\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":764,"value":"function makeFace(points) {\n const geometry = new THREE.Geometry();\n\n for (let i = 0; i < 3; ++i) {\n geometry.vertices.push(\n new THREE.Vector3(\n points[i][0] * gridStep,\n points[i][2] * gridStep,\n points[i][1] * gridStep\n )\n );\n }\n\n const face = new THREE.Face3(0, 1, 2);\n geometry.faces.push(face);\n\n geometry.computeBoundingSphere();\n geometry.computeFaceNormals();\n\n return [face, geometry];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":4,"value":"THREE = {\n const THREE = (window.THREE = await require(\"three@0.99.0/build/three.min.js\"));\n await require(\"three@0.99.0/examples/js/controls/OrbitControls.js\").catch(\n () => {}\n );\n return THREE;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"scene = {\n const scene = new THREE.Scene();\n scene.background = new THREE.Color(0xffffff);\n\n addGrid([gridSize, gridSize], scene);\n\n const hull2D = convexHull2D(poly.map(({ point }) => [point[0], point[1]]));\n addPolygon(hull2D, scene);\n\n poly.forEach(({ point }) => {\n addCube(point, scene, { color: \"red\", r: 5 });\n addLine([point, [point[0], point[1], 0]], scene);\n addCube([point[0], point[1], 0], scene, { r: 4 });\n });\n\n const hull = qh3D(points);\n draw3DHull(hull, scene);\n const triangulation = findNewtonTriangulation(points);\n drawNewtonTriangulation3D(triangulation, scene);\n\n yield scene;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":10,"value":"camera = {\n const fov = 50;\n const near = 0.1;\n const far = 10000;\n const camera = new THREE.PerspectiveCamera(fov, 1, near, far);\n camera.lookAt(new THREE.Vector3(0, 0, 0));\n camera.position.set(500, 1800, 1500);\n\n yield camera;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1913,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2049,"value":"md`## utils `","pinned":false,"hidden":false,"mode":"ojs"},{"id":705,"value":"function randomColor() {\n return `rgba(${Math.floor(Math.random() * 255)},\n ${Math.floor(Math.random() * 255)},\n ${Math.floor(Math.random() * 255)},1)`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2679,"value":"function buildPoly(polynom) {\n const terms = toConventionalNotation(polynom);\n const points = terms.map(t => parseTerm(t));\n const res = [];\n\n for (let i = 0; i < points.length; ++i) {\n res.push({ point: points[i], term: terms[i] });\n }\n\n return res;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":4326,"value":"md`parsing the polynomial could definitly be improved..`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2674,"value":"function toConventionalNotation(polynom) {\n const splited = polynom.split(\"+\");\n\n const prodAsSum = splited.map(term => {\n const asSum = term.replace(/(\$|\$)/g, \"\").replace(/\\*/g, \"+\");\n const sumTerms = asSum.split(\"+\");\n const withExponent = sumTerms.map(t => {\n const [base, exp] = t.split(\"^\");\n return exp ? `${exp}${base}` : t;\n });\n return withExponent.join(\"+\").replace(/\\s/g, \"\");\n });\n\n return prodAsSum;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2421,"value":"function parseTerm(t) {\n const term = t.replace(/\\s/g, \"\");\n\n let xTerm = term.match(/\$?-?\\d*\\/?\\d*\$?\\*?x/g) || [\"0\"];\n let yTerm = term.match(/\$?-?\\d*\\/?\\d*\$?\\*?y/g) || [\"0\"];\n let constantTerm = term.split(\"+\").filter(v => !v.match(/(x|y)/g));\n\n // defaults\n if (constantTerm.length === 0) constantTerm = [\"0\"];\n if (xTerm[0] === \"x\") xTerm = [\"1\"];\n if (xTerm[0] === \"-x\") xTerm = [\"-1\"];\n if (yTerm[0] === \"y\") yTerm = [\"1\"];\n if (yTerm[0] === \"-y\") yTerm = [\"-1\"];\n\n // cleanup\n xTerm = xTerm.map(v => cleanUpTerm(v))[0];\n yTerm = yTerm.map(v => cleanUpTerm(v))[0];\n constantTerm = constantTerm.map(v => cleanUpTerm(v))[0];\n\n return [xTerm, yTerm, constantTerm];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1916,"value":"function cleanUpTerm(term) {\n // first time ever i use eval ... not sure if evil or right...\n return eval(term.replace(/(\$|\$|\\*|x|y)/g, \"\"));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":719,"value":"maxCoeff = points.reduce(\n (acc, curr) => (curr[2] >= acc ? curr[2] : acc),\n points[0][2]\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1998,"value":"points = poly.map(({ point }) => point)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2407,"value":"abs = Math.abs","pinned":false,"hidden":false,"mode":"ojs"},{"id":4649,"value":"function header() {\n const context = DOM.context2d(width, width / 2);\n context.translate(width / 2 - 5, width / 3 - 30);\n context.scale(1, -1);\n\n const headerPoly = buildPoly(headerPolynom);\n const headerPoints = headerPoly.map(({ point }) => point);\n\n const triangulation = findNewtonTriangulation(headerPoints);\n drawTropicalCurve(triangulation, headerPoly, context, {\n gridStep: 30,\n r: 2.3\n });\n\n return context.canvas;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2052,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1894,"value":"md`## imports\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":276,"value":"import {convexHull2D} from '@timhau/convex-hull'","pinned":false,"hidden":false,"mode":"ojs"},{"id":805,"value":"import { \n line,\n circle,\n triangle,\n areaTriangle,\n textAt,\n \n dist2D,\n getAlphaBetweenPoints,\n coordsFromDeg,\n} from '@timhau/geometry'","pinned":true,"hidden":false,"mode":"ojs"},{"id":4288,"value":"md`I would really like to understand how one can calulate the convex hull in 3D but I haven't found a source that I understand so I have to use this module. If you happen to know a good resource that explains it so that I can understand it I would be happy to know!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":486,"value":"qh3D = require(\"https://bundle.run/quickhull3d@2.0.4\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2930,"value":"import { select } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs"},{"id":1899,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":196,"value":"gridStep = 70","pinned":false,"hidden":false,"mode":"ojs"},{"id":808,"value":"gridSize = 10","pinned":false,"hidden":false,"mode":"ojs"},{"id":3455,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}