Форум программистов, компьютерный форум CyberForum.ru

Поможите реализовать эту программу поиск ближайших объектов - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Логическое выражение преобразовать в бинарное дерево http://www.cyberforum.ru/cpp-beginners/thread1147459.html
Преобразовать логическое выражение в бинарное дерево и вывести его.Выражение может содержать логическое и,или,отрицание(&,|,! соответственно).Например: 0|(0 | 1)&X(значение х пользователь вводит руками).
C++ Выяснить, верно ли, что в последовательности имеются пять идущих подряд букв е Условия: Даны натуральное число n, символы s1, …, sn. Выяснить, верно ли, что в последовательности s1, …, sn имеются пять идущих подряд букв е. Примерное решение(моё, может быть абсолютно неправильным т.к. делал по примеру): #include <conio.h> #include <clocale> #include <iostream> #include <cmath> using namespace std; int main () {setlocale(LC_ALL, "Russian_Russia.1251"); int n,i,k=0; http://www.cyberforum.ru/cpp-beginners/thread1147447.html
C++ Советы по программе, которая должна сделать перевод литров в четверти
Народ, нужны ваши советы, надо зделать програму на языке C++, перевод литров в чверти. В одной чверте 3.08 литров. Я пытался зделать сам и оно получилось (один раз, без понятия почему потом не хотело), но потом начелов выдавать такое, до этой програмы мне такого не писало: "suchera.exe": Загружено: "D:\suchera\Debug\suchera.exe", Символы загружены. "suchera.exe": Загружено:...
C++ По заданным значениям х и n найти элементы ряда и вывести на экран
2. По заданным значениям х и n найти элементы ряда и вывести на экран. x1/2, x2/3, x3/4, ...... , xn/(n+1).
C++ Определить, через сколько лет селекционер сможет засеять новой зерновой культурой поле площадью s га http://www.cyberforum.ru/cpp-beginners/thread1147439.html
Очень нужно решение,. желательно к четвергу. 1. Селекционер вывел новый сорт зерновой культуры и снял с опытной делянки k кг семян. Посеяв 1 кг семян, можно за сезон собрать p кг семян. через сколько лет селекционер сможет засеять новой зерновой культурой поле площадью s га, если норма высева n кг/га? (решить нужно через while). Заранее спасибо!
C++ Ребятушки, у кого-ниудь есть алгоритм кодирования и декодирования по Хаффману? декодирование у меня есть я как бы среднячок, но сама написать не осилю) подробнее

Показать сообщение отдельно
Azihan
0 / 0 / 0
Регистрация: 04.11.2013
Сообщений: 5

Поможите реализовать эту программу поиск ближайших объектов - C++

13.04.2014, 22:08. Просмотров 167. Ответов 0
Метки (Все метки)

C++
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
class SPHERE_SET_TREE
{
public:
  class POSITION;
  class ITEM;
  class NODE;
 
  // Структура задает элемент множества сфер
  struct SPHERE
  {
    void* pData; // Указатель на данные пользователя, шаблоны не применяются для сокращения записи
    POINT3D Center; // Центр сферы
    float Radius; // Радиус сферы
 
    SPHERE( void* const pData_=NULL, const POINT3D& Center_=POINT3D(0,0,0), const float Radius_=0) 
      : pData(pData_), Center(Center_), Radius(Radius_) {}
  };
  
  // Тип функции, которая принимает уведомление о пересечении
  typedef void (*SSTCALLBACK)(const SPHERE&);
 
 
  // Добавляет новую сферу в множество
  POSITION Push( const SPHERE& Sphere );
  // Удаляет сферу из множества
  void Pop( const POSITION& Pos );
  // Перемещает одну из сфер множества в пространстве с получением новой позиции в дереве
  void Move( const SPHERE& Sphere, POSITION& Pos );
  // Удаляет все сферы из множества
  void Clear();
 
  // Проверяет пересечение сферы "Sphere" с множеством сфер, 
  // заданным объектом класса SPHERE_SET_TREE
  void TestIntersection( const SPHERE& Sphere, const SSTCALLBACK Callback ) const;
 
 
  SPHERE_SET_TREE( const AABB& BoundingBox_, // "бокс" описывающий множество
                   const float MaxSphereRadius_,  // радиус наибольшей сферы
                   const float Density_ // Плотность распределения сфер в пространстве, (0,1), 
                                        // 0-низкая, 1-высокая
                   );
  ~SPHERE_SET_TREE() { Clear(); }
 
 
  // --------------------------------------------------------------------------------------------
private:
  NODE* pRootNode;
  const AABB BoundingBox;
  const float MaxSphereRadius;
  const float Density;
 
  SPHERE_SET_TREE( const SPHERE_SET_TREE& ); //запрет копирования
  SPHERE_SET_TREE& operator = ( const SPHERE_SET_TREE& );//запрет присваивания
 
