Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / треугольники / 11 сообщений из 11, страница 1 из 1
10.04.2005, 06:27
    #33006706
regromus
regromus
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
Привет всем

Помогите вот с такой задачей:

Дано 3n точек на плоскости, причем никакие 3 из них не лежат на 1ой прямой.
Построить множество n треугольников с вершинами в этих точках так, чтобы никакие 2 треугольника не пересекались и не содержали друг друга.

Вот то что я сделал:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define M  100 
float x[M];
float y[M];
int i,j,k,n;
//----------------------------------------------------------//
int Chten()
{
 ifstream chten;
 chten.open("c:\\bc\\zadachi\\koor.txt");
 if (chten==NULL)
  {
   cout<<"error";
   return  0 ;
  }
 chten >> n;
 for (i= 0 ;i<n;i++)
  {
   chten>>x[i];
   chten>>y[i];
  }
}
//-----------------------------------------------------------//
int proverka()
{
 for (i= 0 ;i<n;i++){
 for (j=i;j<n;j++){
 for (k=j;k<n;k++){
 if ((x[j]-x[i])== 0 )   continue;
 if ((y[j]-y[i])== 0 )   continue;
 if ((k==j) || (i==j)) continue;
 if (((x[k]-x[i])/(x[j]-x[i]))-((y[k]-y[i])/(y[j]-y[i]))== 0 )
 {
  cout<<"error";
  return  0 ;
 }
}}}}
//===========================================================//
int main()
{
 clrscr();
 Chten();//чтение точек из файла//
 proverka();//чтобы никакие 3 точки не лежали на 1ой прямой//
 printf("\nX\n");//распечатка исходных точек//
 for (i= 0 ;i<n;i++)
  {
   printf("%f",x[i]);
   printf("%c",i% 2 ?'\t':'\n');
  }
 printf("\nY\n");
 for (i= 0 ;i<n;i++)
  {
   printf("%f",y[i]);
   printf("%c",i% 2 ?'\t':'\n');
  }
 getch();
}

Теперь надо:Построить множество n треугольников с вершинами в этих точках так, чтобы никакие 2 треугольника не пересекались и не содержали друг друга.

Помогите плз
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2005, 12:18
    #33006771
Lelikk
Lelikk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
Последнее время уважаемый regromus интересутеся исключительно геометрическими задачами, к чему бы?
________________________________________________________
Глюк - это высокоорганизованная система не поддающихся определению частиц
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2005, 12:23
    #33006773
XM
XM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
Гы, построить несамопересекающийся контур, охватывающий все точки и свести задачу к триангуляции невыпуклого полигона
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2005, 14:23
    #33006835
regromus
regromus
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
ХА-ХА блин
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2005, 14:27
    #33006837
regromus
regromus
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
Чё вы коры мочите.Помог бы кто!!!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2005, 22:09
    #33007163
Lelikk
Lelikk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
XMГы, построить несамопересекающийся контур, охватывающий все точки и свести задачу к триангуляции невыпуклого полигона

Вообще-то это уже решение, осталось немного подумать над кодом. Все алгоритмы стандартны.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.04.2005, 10:35
    #33007536
Petro123
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
В каждой OS есть OpenGL а в ней есть класс - тесселятор
Код: plaintext
gluTessBeginPolygon
сделает тебе триангуляцию полигона и даже невыпуклого.
)))))).
______________________________________________
Вы имеете право хранить молчание! Всё что Вы скажете может быть использовано против Вас в суде!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2005, 13:38
    #33010658
rergomus
rergomus
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
Привет всем.

Выкладываю код готовой программы:

Дано 3n точек на плоскости, причем никакие 3 из них не лежат на 1ой прямой.
Построить множество n треугольников с вершинами в этих точках так, чтобы никакие 2 треугольника не пересекались и не содержали друг друга.

Все кому не лень, могут разобраться в коде, заодно ПРОТЕСТИРОВАТЬ и доложить мне об ошибке(я даже не прошу её исправлять,но надеюсь на это). Можете обсерать этот код - мне по..уй.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#define M  50 
float x[M],y[M]; //координаты точек//
int i,j,k,n,q,l= 0 ,z[M],w= 0 ,r;
long double a,b,c,a1,b1,c1;
long double p,p1,p2,p3,s,s1,s2,s3;
float t[M][ 6 ];  //треугольники//

