2

I have a set of coordinates that I want to draw an outline around. This question describes my problem perfectly, but unfortunately many of the resources go to dead links, and while the first answer is a great solution, I'm having trouble implementing it.

I've been experimenting with a primitive JS canvas as it's quick for prototyping, but ideally the solution will be language agnostic so I can easily port it to another language.

I've managed to do what I thought was the hard bit - calculate the coordinates of the offset lines. For instance, in the image below the green dots are the coordinates of two lines offset from the black dots.

two black dots, with four green dots being the coordinates of offset lines

The bit I'm struggling with is working out which order to visit each of the offset coordinates in. I've started trying to calculate just one side of the outline, and this is how far I've got:

enter image description here

The black dots are the coordinates to outline, the green dots are the offset line coordinates, and the numbered red line is the outline in the order the offset coordinates are visited.

The first line from 0 to 1 is correct, but then point 2 should be the top-left of those four dots, likewise for point 3.

Here's the code I've been using to generate the path.

canvas = document.getElementById("canvas");
ctx = canvas.getContext('2d');

const OFFSET = 10

ctx.fillStyle = '#aaa';
ctx.fillRect(0, 0, 400, 400);

class Point {
  constructor(x, y, colour = 'black') {
    this.x = x
    this.y = y
    this.colour = colour
  }

  draw() {
    // Draws a dot at the x, y coords
    ctx.beginPath();
    ctx.arc(this.x, this.y, 2, 0, 2 * Math.PI, false);
    ctx.fillStyle = this.colour;
    ctx.fill();
  }


  getOffsetPoint(lastPoint, colour, offset) {
    let gradient = -1 / ((this.y - lastPoint.y) / (this.x - lastPoint.x))

    let a = new Point(0, 0, colour)
    let b = new Point(0, 0, colour)
    if (gradient == 0) {
      a.x = this.x + offset
      a.y = this.y
    } else if (gradient == Infinity) {
      a.x = this.x
      a.y = this.y + offset
    } else {
      let dx = (offset / Math.sqrt(1 + (gradient * gradient)));
      let dy = gradient * dx;
      a.x = this.x + dx;
      a.y = this.y + dy;
    }

    a.draw()

    return a;
  }

  label(text) {
    ctx.fillStyle = 'black'
    ctx.font = "14px Arial";
    ctx.fillText(text, this.x + 4, this.y);
  }

}

/* Draws example two points and the offset coords
let a = new Point(50, 20)
let b = new Point(70, 70)
a.draw()
b.draw()

a.getOffsetPoint(b, 'green', 10)
a.getOffsetPoint(b, 'green', -10)

b.getOffsetPoint(a, 'green', 10)
b.getOffsetPoint(a, 'green', -10)
*/

// The path we want to outline
path = [new Point(100, 100), new Point(150, 200), new Point(200, 100), new Point(250, 300), new Point(300, 300), new Point(250, 350), new Point(100, 310)]

for (i = 0; i < path.length; i++) {
  path[i].draw()
}


outline_points = [] // Stores the outline

let a_offset_point, b_offset_point;
for (i = 1; i < path.length; i++) {
  let a = path[i - 1]
  let b = path[i]

  let offset = OFFSET;

  // if (some condition) { offset = offset * -1 }

  // Draws the offset points, and labels them with the order they'll be visited in
  a_offset_point = a.getOffsetPoint(b, 'green', offset)
  a_offset_point.label(outline_points.length);
  outline_points.push(a_offset_point)


  b_offset_point = b.getOffsetPoint(a, 'green', offset)
  b_offset_point.label(outline_points.length);
  outline_points.push(b_offset_point)

  // Draw the other two offset points we're not visiting
  a.getOffsetPoint(b, 'green', -offset)
  b.getOffsetPoint(a, 'green', -offset)

}

