Поиск групп подобных треугольников среди массива треугольников по сторонам. Как реализовать?

Question

[Silence]

ПОИСК ГРУПП ПОДОБНЫХ ТРЕУГОЛЬНИКОВ.
Нужно, чтобы в итоге получилось например : Группа 1- 1,2,3.(Треугольники). Группа2-4,5.
Попробовал написать, но получается полная чушь.
Как реализовать?

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct
{
 double n;
 double m;
 double o;
 double s;
}Triangle;
int array (int n)
{
        while(1) 
        { 
                 printf("Enter array size: \n "); 
                 scanf("%d",&n); 
                 fflush(stdin); 
                 if (n>1 && n<=20)
                 break; 
                 printf("Error \n"); 
        } 
        printf("\n"); 
        return n; 
} 

void entercoord(Triangle *p)
{  
     printf("Enter first line range: \n");
     while (1)
    {
           fflush(stdin);
           if(scanf("%lg", &p->n)==1)
             break;
           printf("Eror! Enter 'n' again:"); 
     } 
	 printf("Enter second line range: \n");
     while (1)
    {
           fflush(stdin);
           if(scanf("%lg", &p->m)==1)
             break;
           printf("Eror! Enter 'm' again:"); 
     } 
     printf("Enter third line range: \n");
     while (1)
    {
           fflush(stdin);
           if(scanf("%lg", &p->o)==1)
             break;
           printf("Eror! Enter 'o' again:"); 
     } 
}
void enter(Triangle z[],int n)
{
     int i;
     for(i=0;i<n;i++)
     {
     printf("Enter lines for triangle [%d]\n",i+1);
     entercoord(&z[i]);
     }
}

void SumArea(Triangle z[20],int n)
{
       int j;
       for (j=0;j<n;j++)
       {
         z[j].s=sqrt (((z[j].n+z[j].m+z[j].o)/2)*(((z[j].n+z[j].m+z[j].o)/2)- z[j].n)*(((z[j].n+z[j].m+z[j].o)/2)-z[j].m)*(((z[j].n+z[j].m+z[j].o)/2)-z[j].o));
       }
}

void CompareTriangle( Triangle z[20],int n)
{
     int i,j;
     for(i = 0 ; i <n ; i++) 
     { 
       for(j = 0 ; j <n - i ; j++) 
       {  
           if(z[j].s < z[j+1].s) 
           {           
              Triangle tmp = z[j];
              z[j] = z[j+1];
              z[j+1] = tmp; 
           }
        }
    } 
}
void Output( Triangle z[20],int n)
{
     int i;
     for (i=0;i<n;i++)     
     {    
     printf("Line size of Triangle z[%d] : %lg,%lg,%lg \n",i+1,z[i].n,z[i].m,z[i].o);   
     printf("Triangle area z[%d]: %lg%\n",i+1,z[i].s);
     }
}


int main()
{
    int n;
    Triangle z[20];
    n=array(n);
    enter(z,n);
    SumArea(z,n);
    printf("Before sort:\n");
    Output(z,n);
    printf("Triangle compare:\n");
    CompareTriangle(z,n);
    printf("Sortirovka po ploshadeam:\n");
    Output(z,n);
    
    
    system("pause");
    return (0);
}

Answer 1

[Rsa97]

Для начала, чтобы было проще искать, лучше сохранить стороны треугольников по возрастанию, то есть z[j].n <= z[j].m <= z[j].o
Затем, вспоминаем правило подобия треугольников с учётом сортировки длин сторон:

(z[i].n / z[j].n) = (z[i].m / z[j].m) = (z[i].o / z[j].o)

Перепишем эти условия для компьютера:

(z[i].n / z[j].n) = (z[i].m / z[j].m) => ((z[i].n * z[j].m) / (z[i].m * z[j].n)) = 1
(z[i].n / z[j].n) = (z[i].o / z[j].o) => ((z[i].n * z[j].o) / (z[i].o * z[j].n)) = 1

Поскольку вещественные вычисления на компьютере дают погрешность, то условия надо преобразовать (epsilon - константа, задающая точность вычислений):

abs(((z[i].n * z[j].m) / (z[i].m * z[j].n)) - 1) < epsilon && 
abs((z[i].n * z[j].o) / (z[i].o * z[j].n)) - 1) < epsilon

Теперь начиная с первого треугольника, относим его к классу 1 проверяем его на подобие остальным и там, где треугольники подобны записываем их в класс 1.
Затем ищем треугольник, у которого класс не задан, относим его с следующему классу, проверяем его подобие остальным бесклассовым треугольникам, для подобных записываем тот же класс.
Продолжаем, пока все треугольники не будут отнесены к одному из классов.

Comments

[Silence]

Можешь пожалуйста более подробно написать, как сделать вот эту часть?
"Теперь начиная с первого треугольника, относим его к классу 1 проверяем его на подобие остальным и там, где треугольники подобны записываем их в класс 1.
Затем ищем треугольник, у которого класс не задан, относим его с следующему классу, проверяем его подобие остальным бесклассовым треугольникам, для подобных записываем тот же класс.
Продолжаем, пока все треугольники не будут отнесены к одному из классов."
Если в виде кода, вообще будет идеально, уж извини за тупость.

[Rsa97]

Adrikk: Примерно так:

class = 0;
for (i = 0; i < triangles.length; i++) {
  if (0 == triangle[i].class) {
    class++;
    triangle[i].class = class;
    for (j = i+1; j < triangles.length; j++) {
      if (0 == triangle[j].class && is_similar(triangle[i], triangle[j])) {
        triangle[j] = class;
      }
    }
}

[Silence]

Rsa97:
Я уже совсем запутался, не мог бы ты показать как вся эта функция поиска подобных групп выглядела бы в готов варианте?( на моем коде).
Уже и просить неловко,но тупо выбора нет...

Answer 2

[Александр]

Сравнивать один с остальными. Чтобы узнать подобные треугольники или нет - нужно отсортировать длины сторон по убыванию и сравнить их отношение(соотношения каждой пары сторон) - должно быть одинаковым или в определенном интервале(так как есть погрешность вычисления). Добавлять индексы найденых в группы. Ну и как то отмечать в массиве уже обработанные треугольники.