时间戳

首页 > 解决方案 > 两条线的交点，一种情况有效，另一种情况无效

javascript - 两条线的交点，一种情况有效，另一种情况无效

问题描述

我有这个代码https://codepen.io/octaviandd/pen/dyoaJVZ?editors=0010

基本上是一个多边形和一条线，当我移动鼠标并穿过整个多边形时，我需要找到线和多边形线之间的交点（就在多边形的左侧和右侧）。我对左侧和右侧使用相同的算法，左侧有效，右侧无效。

左边 ：

if (
    (positions.a1x === positions.a2x && positions.a1y === positions.a2y) ||
    (points[0].x === points[6].x && points[0].y === points[6].y)
  ) {
    return false;
  }

  let denominator =
    (points[6].y - points[0].y) * (positions.a2x - positions.a1x) -
    (points[6].x - points[0].x) * (positions.a2y - positions.a1y);

  if (denominator === 0) {
    return false;
  }

  let ua =
    ((points[6].x - points[0].x) * (positions.a1y - points[0].y) -
      (points[6].y - points[0].y) * (positions.a1x - points[0].x)) /
    denominator;
  let ub =
    ((positions.a2x - positions.a1x) * (positions.a1y - points[0].y) -
      (positions.a2y - positions.a1y) * (positions.a1x - points[0].x)) /
    denominator;

  if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {
    return false;
  }

  let x = positions.a1x + ua * (positions.a2x - positions.a1x);
  let y = positions.a1y + ua * (positions.a2y - positions.a1y);

右边：

if (
    (positions.a1x === positions.a2x && positions.a1y === positions.a2y) ||
    (points[2].x === points[3].x && points[2].y === points[3].y)
  ) {
    return false;
  }

  let denominator2 =
    (points[3].y - points[2].y) * (positions.a2x - positions.a1x) -
    (points[3].x - points[2].x) * (positions.a2y - positions.a1y);

  if (denominator2 === 0) {
    return false;
  }

  let ua2 =
    ((points[3].x - points[2].x) * (positions.a1y - points[2].y) -
      (points[3].y - points[2].y) * (positions.a1x - points[2].x)) /
    denominator;
  let ub2 =
    ((positions.a2x - positions.a1x) * (positions.a1y - points[2].y) -
      (positions.a2y - positions.a1y) * (positions.a1x - points[2].x)) /
    denominator;

  if (ua2 < 0 || ua2 > 1 || ub2 < 0 || ub2 > 1) {
    return false;
  }

  let x2 = positions.a1x + ua2 * (positions.a2x - positions.a1x);
  let y2 = positions.a1y + ua2 * (positions.a2y - positions.a1y);

如果我从左到右穿过多边形，碰撞点似乎向内，如果我从右到左，碰撞点似乎向外；如果我的线来自左侧并靠近右侧但没有碰到它，算法仍然会以某种方式找到假碰撞。

多边形的初始坐标：

    const points = [
      { x: 100, y: 100 },
      { x: 200, y: 50 },
      { x: 300, y: 50 },
      { x: 400, y: 200 },
      { x: 350, y: 250 },
      { x: 200, y: 300 },
      { x: 150, y: 300 }
    ];

有什么帮助吗？

标签： javascriptalgorithmsvggraphpolygon

解决方案

我一直在寻找完全相同的问题，直到我最终为这些问题编写了自己的一套解决方案：

请注意，您可能需要调整 epsilon 值，因为我已将其设置为 1，因为一个像素已经太小了。

我不能保证这是计算效率方面的最佳方式，但可以肯定的是，对于所有情况，它们对于每个零的任何除法都是安全且稳健的，因为我在任何导致除法的操作之前执行 epsilon 检查.

你可以在这个演示中看到整个东西在现场运行，我用它来绘制一个图形，我需要找到边缘的箭头会接触到顶点标签框的位置。 https://networkgraphs.github.io/graphysics/

推荐阅读