//----------------------------------------------------------//
int Chten()
{
 ifstream chten;
 chten.open("c:\\bc\\zadachi\\koor.txt");
 if (chten==NULL)
  {
   cout<<"error";
   return  0 ;
  }
 chten >> n;
 for (i= 0 ;i<n;i++)
  {
   chten>>x[i];
   chten>>y[i];
  }
}
//-----------------------------------------------------------//
int proverka()
{
 for (i= 0 ;i<n;i++){
 for (j=i;j<n;j++){
 for (k=j;k<n;k++){
 if ((x[j]-x[i])== 0 )   continue;
 if ((y[j]-y[i])== 0 )   continue;
 if ((k==j) || (i==j)) continue;
 if (((x[k]-x[i])/(x[j]-x[i]))-((y[k]-y[i])/(y[j]-y[i]))== 0 )
 {
  cout<<"error";
  getch();
  return  0 ;
 }
}}}}
//-----------------------------------------------------------//
float postr()
{
  a=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
  b=sqrt((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k]));
  c=sqrt((x[i]-x[k])*(x[i]-x[k])+(y[i]-y[k])*(y[i]-y[k]));
  p=(a+b+c)/ 2 ;
  s=sqrt(p*(p-a)*(p-b)*(p-c));
  for (q= 0 ;q<n;q++)
  {
   if ((q==i)||(q==k)||(q==j))
   continue;
   a1=sqrt((x[k]-x[q])*(x[k]-x[q])+(y[k]-y[q])*(y[k]-y[q]));
   b1=sqrt((x[j]-x[q])*(x[j]-x[q])+(y[j]-y[q])*(y[j]-y[q]));
   c1=sqrt((x[i]-x[q])*(x[i]-x[q])+(y[i]-y[q])*(y[i]-y[q]));

double  ca=(y[k]-y[j])*(x[q]-x[j]) - (y[q]-y[j])*(x[k]-x[j]);
double  cb=(y[q]-y[j])*(x[q]-x[i]) - (y[q]-y[i])*(x[q]-x[j]);
double  z =(y[k]-y[j])*(x[q]-x[i]) - (y[q]-y[i])*(x[k]-x[j]);
double  ua;
double  ub;

           if (z!= 0 )
                { ua=ca/z;
                  ub=cb/z; }
           else
                { ua=ub= 0 ; }

  if ( ( 0 <=ua)&&(ua<= 1 )&&( 0 <=ub)&&(ub<= 1 ) )
  {
   p1=(a1+b1+b)/ 2 ;
   p2=(b1+c1+a)/ 2 ;
   p3=(a1+c1+c)/ 2 ;
   goto kor;
  }

        ca=(y[i]-y[j])*(x[q]-x[j]) - (y[q]-y[j])*(x[i]-x[j]);
        cb=(y[q]-y[j])*(x[q]-x[k]) - (y[q]-y[k])*(x[q]-x[j]);
        z =(y[i]-y[j])*(x[q]-x[k]) - (y[q]-y[k])*(x[i]-x[j]);

        if (z!= 0 )
                { ua=ca/z;
                  ub=cb/z; }
           else
                { ua=ub= 0 ; }

  if ( ( 0 <=ua)&&(ua<= 1 )&&( 0 <=ub)&&(ub<= 1 ) )
  {
   p1=(a1+b1+c)/ 2 ;
   p2=(b1+c1+b)/ 2 ;
   p3=(a1+c1+a)/ 2 ;
   goto kor;
  }

        ca=(y[i]-y[j])*(x[q]-x[k]) - (y[q]-y[k])*(x[i]-x[j]);
        cb=(y[q]-y[j])*(x[q]-x[i]) - (y[q]-y[i])*(x[q]-x[j]);
        z =(y[i]-y[j])*(x[q]-x[i]) - (y[q]-y[i])*(x[i]-x[j]);

        if (z!= 0 )
                { ua=ca/z;
                  ub=cb/z; }
           else
                { ua=ub= 0 ; }

  if ( ( 0 <=ua)&&(ua<= 1 )&&( 0 <=ub)&&(ub<= 1 ) )
  {
   p1=(a1+b1+a)/ 2 ;
   p2=(b1+c1+c)/ 2 ;
   p3=(a1+c1+b)/ 2 ;
   goto kor;
  }


       p1=(a1+b1+b)/ 2 ;
       p2=(b1+c1+c)/ 2 ;
       p3=(a1+c1+a)/ 2 ;

kor:  s1=sqrt(p1*(p1-a1)*(p1-b1)*(p1-b));
      s2=sqrt(p2*(p2-b1)*(p2-c1)*(p2-c));
      s3=sqrt(p3*(p3-a1)*(p3-c1)*(p3-a));
   if (s==(s1+s2+s3)) return  0 . 0 ;
  }
    t[l][ 0 ]=x[i];
    t[l][ 1 ]=y[i];
     z[w]=i;
     w=w+ 1 ;
    t[l][ 2 ]=x[j];
    t[l][ 3 ]=y[j];
     z[w]=j;
     w=w+ 1 ;
    t[l][ 4 ]=x[k];
    t[l][ 5 ]=y[k];
     z[w]=k;
     w=w+ 1 ;
     l=l+ 1 ;
    return  1 . 0 ;
}
//===========================================================//
int main()
{
 clrscr();
 z[ 0 ]= 100 ;//главное чтобы z[i]!=0//
 z[ 0 ]= 100 ;//главное чтобы z[i]!=0//
 Chten();//чтение точек из файла//
 if (n% 3 != 0 ) {printf("error");getch();return  0 ;}//чтобы кол_во точек делилось
 if (proverka()== 0 ) return  0 ;//чтобы никакие 3 точки не лежали на 1ой прямой//
  if (n== 3 )//если кол_во точек равно 3 то строим 1 теругольник и выходим//
 {
  t[ 0 ][ 0 ]=x[ 0 ];
  t[ 0 ][ 1 ]=y[ 0 ];
  t[ 0 ][ 2 ]=x[ 1 ];
  t[ 0 ][ 3 ]=y[ 1 ];
  t[ 0 ][ 4 ]=x[ 2 ];
  t[ 0 ][ 5 ]=y[ 2 ];
  goto kc;
}
 for (i= 0 ;i<n;i++){  //строим тругольники!!!//
 for (j=i;j<n;j++){
 for (k=j;k<n;k++){
 if ((i==j)||(j==k)||(k==i)) continue;
 for (r= 0 ;r<=w;r++)  //мы не берем координаты уже построенных треугольников//
 {
  if ((i==z[r])||(j==z[r])||(k==z[r])) goto as;
 }
 if (postr()== 0 . 0 ) continue;//проверяем лежит ли точка внутри треугольника//
as:;
 }}}
kc:printf("\nответ!!!\n");//распечатка координат треугольников//
   for (i= 0 ;i<l;i++)
   {
    printf("%d треугольник",(i+ 1 ));
   for (j= 0 ;j< 6 ;j++)
   {
    printf("%5.2f",t[i][j]);
    if ((j% 5 == 0 )&&(j!= 0 )) printf("\n");
   }
   }
 getch();
}



Можете задавать вопросы по коду....
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2005, 13:52
    #33010711
Petro123
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
Весело .
Раз тебе "по..уй", то нам тем-более.
)))))))).
______________________________________________
Вы имеете право хранить молчание! Всё что Вы скажете может быть использовано против Вас в суде!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2005, 17:57
    #33011594
Lelikk
Lelikk
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
2 rergomus:
Ну нафига нам разбирать твой код?
Если он работает, то и прекрасно, пользуйся
________________________________________________________
Глюк - это высокоорганизованная система не поддающихся определению частиц
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.04.2005, 21:02
    #33011971
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
треугольники
2 regromus

А в чем проблема-то?

Все алгоритмы которые тебе рекомендовали использользовать - стандартны. Часть из них реализована в STL. Часть содержится в любой библиотеки работы с графикой.

Чего непонятно-то конкретно?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / C++ [игнор отключен] [закрыт для гостей] / треугольники / 11 сообщений из 11, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 465ms
Закрыть
start [/forum/topic.php?fid=57&tablet=1&tid=2033478]:
 0ms
get settings:
 6ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 139ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 55ms
get tp. blocked users:
 2ms
others: 231ms
total:  465ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]