  POSITION RecursivePush( NODE*& pNode, NODE* const pParent, const AABB& B, const SPHERE& Sphere);
  void DeleteItem( const POSITION& Pos ); //удаляет элемент из списка, прикрепленного к узлу
  bool DeleteNode( NODE*& pNode ); //удаляет узел дерева
  void RecursiveTestIntersection( const NODE* const pNode, const SPHERE& Sphere, 
                                  const SSTCALLBACK Callback ) const;
  bool IsSphereInsideBox( const SPHERE& Sphere, const AABB& Box ) const;//проверяет находится ли
                                                                        //сфера внутри "бокса"
  bool TestIntersection( const SPHERE&, const SPHERE& ) const;//проверяет пересечение двух сфер
};
 
 
// задает позицию элемента множества в дереве
class SPHERE_SET_TREE::POSITION
{
public:
  POSITION() : pNode(NULL), pItem(NULL) {}
 
private:
  friend SPHERE_SET_TREE;
 
  NODE* pNode;
  ITEM* pItem;
 
  POSITION( NODE* const pNode_, ITEM* const pItem_ ) : pNode(pNode_), pItem(pItem_) {}
};
 
// Внутреннее представление элемента множества
class SPHERE_SET_TREE::ITEM
{
public:
  SPHERE Sphere;
  ITEM* pPrev, * pNext;
 
  ITEM( const SPHERE& Sphere_, ITEM* const pNext_ ) : Sphere(Sphere_),pPrev(NULL),pNext(pNext_){}
  ~ITEM() { delete pNext; }
 
private:
  ITEM( const ITEM& );//запрет копирования
  ITEM& operator=( const ITEM& );//запрет присваивания
};
 
// Узел дерева
class SPHERE_SET_TREE::NODE
{
public:
  const AABB B;
  const int IndexOfMaxBoxDimension;
  ITEM* pItem;
  NODE* pParent, * pPositive, * pNegative;
 
  NODE( const AABB& B_, const int IndexOfMaxBoxDimension_, NODE* const pParent_ );
  ~NODE();
 
  bool IsEmpty() const { return !pItem && !pPositive && !pNegative; }
 
private:
  NODE( const NODE& );//запрет копирования
  NODE& operator=( const NODE& );//запрет присваивания
};
 
 
SPHERE_SET_TREE::NODE::NODE(const AABB& B_,const int IndexOfMaxBoxDimension_,NODE* const pParent_)
  : B(B_), IndexOfMaxBoxDimension(IndexOfMaxBoxDimension_), 
    pItem(NULL), pParent(pParent_), pPositive(NULL), pNegative(NULL) {}
 
SPHERE_SET_TREE::NODE::~NODE() 
{
  delete pItem; delete pPositive; delete pNegative;
}
 
 
SPHERE_SET_TREE::POSITION SPHERE_SET_TREE::RecursivePush( NODE*& pNode, NODE* const pParent, 
                                                          const AABB& B, const SPHERE& Sphere  )
{
  // Ищем максимальный размер бокса
  int IndexOfMaxBoxDimension=0;
  { const POINT3D Size(B.Size());float MaxBoxDimension=Size[0];
    for( int i=1; i<3; ++i ) if( Size[i]>MaxBoxDimension ) 
    { 
      MaxBoxDimension=Size[i]; 
      IndexOfMaxBoxDimension=i; 
    } 
  }
 
  // Если эта часть пространства не описана деревом, строим новый узел
  if( !pNode ) pNode=new NODE(B,IndexOfMaxBoxDimension,pParent); 
 
  assert( B.Equal(pNode->B) );
  assert( IndexOfMaxBoxDimension==pNode->IndexOfMaxBoxDimension );
 
  // Вычисляем ширину общей области двух подпространств
  const float MaxBoxDimension=B.Max[IndexOfMaxBoxDimension]-B.Min[IndexOfMaxBoxDimension],
              BorderHalfWidth=std::min(float(MaxSphereRadius),MaxBoxDimension*Density*0.25f);
 
  if( Sphere.Radius>=BorderHalfWidth ) //проверяем соотношение радиуса сферы и ширины границы
  { // прикрепляем сферу к узлу дерева
    pNode->pItem=new ITEM(Sphere,pNode->pItem); 
    if( pNode->pItem->pNext ) pNode->pItem->pNext->pPrev=pNode->pItem;
    return POSITION(pNode,pNode->pItem);
  }
  else
  { // продолжаем разбиение пространства
    AABB B2(B);
    const float MaxBoxDimensionCenter=
                (B.Max[IndexOfMaxBoxDimension]+B.Min[IndexOfMaxBoxDimension])*0.5f,
                UnusedSpace=0.5f*MaxBoxDimension-BorderHalfWidth;
 
    if( Sphere.Center[IndexOfMaxBoxDimension]>MaxBoxDimensionCenter )
    {
      B2.Min[IndexOfMaxBoxDimension]+=UnusedSpace;
      return RecursivePush(pNode->pPositive,pNode,B2,Sphere);
    }
    else
    {
      B2.Max[IndexOfMaxBoxDimension]-=UnusedSpace;
      return RecursivePush(pNode->pNegative,pNode,B2,Sphere);
    }
  }
}
 
