As a partial-time project, I work on some geometry utilities and come across a relatively simple question that seems to have a not-so-simple solution.
The problem is that EPSILON is too small for the problem. To see if the two triangles are similar, I train the 3 internal corners as their cosines for each triangle, and then sort them. Then I test Math.abs(t1[0]-t2[0]) < EPSILON , where t1 is one triangle and t2 is another, each of which contains three angles.
I get about 20% - 80% failures on triangles, which, as I know, are similar. When I bring EPSILON to a larger value, for example, still very small 0.0000001, there is no failure (well, not at the time I gave the tests).
Below is the extracted relevant triangle function, and I also included the test code as a demo below. Press the button and run the tests and show the results. Triangles are randomly generated. Each one so often forms two identical triangles, of which approximately half are exact copies, and the rest are copies, but the scaled, mirrored, rotated and vec-order are shuffled, while maintaining similarity
I would like to know how to calculate a reasonable EPSILON that will reduce incorrect results but keep the system as accurate as possible?
Although there is a possibility that there is another error in the test code, which I will continue to check.
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 ab }; // 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;
UPDATE
Additional Information.
Error in a similar triangle using the cosine of the angles EPSILON: 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
UPDATE 2
Outputting results and fixing errors (apologies @lhf I did not use sqrt epsilon, I still used the original constant)
Here are the test results for the same set of triangles. Inconsistency means that comparing triangle 1 with triangle 2 is a different result than triangle 2 to 1. False means that two well-known similar triangles failed, and incorrect inconsistency means that two well-known similar triangles did not pass one test and passed the other.
Using length relationships gave the worst result, but using cosine was not much better than similar triangles with irregular inconsistencies, which had a very high inconsistency rate between comparing t1 and t2 and t2-t1 using the length ratio. But it makes sense that the magnitude of the coefficients will vary greatly depending on which order is executed.
As you can see, using the square root of EPSILON completely eliminated the error for both methods.
If lhf wants to put sqrt (epsilon) comment as an answer, I agree as an answer. And thanks to everyone for their input, and I have some further readings thanks to 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;