// Draws the outline path
ctx.beginPath()
ctx.moveTo(outline_points[0].x, outline_points[0].y)
for (i = 1; i < outline_points.length; i++) {
  ctx.lineTo(outline_points[i].x, outline_points[i].y)
}
ctx.strokeStyle = 'red'
ctx.stroke();
<canvas id="canvas" width=400 height=400>
</canvas>

It's a bit clunky, but line 86 is where I'm pretty sure the change needs to be made - depending on some condition (that most likely takes into account the coords of the two points), the sign of the offset should be flipped.

I've read something about normals, and think they may be able to help, but I'm not too sure how to calculate them, and then once I've got them how they could be used.

Thanks very much in advance for the help

Edit: To clarify, I'm looking for a way of generating a set of coordinates that, when joined up, form the outline of a line

Jacob Barrow
  • 631
  • 1
  • 8
  • 25

2 Answers2

1

If all you are looking for is to draw an outline...
One strategy that I've used in the past is just to spin around the shape.
We do not get a polygon like what you show on your image, here is sample:

let s = 20; // thickness scale
let x = 25, y = 25; // final position

let shape = new Path2D();
shape.lineTo(0, 0);
shape.lineTo(50, 50);
shape.lineTo(80, 50);
shape.lineTo(120, 12);

var ctx = document.getElementById("canvas1").getContext("2d");

ctx.strokeStyle = "black";
ctx.lineWidth = 3;
ctx.translate(x, y);

for (i = 0; i < 360; i++) {
  ctx.save();
  ctx.translate(Math.sin(i * Math.PI / 180) * s, Math.cos(i * Math.PI / 180) * s);
  ctx.stroke(shape);
  ctx.restore();
}

ctx.beginPath();
ctx.strokeStyle = "red";
ctx.stroke(shape);
<canvas id="canvas1" width="180" height="120"></canvas>

But that same logic can be used in more complex shapes like an image
Here is that applied to an image:

var s = 20, // thickness scale
  x = 25, // final position
  y = 25;

var ctx1 = document.getElementById('canvas1').getContext('2d'),
  img1 = new Image;

img1.onload = draw1;
img1.src = "https://i.stack.imgur.com/UFBxY.png";

function draw1() {
  ctx1.globalAlpha = 0.01
  for (i = 0; i < 360; i++)
    ctx1.drawImage(img1, x + Math.sin(i * Math.PI / 180) * s, y + Math.cos(i * Math.PI / 180) * s);
  ctx1.globalAlpha = 1
  ctx1.drawImage(img1, x, y);
}
<canvas id="canvas1" width=350 height=500></canvas>
Helder Sepulveda
  • 15,500
  • 4
  • 29
  • 56
  • I appreciate your answer but it doesn't quite apply - I'm looking to generate a set of coordinates that can be used to draw the outline, rather than finding another way of drawing it - I've added some more detail to the question – Jacob Barrow Dec 12 '21 at 11:10
1

I finally cracked it! Depending on whether a point's y coord is bigger than it's predecessor, the offset needs to be flipped. Here's the code I changed from my example:

outline_points = [] // Stores the outline
reverse_outline_points = [] // Stores the opposite of the outline
let a_offset_point, b_offset_point;
for (i=0; i<path.length-1; i++) {
  let mid_point = path[i]  
  let end_point = path[i+1]
  
  let offset = OFFSET
  if(end_point.y >= mid_point.y) {
    offset = -OFFSET
  }
  outline_points.push(mid_point.getOffsetPoint(end_point, 'blue', offset))
  outline_points.push(end_point.getOffsetPoint(mid_point, 'blue', offset))
  
  reverse_outline_points.push(mid_point.getOffsetPoint(end_point, 'blue', -offset))
  reverse_outline_points.push(end_point.getOffsetPoint(mid_point, 'blue', -offset))
  
}

This also calculates the complement of the offset, which drawn in reverse gives both sides of the outline

Jacob Barrow
  • 631
  • 1
  • 8
  • 25