JS对角线碰撞检测：随机无重叠连线程序开发问询

一、修复原代码的基础Bug #

你的代码存在两处关键错误，会导致线段属性计算失效：

• 斜率计算时缺少括号，正确的斜率公式应为 (终点Y - 起点Y) / (终点X - 起点X)，需注意处理**垂直直线（分母为0）**的情况，避免生成NaN。
• lineDistance 和 slope 错误地固定使用 players[0] 的数据，应改为当前循环的 players[i]。

修复后的属性计算代码：

players[i].lineDistance = Math.sqrt(
  Math.pow(players[i].endPathX - players[i].beginPathX, 2) +
  Math.pow(players[i].endPathY - players[i].beginPathY, 2)
);
// 处理垂直直线，用Infinity表示斜率
players[i].slope = players[i].endPathX === players[i].beginPathX 
  ? Infinity 
  : (players[i].endPathY - players[i].beginPathY) / (players[i].endPathX - players[i].beginPathX);

二、实现线段相交检测（含对角线） #

线段相交检测的核心是跨立实验（Orientation算法），可准确判断两条线段是否相交（包括端点接触、共线重叠的情况）。

1. 辅助函数：计算三点方向

该函数返回三个点的相对方向，用于判断线段是否跨立：

// 返回值：
// 0：三点共线
// 1：逆时针方向
// 2：顺时针方向
function orientation(p1, p2, p3) {
  const val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
  if (val === 0) return 0;
  return val > 0 ? 1 : 2;
}

2. 核心函数：判断两条线段是否相交

包含共线线段的重叠判断，确保生成的线段完全无重叠：

function doSegmentsIntersect(seg1, seg2) {
  // 转换为点对象方便处理
  const p1 = {x: seg1.beginPathX, y: seg1.beginPathY};
  const q1 = {x: seg1.endPathX, y: seg1.endPathY};
  const p2 = {x: seg2.beginPathX, y: seg2.beginPathY};
  const q2 = {x: seg2.endPathX, y: seg2.endPathY};

  const o1 = orientation(p1, q1, p2);
  const o2 = orientation(p1, q1, q2);
  const o3 = orientation(p2, q2, p1);
  const o4 = orientation(p2, q2, q1);

  // 一般情况：两条线段互相跨立
  if (o1 !== o2 && o3 !== o4) return true;

  // 特殊情况：共线且端点重叠/线段重叠
  // p2在p1q1上
  if (o1 === 0 && isPointOnSegment(p1, p2, q1)) return true;
  // q2在p1q1上
  if (o2 === 0 && isPointOnSegment(p1, q2, q1)) return true;
  // p1在p2q2上
  if (o3 === 0 && isPointOnSegment(p2, p1, q2)) return true;
  // q1在p2q2上
  if (o4 === 0 && isPointOnSegment(p2, q1, q2)) return true;

  return false;
}

// 判断点q是否在线段pr上
function isPointOnSegment(p, q, r) {
  return q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) &&
         q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y);
}

三、整合到生成逻辑中 #

生成新线段时，先与所有已存在的线段检测是否相交，仅当不相交时才加入数组：

// 生成随机线段的示例函数
function generateRandomSegment() {
  const beginX = Math.random() * canvas.width;
  const beginY = Math.random() * canvas.height;
  const endX = Math.random() * canvas.width;
  const endY = Math.random() * canvas.height;
  return new Player(beginX, beginY, endX, endY);
}

// 添加无重叠线段
function addNonOverlappingSegment() {
  let newSeg;
  let isOverlapping;
  // 循环生成直到找到不相交的线段
  do {
    newSeg = generateRandomSegment();
    isOverlapping = players.some(seg => doSegmentsIntersect(seg, newSeg));
  } while (isOverlapping);
  
  players.push(newSeg);
  // 重新绘制所有线段
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  testLine();
}

四、完整修改后的代码 #

let players = [];
const canvas = document.getElementById("yourCanvasId"); // 替换为你的canvas元素ID
const ctx = canvas.getContext("2d");

function Player(beginPathX, beginPathY, endPathX, endPathY, lineDistance, slope) {
  this.beginPathX = beginPathX;
  this.beginPathY = beginPathY;
  this.endPathX = endPathX;
  this.endPathY = endPathY;
  this.lineDistance = lineDistance || 0;
  this.slope = slope || 0;
}

// 初始化一条线段
players.push(new Player(100, 100, 200, 200, 0, 0));

function testLine() {
  for (let i = 0; i < players.length; i++) {
    ctx.beginPath();
    ctx.moveTo(players[i].beginPathX, players[i].beginPathY);
    ctx.lineTo(players[i].endPathX, players[i].endPathY);
    ctx.stroke();
    // 修复线段长度计算
    players[i].lineDistance = Math.sqrt(
      Math.pow(players[i].endPathX - players[i].beginPathX, 2) +
      Math.pow(players[i].endPathY - players[i].beginPathY, 2)
    );
    // 修复斜率计算，处理垂直直线
    players[i].slope = players[i].endPathX === players[i].beginPathX 
      ? Infinity 
      : (players[i].endPathY - players[i].beginPathY) / (players[i].endPathX - players[i].beginPathX);
  }
}

// 辅助函数：计算三点方向
function orientation(p1, p2, p3) {
  const val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
  if (val === 0) return 0;
  return val > 0 ? 1 : 2;
}

// 判断点q是否在线段pr上
function isPointOnSegment(p, q, r) {
  return q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) &&
         q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y);
}

// 判断两条线段是否相交
function doSegmentsIntersect(seg1, seg2) {
  const p1 = {x: seg1.beginPathX, y: seg1.beginPathY};
  const q1 = {x: seg1.endPathX, y: seg1.endPathY};
  const p2 = {x: seg2.beginPathX, y: seg2.beginPathY};
  const q2 = {x: seg2.endPathX, y: seg2.endPathY};

  const o1 = orientation(p1, q1, p2);
  const o2 = orientation(p1, q1, q2);
  const o3 = orientation(p2, q2, p1);
  const o4 = orientation(p2, q2, q1);

  if (o1 !== o2 && o3 !== o4) return true;

  if (o1 === 0 && isPointOnSegment(p1, p2, q1)) return true;
  if (o2 === 0 && isPointOnSegment(p1, q2, q1)) return true;
  if (o3 === 0 && isPointOnSegment(p2, p1, q2)) return true;
  if (o4 === 0 && isPointOnSegment(p2, q1, q2)) return true;

  return false;
}

// 生成随机线段
function generateRandomSegment() {
  const beginX = Math.random() * canvas.width;
  const beginY = Math.random() * canvas.height;
  const endX = Math.random() * canvas.width;
  const endY = Math.random() * canvas.height;
  return new Player(beginX, beginY, endX, endY);
}

// 添加无重叠线段
function addNonOverlappingSegment() {
  let newSeg;
  let isOverlapping;
  do {
    newSeg = generateRandomSegment();
    isOverlapping = players.some(seg => doSegmentsIntersect(seg, newSeg));
  } while (isOverlapping);
  
  players.push(newSeg);
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  testLine();
}

// 初始化绘制
testLine();

内容的提问来源于stack exchange，提问作者gabe ramos