There is an array of triangles given by vertex coordinates. How to determine the numbers of triangles similar to the first one?

Question

Python

Hello!
There is an array of triangles given by vertex coordinates. It is necessary to determine the numbers of triangles similar to the first one.
What am I doing.
1. We need a formula for the distance between points:

def length(a, b):
  return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

2. To determine similar triangles, I will use the fact that the ratio of the perimeters of such triangles is equal to the coefficient. similarity, and the ratio of areas - the square of the same number. Accordingly, I need to find them for each of the triangles. Like this:

triangles = []

for i in v:
  a = length(i[0], i[1])
  b = length(i[0], i[2])
  c = length(i[1], i[2])
  triangle = []
  p = (a + b + c)/2
  area = math.sqrt(p * (p - a) * (p - b) * (p - c))
  triangle.append(p*2)
  triangle.append(area)
  triangles.append(triangle)

3. Now a function that will determine similar triangles:

def is_sim(sample, triangle):
  if int(sample[0]/triangle[0])**2 == int(sample[1]/triangle[1]):
    return True
  else:
    return False

4. And this function ran through the list of triangles

for i in range(0, len(triangles) - 1):
  if is_sim(triangles[0], triangles[i]):
    print str(i+1)

There is a competent person who claims that the result of the work is incorrect. But categorically refuses to even look into the code.
What's my mistake?

Answer 1

I read about the similarity of triangles ... I wondered why it is impossible to act according to the definition or signs of similarity? Rotate the triangle so that one edge lies on the axis, nothing interferes, right? So nothing prevents you from building a height and calculating an angle? This means you can do this three times.

Answer 2

I.
b = 1/32 * (137-sqrt(9553))
a = 9 / b
c = 16 - a - b
II.
a = 5
b = 5
c = 6
are far from similar, but they fall under 2 of your signs.
you have chosen not a sufficient condition to determine the similarity.

Answer 3

1. Checking the similarity by the ratios of the perimeter and area is not enough. See @tsarevfs for a counterexample , and @jcmvbkbc for a theoretical justification . 2. If the triangles are given by the coordinates of the vertices, the easiest way is to check the third sign of similarity (all three sides of one triangle are proportional to the sides of another). 3. If the coordinates of the vertices are small integers, then it is better to check the proportionality of not the sides themselves, but their squares, and check not the ratios of the sides, but the "cross-wise" products. To compare only potentially matching sides -- sort the side lengths (actually the squares of the lengths) in each triangle in ascending order.
For example, this is how you can modify the source code:

# квадрат расстояния между двумя точками
def length2(a, b):
    return (a[0] - b[0])**2 + (a[1] - b[1])**2

# подобны ли 2 треугольника, заданные отсортированными массивами длин сторон
def is_sim(sample, triangle):
    if sample[0] * triangle[1] != sample[1] * triangle[0]:
        return False
    elif sample[0] * triangle[2] != sample[2] * triangle[0]:
        return False
    elif sample[1] * triangle[2] != sample[2] * triangle[1]:
        return False
    else:
        return True

# преобразование массивов координат в массивы длин сторон
def make_triangles(v):
    triangles = []
    for i in v:
        a2 = length2(i[0], i[1])
        b2 = length2(i[0], i[2])
        c2 = length2(i[1], i[2])
        triangle = [a2, b2, c2]
        triangle.sort()
        triangles.append(triangle)
    return triangles

# основной код
triangles = make_triangles(v)

for i in range(1, len(triangles) ):
    if is_sim(triangles[0], triangles[i]):
        print "found similar trinangle: %s" % v[i]

If the coordinates can be large and/or real, then it is better to return to lengths and ratios, but when comparing in the is_sim function, rely not on exact equality, but with a tolerance ("with epsilons", see the comments of @bluesky and @tsarevfs )
AND on just in case: in the comments there were doubts about mirror-symmetrical triangles. So, the mirror image is similar to the original triangle, and the order of bypassing the sides for comparison does not play a role.

Answer 4

The mirror image of one of the similar triangles preserves the proportions of the sides and areas, but the triangles cease to be similar if they are not isosceles.

Answer 5

In general, if you think a little, it is easy to see (c) that there are infinitely many different triangles with equal perimeter and area. The (non-rigorous) proof goes something like this:
Consider all triangles of a given perimeter. Let's represent each of them as a point P in the polar coordinate system, one of the vertices of the triangle lies at the origin, the second is the given point, the third lies on the polar axis. Let us represent the area of ​​such a triangle with height z in a cylindrical coordinate system based on a given polar one. The set of all triangles of a given perimeter is described by a set of points P, which covers some simply connected region, on the boundaries of which the area is equal to 0. In addition, the area of ​​a triangle is a continuous function of P. Let us choose an arbitrary point P0 inside the region. Let S(P0) = S0 > 0. Consider all possible paths from the point P0 to the boundaries of the region. On each of these paths, S is a continuous function varying from S0 to 0. We choose a value S1, 0 < S1 < S0.

Answer 6

What does similar mean? in fact, you need to take a set of angles, right? further sorting the set of angles, you can group the data and return similar ones. Is it mirrored, too?

Answer 7

Take 3 signs of similarity.
Write tests for them.
You run 100,000 triangles. Take whatever is faster. Some have sines-cosines, others have square roots.

Answer 8

Most likely, integer coordinates are assumed in the problem. In this case, the error is in using sqrt, since the problem can be solved in integers: use, for example, scalar products.
If not, then you need to compare for equality using epsilons. And in any case, forget about Heron's formula.