确定两个 3D（共面）三角形的所有交点

Question

我正在尝试确定两个共面的 3D 三角形相交的所有点。我找到了检测三角形是否相交的方法，但我真正需要的是相交发生的实际点。下面我展示了这种情况的几个案例。此外，我将在 Java 中对此进行编码，但我相信只要我理解数学，我就可以转换另一种语言！

我知道所有的顶点，仅此而已！编辑澄清。

谢谢，迈克尔

https://www.dropbox.com/s/yoszrlfqbx3usrf/cases.png?dl=0

Answer 1

如果您没有飞机的方程式，则需要计算它。
暂时忽略 z 轴（除非这会让你所有的点都落在同一条线上，在这种情况下忽略另一个轴:)
找到第一个三角形的每条边和另一个三角形的每条边的交点
将交叉点重新插入平面方程以恢复 z

第 3 步：来自 line line intersection wikipedia article

丢弃不落在两条边上的任何交叉点

这是执行第 3 步的 js 片段

var a;
var b;
var bs = document.body.style;
var ds = document.documentElement.style;
bs.height = bs.width = ds.height = ds.width = "100%";
bs.border = bs.margin = bs.padding = 0;
var c = document.createElement("canvas");
c.style.display = "block";
c.addEventListener("mousedown", randomize, false);
c.addEventListener("mousemove", follow, false);
document.body.appendChild(c);
var ctx = c.getContext("2d");
window.addEventListener("resize", redraw);
randomize();

function randomPoint() {
  return {x:Math.random() * window.innerWidth, 
          y: Math.random() * window.innerHeight};
}
function randomize(e) {
  a = [];
  b = [];
  for (var i = 0; i < 3; i++) {
    a[i] = randomPoint();
    b[i] = randomPoint();
  }
  redraw();
}
function follow(e) {
  var average = {x:0, y:0};
  for (var i = 0; i < 3; i++) {
    average.x += a[i].x / 3;
    average.y += a[i].y / 3;
  }
  for (var i = 0; i < 3; i++) {
    a[i].x += e.clientX - average.x;
    a[i].y += e.clientY - average.y;
  }
  redraw();
}
function drawPoint(p, color) {
  ctx.strokeStyle = color;
  ctx.beginPath();
  ctx.arc(p.x, p.y, 10, 0, 2 * Math.PI, true);
  ctx.closePath();
  ctx.stroke();
}
function isPointOnLine(p, v1, v2) {
  if (v1.x === v2.x) 
    return (Math.max(v1.y, v2.y) >= p.y && Math.min(v1.y, v2.y) <= p.y)
  else 
    return (Math.max(v1.x, v2.x) >= p.x && Math.min(v1.x, v2.x) <= p.x)
}
function calculateIntersection(a1, a2, b1, b2) {
  var d = (a1.x - a2.x)*(b1.y - b2.y) -
      (a1.y - a2.y)*(b1.x - b2.x);
  if (!d) return null;
  return {
    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)) / d,
    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)) / d
  };
}
function drawIntersections(a, b) {
  a.forEach(function (a1, i) {
    var a2 = a[(i + 1) % a.length];
    b.forEach(function (b1, j) {
      var b2 = b[(j + 1) % b.length];
      var p = calculateIntersection(a1, a2, b1, b2);
      if(!p) return;
      if (isPointOnLine(p, a1, a2) && isPointOnLine(p, b1, b2)) 
        drawPoint(p, "red");
      else
        drawPoint(p, "yellow");
    });
  });
}
function drawShape(shape) {
  ctx.strokeStyle = "black";
  ctx.beginPath();
  ctx.moveTo(shape[0].x, shape[0].y);
  for (var i = 1; i <= shape.length; i++) {
    ctx.lineTo(shape[i % shape.length].x, shape[i % shape.length].y);
  }
  ctx.closePath();
  ctx.stroke();
}
function redraw() {
  c.width = window.innerWidth;
  c.height = window.innerHeight;
  ctx.clearRect(0, 0, c.width, c.height);
  ctx.fillStyle = "rgb(200, 200, 200)";
  ctx.font = "40px serif";
  ctx.fillText("click to randomize", 20, 40);
  drawShape(a);
  drawShape(b);
  drawIntersections(a, b);
}

确定两个 3D（共面）三角形的所有交点

Determine all points of intersection for two 3D (coplanar) triangles

java

2d

intersection