作为兼职项目，我正在研究一些几何实用程序，遇到了一个相对简单的问题，但似乎没有那么简单的解决方案。
问题涉及 EPSILON 对于该问题来说太小了。为了查看两个三 Angular 形是否相似，我以每个三 Angular 形的余弦形式计算 3 个内 Angular ，然后对它们进行排序。然后我测试 Math.abs(t1[0]-t2[0]) < EPSILON，其中 t1 是一个三 Angular 形，t2 是另一个三 Angular 形，每个三 Angular 形都包含三个 Angular 。
在我知道相似的三 Angular 形上，我得到大约 20% - 80% 的失败率。当我将 EPSILON 设置为一个更大的值时，例如仍然是一个非常小的 0.0000001 时，没有失败(好吧，在我让测试运行的时候)。
下面是提取的相关三 Angular 函数，我还在下面包含了测试代码作为演示。单击该按钮，它会运行测试并显示结果。三 Angular 形是随机生成的。每隔一段时间就会创建两个相似的三 Angular 形，其中大约一半是精确的副本，其余的是副本但缩放、镜像、旋转和打乱 vec 顺序，同时仍然保持相似性
我想知道如何计算一个合理的 EPSILON，以减少不正确的结果，同时保持系统尽可能准确？
虽然也有可能是测试代码有其他错误，我会继续检查。
const EPSILON = Number.EPSILON
function Triangle(p1,p2,p3){
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
}
Triangle.prototype.p1 = undefined;
Triangle.prototype.p2 = undefined;
Triangle.prototype.p3 = undefined;
Triangle.prototype.isSimilar = function(triangle){
var a1,b1,c1,a2,b2,c2,aa1,bb1,cc1,aa2,bb2,cc2; //
var t1 = [];
var t2 = [];
var sortF = function(a,b){ return a-b };
// get the length squared and length of each side
a1 = Math.sqrt(aa1 = Math.pow(this.p1.x - this.p2.x, 2) + Math.pow(this.p1.y - this.p2.y, 2));
b1 = Math.sqrt(bb1 = Math.pow(this.p2.x - this.p3.x, 2) + Math.pow(this.p2.y - this.p3.y, 2));
c1 = Math.sqrt(cc1 = Math.pow(this.p3.x - this.p1.x, 2) + Math.pow(this.p3.y - this.p1.y, 2));
a2 = Math.sqrt(aa2 = Math.pow(triangle.p1.x - triangle.p2.x, 2) + Math.pow(triangle.p1.y - triangle.p2.y, 2));
b2 = Math.sqrt(bb2 = Math.pow(triangle.p2.x - triangle.p3.x, 2) + Math.pow(triangle.p2.y - triangle.p3.y, 2));
c2 = Math.sqrt(cc2 = Math.pow(triangle.p3.x - triangle.p1.x, 2) + Math.pow(triangle.p3.y - triangle.p1.y, 2));
// get the cosin of each angle for both triangle
t1[0] = (cc1 - (aa1 + bb1)) / (-2 * a1 * b1);
t1[1] = (aa1 - (cc1 + bb1)) / (-2 * c1 * b1);
t1[2] = (bb1 - (cc1 + aa1)) / (-2 * c1 * a1);
t2[0] = (cc2 - (aa2 + bb2)) / (-2 * a2 * b2);
t2[1] = (aa2 - (cc2 + bb2)) / (-2 * c2 * b2);
t2[2] = (bb2 - (cc2 + aa2)) / (-2 * c2 * a2);
t1.sort(sortF);
t2.sort(sortF);
if(Math.abs(t1[0] - t2[0]) < EPSILON && Math.abs(t1[1] - t2[1]) < EPSILON && Math.abs(t1[2] - t2[2]) < EPSILON){
return true;
}
return false;
}
function Vec(x,y){
this.x = x;
this.y = y;
}
Vec.prototype.x = undefined;
Vec.prototype.y = undefined;
更新
更多信息。
使用 Angular 余弦 EPSILON 的相似三 Angular 形失败:2.220446049250313e-16
Failed Triangles ID : 94
Method : compare cosine of angles
Both Compare T1 to T2 and T2 to T1 failed
Both Triangles known to be similare
Triangle 1
p1.x = -149241116087155.97;
p1.y = -1510074922190599.8;
p2.x = -2065214078816255.8;
p2.y = 6756872141691895;
p3.x = -7125027429739231;
p3.y = -5622578541875555;
Triangle 2
p1.x = -307440480802857.2;
p1.y = -404929352172871.56;
p2.x = -3020163594243123;
p2.y = -355583557775981.75;
p3.x = 595422457974710.8;
p3.y = 2291176238828451.5;
Compare T1 to T2 Result : false
Computed values
Triangle 1 length of side and square length
length a : 8486068945686473 squared : 7.201336615094433e+31
length b : 13373575078230092 squared : 1.78852510373057e+32
length c : 8097794805726894 squared : 6.557428071565746e+31
Unsorted cosines C is angle opposite side c
cosine C : 0.8163410767815653
cosine A : 0.7960251614312384
cosine B : -0.30024590551189423
ratio a : undefined
ratio b : undefined
ratio c : undefined
Triangle2
length a : 2713171888697380.5 squared : 7.36130169761771e+30
length b : 4480825808030667.5 squared : 2.0077799921913682e+31
length c : 2843263414467020.5 squared : 8.08414684404666e+30
Unsorted cosines C is angle opposite side c
cosine C : 0.7960251614312384
cosine A : 0.8163410767815651
cosine B : -0.3002459055118942
Compare T2 to T1 Result : false
Triangle1
Computed values
Triangle 1 length of side and square length
length a : 2713171888697380.5 squared : 7.36130169761771e+30
length b : 4480825808030667.5 squared : 2.0077799921913682e+31
length c : 2843263414467020.5 squared : 8.08414684404666e+30
Unsorted cosines C is angle opposite side c
cosine a : 0.7960251614312384
cosine b : 0.8163410767815651
cosine c : -0.3002459055118942
ratio a : undefined
ratio b : undefined
ratio c : undefined
Triangle2
length a : 8486068945686473 squared : 7.201336615094433e+31
length b : 13373575078230092 squared : 1.78852510373057e+32
length c : 8097794805726894 squared : 6.557428071565746e+31
cosine a : 0.8163410767815653
cosine b : 0.7960251614312384
cosine c : -0.30024590551189423
更新 2
结果输出和 bug 修复(抱歉@lhf 我没有 sqrt epsilon 我还在使用原来的常量)
这显示了对同一组三 Angular 形的测试结果。不一致是指比较三 Angular 形 1 和三 Angular 形 2 的结果与比较三 Angular 形 2 和三 Angular 形 1 的结果不同。不正确是指两个已知的相似三 Angular 形失败，不正确不一致是指两个已知相似三 Angular 形未通过一个测试而通过另一个测试。
使用长度比率给出了最差的结果，但使用余弦并没有好多少，除了不正确的不一致相似三 Angular 形，在使用长度比率比较 t1 与 t2 和 t2 与 t1 之间具有非常高的不一致率。但这是有道理的，因为比率的大小会根据测试的顺序而有很大差异。
如您所见，使用 EPSILON 的平方根完全消除了两种方法的误差。
如果 lhf 希望将 sqrt(epsilon) 评论作为答案，我会接受它作为答案。感谢大家的投入，感谢 Salix，我有一些进一步的阅读
======================================
Default EPSILON : 2.220446049250313e-16
======================================
Via cosine of angles
All Inconsistency failed : 0 of 10000
Similar Incorrect failed : 1924 of 5032
Similar Incorrect Inconsistency failed : 0 of 5032
======================================
Via ratio of lengths
All Inconsistency failed : 1532 of 10000
Similar Incorrect failed : 2082 of 5032
Similar Incorrect Inconsistency failed : 1532 of 5032
======================================
Squaring EPSILON : 1.4901161193847656e-8
======================================
Via cosine of angles
All Inconsistency failed : 0 of 10000
Similar Incorrect failed : 0 of 5032
Similar Incorrect Inconsistency failed : 0 of 5032
======================================
Via ratio of lengths
All Inconsistency failed : 0 of 10000
Similar Incorrect failed : 0 of 5032
Similar Incorrect Inconsistency failed : 0 of 5032
const EPSILON = Number.EPSILON
function Triangle(p1,p2,p3){
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
}
Triangle.prototype.p1 = undefined;
Triangle.prototype.p2 = undefined;
Triangle.prototype.p3 = undefined;
Triangle.prototype.isSimilar = function(triangle){
var a1,b1,c1,a2,b2,c2,aa1,bb1,cc1,aa2,bb2,cc2; //
var t1 = [];
var t2 = [];
var sortF = function(a,b){ return a-b };
// get the length squared and length of each side
a1 = Math.sqrt(aa1 = Math.pow(this.p1.x - this.p2.x, 2) + Math.pow(this.p1.y - this.p2.y, 2));
b1 = Math.sqrt(bb1 = Math.pow(this.p2.x - this.p3.x, 2) + Math.pow(this.p2.y - this.p3.y, 2));
c1 = Math.sqrt(cc1 = Math.pow(this.p3.x - this.p1.x, 2) + Math.pow(this.p3.y - this.p1.y, 2));
a2 = Math.sqrt(aa2 = Math.pow(triangle.p1.x - triangle.p2.x, 2) + Math.pow(triangle.p1.y - triangle.p2.y, 2));
b2 = Math.sqrt(bb2 = Math.pow(triangle.p2.x - triangle.p3.x, 2) + Math.pow(triangle.p2.y - triangle.p3.y, 2));
c2 = Math.sqrt(cc2 = Math.pow(triangle.p3.x - triangle.p1.x, 2) + Math.pow(triangle.p3.y - triangle.p1.y, 2));
// get the cosin of each angle for both triangle
t1[0] = (cc1 - (aa1 + bb1)) / (-2 * a1 * b1);
t1[1] = (aa1 - (cc1 + bb1)) / (-2 * c1 * b1);
t1[2] = (bb1 - (cc1 + aa1)) / (-2 * c1 * a1);
t2[0] = (cc2 - (aa2 + bb2)) / (-2 * a2 * b2);
t2[1] = (aa2 - (cc2 + bb2)) / (-2 * c2 * b2);
t2[2] = (bb2 - (cc2 + aa2)) / (-2 * c2 * a2);
t1.sort(sortF);
t2.sort(sortF);
if(Math.abs(t1[0] - t2[0]) < EPSILON && Math.abs(t1[1] - t2[1]) < EPSILON && Math.abs(t1[2] - t2[2]) < EPSILON){
return true;
}
return false;
}
function Vec(x,y){
this.x = x;
this.y = y;
}
Vec.prototype.x = undefined;
Vec.prototype.y = undefined;
var iterations = 1000; // number of tests
var presentSimilar = 1/2; // odds of similar triangle
var presentSuperSimilar = 1/2; // odds of triangles being identical
var presentInfinity = 0;//1/20; // odds of a divide by zero
var presentDegenerate = 0;//1/100; // odds of a degenerate triangle can be colinear or degenerate right triangle
var v; // temp for swap
var xdx,xdy,ydx,ydy; // vars for rotation
var copyVec = [["p1","p2","p3"],["p2","p3","p1"],["p3","p1","p2"]]; // pick a vec for selecting vecs
// the triangles for testing;
var tri1 = new Triangle(new Vec(0,0), new Vec(0,0), new Vec(0,0));
var tri2 = new Triangle(new Vec(0,0), new Vec(0,0), new Vec(0,0));
// max Random
function rMax(){
return ((Math.random()*2)-1) * Number.MAX_SAFE_INTEGER;
}
// rotate function
function rotate(vec){
var x = vec.x;
var y = vec.y;
vec.x = x * xdx + y * ydx;
vec.y = x * xdy + y * ydy;
};
function translateVec(vec,x,y){
vec.x += x;
vec.y += y;
}
function translateTriangle(tri,x,y){
translateVec(tri.p1);
translateVec(tri.p2);
translateVec(tri.p3);
}
// make infinite vec to simulate the result of a divide by zero
function doInfinity(vec){
if(Math.random() < presentInfinity){
if(Math.random() < 0.5){
vec.x = Infinity;
vec.y = Infinity;
}else{
vec.x = -Infinity;
vec.y = -Infinity;
}
}
}
// create a random vector;
function randomVec(vec){
vec.x = rMax();
vec.y = rMax();
doInfinity(vec);
}
// create a random triangle
function randomTriangle(tri){
var p,r;
randomVec(tri.p1);
randomVec(tri.p2);
randomVec(tri.p3);
if(Math.random() < presentDegenerate){
r = Math.random();
if(r < 1/3){ // Degenerate right triangle
p = copyVec[Math.floor(Math.random()*3)]; // get two vec to be at the same location
tri[p[0]].x = tri[p[1]].x;
tri[p[0]].y = tri[p[1]].y;
}else // Degenerate colinear triangle
if(r < 2/3){
p = copyVec[Math.floor(Math.random()*3)]; // get two vec to be at the same location
r = Math.random();
tri[p[0]].x = (tri[p[1]].x - tri[p[2]].x) * r + tri[p[2]].x;
tri[p[0]].y = (tri[p[1]].y - tri[p[2]].y) * r + tri[p[2]].y;
}else{ // degenerate undimentioned triangle. Has not area
tri.p1.x = tri.p2.x = tri.p3.x;
tri.p1.y = tri.p2.y = tri.p3.y;
}
}
}
function runTest(){
var result1,result2,mustBeSimilar;
var countSimilar = 0;
var countNorm = 0;
var error1 = 0;
var error2 = 0;
for(var i = 0; i < iterations; i ++){
randomTriangle(tri1);
if(Math.random() < presentSimilar){
mustBeSimilar = true;
countSimilar += 1;
tri2.p1.x = tri1.p1.x;
tri2.p1.y = tri1.p1.y;
tri2.p2.x = tri1.p2.x;
tri2.p2.y = tri1.p2.y;
tri2.p3.x = tri1.p3.x;
tri2.p3.y = tri1.p3.y;
if(Math.random() >= presentSuperSimilar){
if(Math.random() < 0.5){ // swap two
v = tri2.p1;
tri2.p1 = tri2.p2;
tri2.p2 = v;
}
if(Math.random() < 0.5){ // swap two
v = tri2.p2;
tri2.p2 = tri2.p3;
tri2.p3 = v;
}
if(Math.random() < 0.5){ // swap two
v = tri2.p1;
tri2.p1 = tri2.p3;
tri2.p3 = v;
}
// scale and or mirror the second triangle
v = Math.random() * 2 - 1;
tri2.p1.x *= v;
tri2.p1.y *= v;
tri2.p2.x *= v;
tri2.p2.y *= v;
tri2.p3.x *= v;
tri2.p3.y *= v;
// rotate the triangle
v = (Math.random()- 0.5) * Math.PI * 4;
ydy = xdx = Math.cos(v);
ydx = -(xdy = Math.sin(v));
rotate(tri2.p1);
rotate(tri2.p2);
rotate(tri2.p3);
}
}else{
randomTriangle(tri2);
mustBeSimilar = false;
}
countNorm += 1;
result1 = tri1.isSimilar(tri2);
result2 = tri2.isSimilar(tri1);
if(result1 !== result2){
error1 += 1;
}
if(mustBeSimilar && (!result1 || !result2)){
error2 += 1;
}
for(var j = 0; j < 10; j++){
translateTriangle(tri1,Math.random(),Math.random());
translateTriangle(tri2,Math.random(),Math.random());
if(mustBeSimilar){
countSimilar += 1;
}
countNorm += 1;
result1a = tri1.isSimilar(tri2);
result2a = tri2.isSimilar(tri1);
if(result1a !== result2a || result1 !== result1a || result2 !== result2a){
error1 += 1;
}
if(mustBeSimilar && (!result1a || !result2a)){
error2 += 1;
}
}
}
divResult1.textContent = "Inconsistancy result failed : "+error1 + " of "+ countNorm;
divResult2.textContent = "Incorrect result failed : "+error2 + " of "+ countSimilar
}
var button = document.createElement("input");
button.type = "button"
button.value = "Run test"
button.onclick = runTest;
var divResult1 = document.createElement("div");
var divResult2 = document.createElement("div");
document.body.appendChild(button);
document.body.appendChild(divResult1);
document.body.appendChild(divResult2);最佳答案
根据 willywokka 的评论。您也许可以只查看是否存在单个比例因子。
// get the length squared and length of each side
a1 = Math.sqrt(...);
....
// Sort the values so a1 < b1 < c1, a2 < b2 < c2
if(b1 < a1) { tmp = b1; b1 = a1; a1 = tmp }
if(c1 < a1) { tmp = c1; c1 = a1; a1 = tmp }
if(c1 < b1) { tmp = c1; c1 = b1; b1 = tmp }
if(b2 < a2) { tmp = b2; b2 = a2; a2 = tmp }
if(c2 < a2) { tmp = c2; c2 = a2; a2 = tmp }
if(c2 < b2) { tmp = c2; c2 = b2; b2 = tmp }
// work out the scale factors
ka = a2 / a1;
kb = b2 / b1;
kc = c2 / c1;
if( abs(ka - kb) < epsilon && abs(kc - ka) < epsilon && abs(kc - kb) < epsilon )
// similar
else
// not similar
与其使用绝对 epsilon，不如使用值的 x% 以内的 epsilon。因此，如果 ka - x% < kb < ka + x%，即 (1-x/100) ka < kb < (1+x/100) ka，则认为这些值相等。或 (1-x/100) < kb/ka < (1+x/100)，或 abs(kb/ka) < x/100。
这个问题有一个统计上更严格的方法。这将涉及对我们所说的相似和检查三 Angular 形分布的含义的非常精确的定义。 Statistical shape analysis是一个糟糕的起点。 David George Kendall确实研究了三 Angular 形的形状。
关于javascript - 两个三 Angular 形相似吗，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36741468/