SPHERE_SET_TREE::POSITION SPHERE_SET_TREE::Push( const SPHERE& Sphere )
{
  assert( Sphere.Radius>0 );
 
  return RecursivePush(pRootNode,NULL,BoundingBox,Sphere);
}
 
// удаляет элемент, при этом корректирует двусвязный список
void SPHERE_SET_TREE::DeleteItem( const POSITION& Pos )
{
  assert( Pos.pNode && Pos.pItem );
 
  if( Pos.pItem->pPrev ) 
    Pos.pItem->pPrev->pNext=Pos.pItem->pNext;
  else                 
    Pos.pNode->pItem=Pos.pItem->pNext;
 
  if( Pos.pItem->pNext )
  { 
    Pos.pItem->pNext->pPrev=Pos.pItem->pPrev; 
    Pos.pItem->pNext=NULL;
  }
 
  delete Pos.pItem;
}
 
// Если у узла нет детей и прикрепленных элементов, удаляет узел и корректирует дерево
bool SPHERE_SET_TREE::DeleteNode( NODE*& pNode )
{
  if( pNode && pNode->IsEmpty() )
  {
    if( pNode->pParent )
    {
      if( pNode->pParent->pPositive==pNode ) pNode->pParent->pPositive=NULL;
      if( pNode->pParent->pNegative==pNode ) pNode->pParent->pNegative=NULL;
 
      NODE* const pNode2=pNode;
      pNode=pNode->pParent;
      delete pNode2;
    }
    else
    {
      assert( pRootNode==pNode );
      pRootNode=NULL;
      delete pNode;
      pNode=NULL;
    }
    return true;
  }
  return false;
}
 
// Удаляет элемент и корректирует дерево
void SPHERE_SET_TREE::Pop( const POSITION& Pos )
{
  assert( Pos.pNode && Pos.pItem );
 
  DeleteItem(Pos);
  for( NODE* pNode=Pos.pNode; DeleteNode(pNode); );
}
 
// Перемещает сферу в пространстве, перестроение дерева минимально, 
// для незначительного перемещения
void SPHERE_SET_TREE::Move( const SPHERE& Sphere, POSITION& Pos )
{
  assert( Sphere.Radius>0 );
  assert( Pos.pNode && Pos.pItem );
 
  if( IsSphereInsideBox(Sphere,Pos.pNode->B) )
  {
    Pos.pItem->Sphere=Sphere;
  }
  else
  {
    DeleteItem(Pos);
 
    NODE* pNode=Pos.pNode;
    if( !DeleteNode(pNode) ) pNode=pNode->pParent;
 
    while( pNode && !IsSphereInsideBox(Sphere,pNode->B) )
      if( !DeleteNode(pNode) ) pNode=pNode->pParent;
 
    if( !pNode ) Pos=Push(Sphere);
    else         Pos=RecursivePush(pNode,pNode->pParent,pNode->B,Sphere);
  }
}
 
void SPHERE_SET_TREE::Clear() 
{ 
  delete pRootNode; pRootNode=NULL; 
}
 
SPHERE_SET_TREE::SPHERE_SET_TREE( const AABB& BoundingBox_, const float MaxSphereRadius_, 
                                  const float Density_ )
  : pRootNode(NULL), BoundingBox(BoundingBox_),MaxSphereRadius(MaxSphereRadius_),Density(Density_)
{}
 
// Рекурсивный проход по дереву для определения пересечения, 
// скорость работы функции достаточно высока из-за простых сравнений
void SPHERE_SET_TREE::RecursiveTestIntersection( const NODE* const pNode, const SPHERE& Sphere,
                                                 const SSTCALLBACK Callback ) const
{
  assert( pNode && !pNode->IsEmpty() );
 
  for( const ITEM* pItem=pNode->pItem; pItem; pItem=pItem->pNext )
    if( TestIntersection(Sphere,pItem->Sphere) )
      Callback(pItem->Sphere); // Callback вызывается в случае пересечения
 
  const int IndexOfMaxBoxDimension=pNode->IndexOfMaxBoxDimension;
 
  if( pNode->pPositive && Sphere.Center[IndexOfMaxBoxDimension]+Sphere.Radius>=
                          pNode->pPositive->B.Min[IndexOfMaxBoxDimension] )
    RecursiveTestIntersection(pNode->pPositive,Sphere,Callback); //продолжаем в позитивном 
                                                                 //подпространстве
 
  if( pNode->pNegative && Sphere.Center[IndexOfMaxBoxDimension]-Sphere.Radius<=
                          pNode->pNegative->B.Max[IndexOfMaxBoxDimension] )
    RecursiveTestIntersection(pNode->pNegative,Sphere,Callback); //продолжаем в негативном 
                                                                 //подпространстве
}
 
void SPHERE_SET_TREE::TestIntersection( const SPHERE& Sphere, const SSTCALLBACK Callback ) const
{
  if( pRootNode )
    RecursiveTestIntersection(pRootNode,Sphere,Callback);
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru