Zakładając, że są tylko 4 punkty, które tworzą kwadrat i znamy normalną:
const EPSILON = 0.0000001;
let points = [
{x: -0.5, y: 0.3535533845424652, z: -0.3535533845424652},
{x: 0.5, y: 0.3535533845424652, z: -0.3535533845424652},
{x: -0.5, y: -0.3535533845424652, z: 0.3535533845424652},
{x: 0.5, y: -0.3535533845424652, z: 0.3535533845424652},
];
const normal = {x: 0, y: 0.7071067811865476, z: 0.7071067811865476};
Przyda się kilka funkcji pomocniczych: liczenie odległości między punktami, sprawdzanie czy wektory są skierowane w tę samą stronę i cross product:
function distance(point_a, point_b) {
return Math.hypot(point_a.x-point_b.x, point_a.y-point_b.y, point_a.z-point_b.z);
}
function same_direction(v1, v2) {
let len1 = Math.hypot(v1.x, v1.y, v1.z);
let len2 = Math.hypot(v2.x, v2.y, v2.z);
let normalized_v1 = {x: v1.x / len1, y: v1.y / len1, z: v1.z / len1};
let normalized_v2 = {x: v2.x / len2, y: v2.y / len2, z: v2.z / len2};
return Math.hypot(
normalized_v1.x - normalized_v2.x, normalized_v1.y - normalized_v2.y,
normalized_v1.z - normalized_v2.z
) < EPSILON;
}
function cross_product(v1, v2) {
let x = v1.y * v2.z - v1.z * v2.y;
let y = v1.z * v2.x - v1.x * v2.z;
let z = v1.x * v2.y - v1.y * v2.x;
return {x, y, z};
}
Załózmy że chcemy znaleźć takie punkty a, b, c, d, ze one są posortowane zgodnie z ruchem wskazówek zegara. Za a możemy wziać dowolny punkt. Posortujemy pozostałem punkty względem odległości do a. Oczywiście najdalszy punkt będzie punktem c.
let a = points[0];
points.sort((point_a, point_b) => distance(a, point_a) - distance(a, point_b));
let c = points[3], b, d;
Pozostało znaleźć który to b i d. W tym celu liczymy wektory c->points[1] (bok kwadratu), c->points[2] (bok kwadratu) i c->a (przekątna kwadratu). Następnie liczymy cross product pierwszego z policzonych wcześniej wektorów z trzecim i drugiego z trzecim. Jeden z tych wektorów będzie miał ten sam kierunek co normalna. To jest szukane b.
let cp1 = {x: points[1].x - c.x, y: points[1].y - c.y, z: points[1].z - c.z}; // wektor c -> p1
let cp2 = {x: points[2].x - c.x, y: points[2].y - c.y, z: points[2].z - c.z}; // wektor c -> p2
let ca = {x: a.x - c.x, y: a.y - c.y, z: a.z - c.z}; // wektor c -> a
let cr1 = cross_product(ca, cp1);
let cr2 = cross_product(ca, cp2);
if(same_direction(normal, cr1)) {
b = points[1];
d = points[2];
}
else if (same_direction(normal, cr2)) {
b = points[2];
d = points[1];
}
else {
console.log("ERROR");
}
console.log(a, b, c, d);
Otrzymaliśmy szukane punkty. Nie piszę normalnie w JS, więc nie wiem jak on sobie radzi z błedami w arytmetyce zmiennoprzecinkowej. Dlatego dałem epsilona żeby temu zaradzić. Trzeba go jakoś odpowiednio dobrać.