Lot's of G0 moves in GCODE

[casperlamboo]

When combing is turned on there are some times a lot of unneeded G0 moves.

With combing turned ON

With combing turned OFF

[casperlamboo]

I have thought of an alternate approach to combing that may work better for us.

First we split the concave shape into convex shapes (if the shape is already convex we can just move to the other location because you can always draw a straight line between two points in a convex shape without the line crossing any edges). After we have split the shape into convex shapes we check in which shape the start point is and in which shape the end point. If they are both in the same shape we can just move. If they are in different shapes we first move to the closest convex edge point then we until we have moved in to the end points shape.

[casperlamboo]

Found a lib that can split concave polygons in to convex polygons (minimum convex decomposition) https://www.npmjs.com/package/poly-decomp (no support for holes)
https://github.com/mikolalysenko/rectangle-decomposition (splits shapes into rectangles?)

paper on the subject https://www.sciencedirect.com/science/article/pii/S0925772105001008
http://openaccess.thecvf.com/content_cvpr_2014/papers/Liu_Dual-Space_Decomposition_of_2014_CVPR_paper.pdf

[casperlamboo]

I've gotten some good results with this approach. Doesn't work 100% yet but it is promising.

import earcut from 'earcut';

const subtract = (a, b) => ({
  x: a.x - b.x,
  y: a.y - b.y
});
const add = (a, b) => ({
  x: a.x + b.x,
  y: a.y + b.y
});
const scale = (v, factor) => ({
  x: v.x * factor,
  y: v.y * factor
});
const divide = (v, factor) => ({
  x: v.x / factor,
  y: v.y / factor
});
const normal = (v) => ({
  x: -v.y,
  y: v.x
});
const equals = (a, b) => a.x === b.x && a.y === b.y;
const almostEquals = (a, b) => Math.abs(a.x - b.x) < 0.001 && Math.abs(a.y - b.y) < 0.001;
const dot = (a, b) => a.x * b.x + a.y * b.y;
const length = (v) => Math.sqrt(v.x * v.x + v.y * v.y);
const distanceToSquared = (a, b) => ((b.x - a.x) ** 2) + ((b.y - a.y) ** 2);
const distanceTo = (a, b) => Math.sqrt(distanceToSquared(a, b));
const normalize = (v) => {
  const l = length(v);

  return {
    x: v.x / l,
    y: v.y / l
  };
};
const lineIntersection = (a1, a2, b1, b2) => {
  // source: http://mathworld.wolfram.com/Line-LineIntersection.html
  const intersection = {
    x: ((a1.x * a2.y - a1.y * a2.x) * (b1.x - b2.x) - (a1.x - a2.x) * (b1.x * b2.y - b1.y * b2.x)) / ((a1.x - a2.x) * (b1.y - b2.y) - (a1.y - a2.y) * (b1.x - b2.x)),
    y: ((a1.x * a2.y - a1.y * a2.x) * (b1.y - b2.y) - (a1.y - a2.y) * (b1.x * b2.y - b1.y * b2.x)) / ((a1.x - a2.x) * (b1.y - b2.y) - (a1.y - a2.y) * (b1.x - b2.x))
  };

  const intersectionA = subtract(intersection, a1);
  const directionA = subtract(a2, a1);
  const normalA = normalize(directionA);
  const distanceA = dot(normalA, intersectionA);
  if (distanceA < 0 || distanceA > dot(normalA, directionA)) return false;

  const intersectionB = subtract(intersection, b1);
  const directionB = subtract(b2, b1);
  const normalB = normalize(directionB);
  const distanceB = dot(normalB, intersectionB);
  if (distanceB < 0 || distanceB > dot(normalB, directionB)) return false;

  return intersection;
};


const START = { x: 560, y: 40 };
const END = { x: 550, y: 570 };
const CONCAVE_POLYGON = [[
  { x: 10, y: 10 },
  { x: 600, y: 10 },
  { x: 500, y: 200 },
  { x: 600, y: 600 },
  { x: 10, y: 600 }
], [
  { x: 160, y: 120 },
  { x: 120, y: 400 },
  { x: 400, y: 400 }
]];

function pointIsInsideConvex(point, convex, vertices) {
  for (let i = 0; i < convex.length; i ++) {
    const vertexA = vertices[convex[i]];
    const vertexB = vertices[convex[(i + 1) % convex.length]];

    const n = normalize(normal(subtract(vertexB, vertexA)));
    const p = subtract(point, vertexA);

    if (dot(p, n) < 0) return false;
  }
  return true;
}

