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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Azihan
0 / 0 / 0
Регистрация: 04.11.2013
Сообщений: 5
#1

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

13.04.2014, 22:08. Просмотров 162. Ответов 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);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2014, 22:08     Поможите реализовать эту программу поиск ближайших объектов
Посмотрите здесь:

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. C++
C++ Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.
C++ Надо изменить эту программу!
объясните пожалуйста эту программу C++
C++ Поиск трех ближайших точек к данной
C++ Поиск двух ближайших друг к другу точек
Числа считаются равными если они отличаются не более, чем на (10^-12) / c++ / как реализовать эту возможность? C++
C++ Реализовать поиск в массиве пользовательских объектов по заданному полю (использовать std::vector)
Реализовать поиск по заданному полю в массиве объектов ползовательского типа (структуры) C++
Реализовать поиск по заданному полю в массиве объектов типа "Знак зодиака" C++
C++ Реализовать поиск по заданному полю в массиве объектов типа Рейс (моделирование работы справочной автовокзала)
C++ Реализовать поиск и сортировку по заданному полю в списке объектов пользовательского типа

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 21:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru