Определить все точки пересечения для двух трехмерных (копланарных) треугольников

Question

Я пытаюсь определить все точки, где пересекаются два трехмерных, но копланарных треугольника. Я нашел методы, которые определяют, пересекаются ли треугольники, но мне действительно нужны фактические точки пересечения. Ниже я показал несколько случаев этой ситуации. Кроме того, я буду кодировать это на Java, но я уверен, что смогу преобразовать другой язык, пока я понимаю математику!

Я знаю все вершины, но это все! Отредактировано для пояснений.

Спасибо, Майкл

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

Answer 1

1. , если вы не имеете уравнение плоскости вам нужно вычислить.

2. игнорировать ось Z на данный момент (если это не делает все ваши очки падают на ту же линию, и в этом случае игнорировать другую ось :)

3. найти пересечения для каждого ребра первого треугольника и каждое ребро другой треугольник

4. плагин пересечениями обратно в уравнение вашего самолета, чтобы восстановить г

---

для шага 3: от line line intersection wikipedia article

отбрасывать все перекрестки, которые не попадают на обоих краях

---

вот JS сниппет, который делает шаг 3

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); 
 
}