[Внешняя графика] Как определить, есть ли у пути пересечение

Canvas

В приложениях визуализации мы часто сталкиваемся с необходимостью определить, пересекается ли путь. В зависимости от того, пересекается путь или нет, можно определить, является ли многоугольник простым многоугольником, есть ли пересечение на маршруте движения и так далее.

Пути, которые не пересекаются (слева) и пути, которые пересекаются (справа)

На самом деле проблема заключается в том, чтобы определить, пересекаются ли два отрезка прямой. Поскольку путь состоит из сегментов линии, нам нужно только судить о том, что нет других сегментов линии, которые пересекают друг друга, кроме смежных сегментов линии.JS-код выглядит следующим образом:

function isPathIntersection(points) {
  const len = points.length;

  for(let i = 0; i < len - 1; i++) {
    const point = points[i];
    const nextPoint = points[i + 1];

    for(let j = 0; j < len - 1; j++) {
      const p1 = points[j],
        p2 = points[j + 1];

      if(p1 !== point && p2 !== point && p1 !== nextPoint && p2 !== nextPoint
        && isCross(p1, p2, point, nextPoint) && isCross(point, nextPoint, p1, p2)) {
        return true;
      }
    }
  }
  return false;
}

Приведенный выше код на самом деле использует два цикла для обхода каждого сегмента линии в пути, чтобы определить, пересекаются ли два сегмента линии, и логика оценки реализована в функции isCross.

Так как же реализовать функцию isCross? Давайте проанализируем это.

Как показано на рисунке ниже, вектор (p3, p4) пересекает прямую, на которой расположен вектор (p1, p2), затем вектор (p1, p3) (обозначается как A) и вектор (p3, p2) ( обозначаемые как B) находятся в векторе (p3, p4) (обозначаемом как C) с обеих сторон, то знаки CXB и CXA должны быть противоположными, то есть цифра слева. Обратно, если вектор (p3, p4) не пересекает прямую, на которой расположен вектор (p1, p2), то вектор (p1, p3) (обозначается как A) и вектор (p3, p2) (обозначается как B) находятся в векторе (p3), p4) (обозначается как C) с одной стороны, то есть CXB и CXA имеют одинаковый знак.

Итак, по этому принципу мы можем реализовать функцию isCross следующим образом:

function isCross(p1, p2, p3, p4) {
  const v1 = subtract([], p4, p3);
  const v2 = subtract([], p1, p3);
  const v3 = subtract([], p2, p3);

  const z1 = cross(v1, v2);
  const z2 = cross(v1, v3);

  return z1 * z2 <= 0;
}

где вычитание — вычитание векторов, а крест — векторное произведение векторов.

Так почему же isCross проверяется дважды в isPathIntersection?

isCross(p1, p2, point, nextPoint) && isCross(point, nextPoint, p1, p2)

Это связано с тем, что пересечение отрезков линии A (p1, p2) и B (p3, p4) должно удовлетворять обоим требованиям: A находится по обе стороны от линии, где находится B, и B находится по обе стороны от линии, где находится A. .

Например, в случае с приведенным выше рисунком isCross(p1, p2, p3, p4) истинно, но isCross(p3, p4, p1, p2) ложно, и два отрезка линии не пересекаются.

Итак, таким образом мы добились всех функций, и полный код не сложный, а именно:

import {subtract, cross} from '../common/lib/math/functions/Vec2Func.js';

function isCross(p1, p2, p3, p4) {
  const v1 = subtract([], p4, p3);
  const v2 = subtract([], p1, p3);
  const v3 = subtract([], p2, p3);

  const z1 = cross(v1, v2);
  const z2 = cross(v1, v3);

  return z1 * z2 <= 0;
}

function isPathIntersection(points) {
  const len = points.length;

  for(let i = 0; i < len - 1; i++) {
    const point = points[i];
    const nextPoint = points[i + 1];

    for(let j = 0; j < len - 1; j++) {
      const p1 = points[j],
        p2 = points[j + 1];

      if(p1 !== point && p2 !== point && p1 !== nextPoint && p2 !== nextPoint
        && isCross(p1, p2, point, nextPoint) && isCross(point, nextPoint, p1, p2)) {
        return true;
      }
    }
  }
  return false;
}

function draw(context, points) {
  context.clearRect(0, 0, context.canvas.width, context.canvas.height);
  const d = `M${points.join('L')}`;
  const color = isPathIntersection(points) ? 'red' : 'blue';
  context.strokeStyle = color;
  const path = new Path2D(d);
  context.stroke(path);
}

const canvas = document.querySelector('canvas');
const ctx = canvas.getContext('2d');
ctx.lineWidth = 5;
ctx.lineJoin = 'round';
ctx.lineCap = 'round';
const points = [];

canvas.addEventListener('click', (evt) => {
  const {x, y} = evt;
  const {x: x0, y: y0} = evt.target.getBoundingClientRect();
  points.push([x - x0, y - y0]);
  draw(ctx, points);
});

canvas.addEventListener('dblclick', (evt) => {
  points.length = 0;
  draw(ctx, points);
});

Окончательный эффект выглядит следующим образом:

Адрес онлайн-демонстрации:Akira-talent.GitHub.IO/graphics/m…

Категории