Exploration of polygon boundaries

.gitignore

# Node.js dependencies
node_modules/

# Parcel files
.cache/
dist/

README.md

gist-polygon-boundary

Exploration of polygon boundaries

Documentation

• See npm run for commands

index.js

index.pug

//- Define common variables
- let canvasSize = 200;
- let pixelSize = 10;

//- Define our page content
doctype html
html(lang="en")
  head
    //- Define meta tags
    meta(charset="utf-8")
    meta(name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no")

    //- Use Bootstrap for pretty content
    link(rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.5.2/css/bootstrap.min.css" integrity="sha384-JcKb8q3iqJ61gNV9KGb8thSsNjpSL0n8PARn9HuZOnIxN0hoP+VmmDGMN5t9UJ0Z" crossorigin="anonymous")

    title gist-polygon-boundary

    //- Set up page styles
    style.
      canvas {
        border: 1px solid black;
      }

    //- Set up an empty script for our HMR hook
    script(src="index.js")

  body
    header
      h1 gist-polygon-boundary
      p Exploration of polygon boundaries
      p
        | Today it clicked that polygon boundaries are mostly a combination of line boundaries
        br
        | which are mostly > or < comparisons
        br
        | so we're coding up some examples for ourselves, then double checking what we've read before long ago
    //- Define common setup
    script.
      window.assert = function (val, msg) {
        if (!val) {
          throw new Error(msg || 'Expected value to be `true` but it was ' + val);
        }
      };
      window.drawOnCanvas = function (canvasEl, pxCallback) {
        // Resolve our context
        window.assert(canvasEl, 'Missing canvas element');
        let ctx = canvasEl.getContext('2d');

        // Draw our pixels
        // DEV: Technically using a callback is inefficient in drawing as it's constantly adding to the stack
        //   but this is more for demo/learning purposes
        //   Also JIT compilation should kick in if needed
        let pxSize = window.pixelSize;
        for (let x = 0; x < window.canvasSize; x += pxSize) {
          for (let y = 0; y < window.canvasSize; y += pxSize) {
            pxCallback(ctx, x, y, pxSize);
          }
        }

        // Return our context for customization
        return ctx;
      };
    script
      = 'window.canvasSize = ' + canvasSize + ';'
      = 'window.pixelSize = ' + pixelSize + ';'

    section
      h2 Checkboard test pattern
      canvas#canvasCheckerboard(width=canvasSize height=canvasSize)
      script.
        (function () {
          let canvasCheckerboardEl = document.getElementById('canvasCheckerboard');
          window.drawOnCanvas(canvasCheckerboardEl, function (ctx, x, y, pxSize) {
            ctx.fillStyle = (x % (pxSize * 2) ^ y % (pxSize * 2)) ? '#fff' : '#000';
            ctx.fillRect(x, y, pxSize, pxSize);
          });
        }());

    section
      h2 Boundary line pattern
      canvas#canvasBoundaryLine(width=canvasSize height=canvasSize)
      script.
        (function () {
          // Fill in pixels for our line
          let canvasBoundaryLineEl = document.getElementById('canvasBoundaryLine');
          let yIntercept = window.canvasSize * 0.6;
          let slope = -0.5;
          let ctx = window.drawOnCanvas(canvasBoundaryLineEl, function (ctx, x, y, pxSize) {
            let yBoundary = x * slope + yIntercept;
            ctx.fillStyle = (y > yBoundary) ? '#fff' : '#000';
            ctx.fillRect(x, y, pxSize, pxSize);
          });

          // Draw the line itself
          ctx.beginPath();
          ctx.moveTo(0 /* x */, yIntercept);
          let endY = window.canvasSize * slope + yIntercept;
          ctx.lineTo(window.canvasSize, endY);
          ctx.closePath();
          ctx.lineWidth = 2;
          ctx.strokeStyle = '#00f';
          ctx.stroke();
        }());
      p
        | Note how the line is above the hard boundary.
        br
        | I guess this is because we're using the upper-left corner of pixels, than the pixel center
        br
        | Correction: Centroid, center is for circles only apparently, https://diffsense.com/diff/center/centroid

    section
      h2 Triangle
      p.bg-warning
        | The following example is overbuilt, apparently we can just use cross products and dot products
        br
        | The issue though is that while I understand how to calculate these values, I'm getting overwhelmed at remembering what they actually do
        br
        | I might come back to this later, I might not
        br
        | Kind of frustrated that there's no explainer which does what I do that I can find early on =/
      canvas#canvasTriangle(width=canvasSize height=canvasSize)
      script.
        (function () {
          // Define our setup
          let canvasTriangleEl = document.getElementById('canvasTriangle');
          let trianglePoints = [
            {x: 0, y: 90},
            {x: 180, y: 40},
            {x: 200, y: 200},
          ];

          // Verify our triangle is right handed chiral
          // DEV: This is required for orientation to work, otherwise our comparisons are off
          //   Though, I'm still uncertain
          // DEV: Right hand chiral would mean... at least 1 line from (0,0)-ish to (1,1)-ish
          let isRightHanded = trianglePoints.some((startVertex, i) => {
            // Resolve our next adjacent point
            let endVertex = trianglePoints[(i + 1) % trianglePoints.length];
            console.log(startVertex.x, endVertex.x, startVertex.y, endVertex.y);
            console.log(startVertex.x < endVertex.x, startVertex.y < endVertex.y);
            return (startVertex.x < endVertex.x && startVertex.y < endVertex.y);
          });
          if (!isRightHanded) {
            console.info('Reversing triangle');
            trianglePoints.reverse();
          }

          // Calculate lines eagerly
          // For each of our adjacent triangle points, verify our point is within their line
          //   This line is infinitely extended
          let triangleLines = trianglePoints.map((startVertex, i) => {
            // Resolve our next adjacent point
            let endVertex = trianglePoints[(i + 1) % trianglePoints.length];

            // Determine our infinitely extended line info
            // DEV: slope = rise/run
            let slope = (endVertex.y - startVertex.y) / (endVertex.x - startVertex.x);
            // DEV: yIntercept via `y = mx + b (yIntercept)` -> `b = y - mx`
            let yIntercept = startVertex.y - (slope * startVertex.x);

            // Determine our line's orientation
            // DEV: We have startVertex -> endVertex always
            //   but the line is ignorate of that vector so we need to persist how that went
            //   If the slope is positive and starting from a "lower" position (assuming 0,0 is lower left)
            //   then, boundary is positive
            //   If slope is negative and start "low", then boundary negative
            //   If slope is positive and start "high", then boundary negative
            //   If slope is negative and start "high", then boundary positive
            let orientation = (slope >= 0) ^ (endVertex.y > startVertex.y);

            // Return our info
            return { slope, yIntercept, orientation };
          });

          // Perform our triangle drawing
          let ctx = window.drawOnCanvas(canvasTriangleEl, function (ctx, x, y, pxSize) {
            // Verify this point is in all our lines
            let inTriangle = triangleLines.every((lineInfo) => {
              // Determine if our point is above or below the line
              let yBoundary = x * lineInfo.slope + lineInfo.yIntercept;
              let underLine = y < yBoundary;

              // Use line orientation to determine how to compare line boundary
              return lineInfo.orientation ? underLine : !underLine;
            });
            ctx.fillStyle = inTriangle ? '#fff' : '#000';

            // Draw our pixel
            ctx.fillRect(x, y, pxSize, pxSize);
          });

          // Draw lines using our equations
          ctx.beginPath();
          triangleLines.forEach((lineInfo) => {
            ctx.moveTo(0 /* x */, lineInfo.yIntercept);
            let endY = window.canvasSize * lineInfo.slope + lineInfo.yIntercept;
            ctx.lineTo(window.canvasSize, endY);
          });
          ctx.lineWidth = 2;
          ctx.strokeStyle = '#00f';
          ctx.closePath();
          ctx.stroke();
        }());

package.json

{
  "name": "gist-polygon-boundary",
  "version": "1.0.0",
  "description": "Exploration of polygon boundaries",
  "main": "index.js",
  "scripts": {
    "start": "parcel index.pug --port 5000",
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "author": "Todd Wolfson <todd@twolfson.com> (http://twolfson.com/)",
  "license": "Unlicense",
  "dependencies": {},
  "devDependencies": {
    "parcel": "~1.12.4",
    "pug": "~3.0.0"
  }
}