function decompose(polygon) {
  const vertices = polygon
    .reduce((points, path) => {
      points.push(...path);
      return points;
    }, []);

  const flatVertices = vertices
    .reduce((points, { x, y }) => {
      points.push(x, y);
      return points;
    }, []);

  let length = 0;
  const holes = polygon
    .map(path => length += path.length)
    .slice(0, polygon.length - 1);

  const flatTrainglesIndexed = earcut(flatVertices, holes);
  const convexPolygons = [];
  for (let i = 0; i < flatTrainglesIndexed.length; i += 3) {
    const face = [
      flatTrainglesIndexed[i],
      flatTrainglesIndexed[i + 1],
      flatTrainglesIndexed[i + 2]
    ];
    const center = divide(face.reduce((total, point) => {
      if (!total) {
        return vertices[point];
      } else {
        return add(total, vertices[point]);
      }
    }, null), face.length);
    convexPolygons.push({
      center,
      face,
      connects: []
    });
  }

  for (let i = 0; i < convexPolygons.length; i ++) {
    for (let j = i + 1; j < convexPolygons.length; j ++) {
      const triangleIndexedA = convexPolygons[i];
      const triangleIndexedB = convexPolygons[j];

      const overlap = [];
      triangleIndexedA.face.map(index => {
        if (triangleIndexedB.face.includes(index)) overlap.push(index);
      });

      if (overlap.length === 2) {
        const distance = distanceTo(convexPolygons[i].center, convexPolygons[j].center);
        triangleIndexedA.connects.push({ to: j, edge: overlap, distance });
        triangleIndexedB.connects.push({ to: i, edge: overlap, distance });
      }
    }
  }

  return { vertices, convexPolygons };
}

function findClosestPath(convexPolygons, start, end, done = [], path = []) {
  if (start === end) return [];

  done = [...done, start];

  const { connects } = convexPolygons[start];

  const finish = connects.find(({ to }) => to === end);
  if (finish) return [...path, finish];

  const posibilities = [];
  for (const connect of connects) {
    if (!done.includes(connect.to)) {
      const p = findClosestPath(convexPolygons, connect.to, end, done, [...path, connect]);
      if (p) posibilities.push(p);
    }
  }

  if (posibilities.length === 0) {
    return null;
  } else if (posibilities.length === 1) {
    return posibilities[0];
  } else if (posibilities.length > 1) {
    const distanceMap = new WeakMap();
    for (const posibility of posibilities) {
      const distance = posibility.reduce((totalDistance, connect) => totalDistance + connect.distance, 0);
      distanceMap.set(posibility, distance);
    }

    return posibilities.sort((a, b) => distanceMap.get(a) - distanceMap.get(b))[0];
  }
}

function containLineInPath(path, start, end, vertices) {
  const line = [start];

  for (const { edge: [indexA, indexB] } of path) {
    const vertexA = vertices[indexA];
    const vertexB = vertices[indexB];

    const intersection = lineIntersection(start, end, vertexA, vertexB);
    if (!intersection) {
      const lastPoint = line[line.length - 1];
      const distanceA = distanceTo(lastPoint, vertexA) + distanceTo(vertexA, end);
      const distanceB = distanceTo(lastPoint, vertexB) + distanceTo(vertexB, end);

      line.push(distanceA < distanceB ? vertexA : vertexB);
    }
  }

  line.push(end);
  return line;
}

const { convexPolygons, vertices } = decompose(CONCAVE_POLYGON);
const startPolygon = convexPolygons.findIndex(({ face }) => pointIsInsideConvex(START, face, vertices));
const endPolygon = convexPolygons.findIndex(({ face }) => pointIsInsideConvex(END, face, vertices));
const path = findClosestPath(convexPolygons, startPolygon, endPolygon);
const line = containLineInPath(path, START, END, vertices);

// draw
const canvas = document.createElement('canvas');
document.body.appendChild(canvas);
canvas.width = 610;
canvas.height = 610;
const context = canvas.getContext('2d');

context.beginPath();
for (const shape of CONCAVE_POLYGON) {
  let first = true;
  for (const { x, y } of shape) {
    if (first) {
      context.moveTo(x, y);
    } else {
      context.lineTo(x, y);
    }
    first = false;
  }
}
context.closePath();
context.fillStyle = 'rgba(0, 0, 0, 0.5)';
context.fill();

context.fillStyle = 'black';
context.strokeStyle = 'black';
context.textAlign = 'center';
context.textBaseline = 'middle';
context.font = '14px arial';
for (let i = 0; i < convexPolygons.length; i ++) {
  const { face, center } = convexPolygons[i];

  context.beginPath();
  for (const index of face) {
    const vertex = vertices[index];
    context.lineTo(vertex.x, vertex.y);
  }
  context.closePath();
  context.stroke();

  context.fillText(i, center.x, center.y);
}

context.beginPath();
for (const { edge: [indexA, indexB] } of path) {
  const pointA = vertices[indexA];
  const pointB = vertices[indexB];
  context.moveTo(pointA.x, pointA.y);
  context.lineTo(pointB.x, pointB.y);
}
context.strokeStyle = 'blue';
context.lineWidth = 3;
context.stroke();

context.beginPath();
for (const point of line) {
  context.lineTo(point.x, point.y);
}
context.strokeStyle = 'green';
context.lineWidth = 2;
context.stroke();

context.beginPath();
context.arc(START.x, START.y, 3, 0, Math.PI * 2);
context.fillStyle = 'blue';
context.fill();

context.beginPath();
context.arc(END.x, END.y, 3, 0, Math.PI * 2);
context.fillStyle = 'red';
context.fill();

[casperlamboo]

I've written an alternate aproach that can be seen here

https://codepen.io/casperlamboo/pen/RyEJRw