Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

Реализовать поиск по заданному полю в массиве объектов пользовательского типа - C++
ОСНОВЫ ОБРАБОТКИ СТРУКТУР С клавиатуры ввести последовательность записей, содержащих информацию о студенческие группы института...

Реализовать поиск по заданному полю в списке объектов пользовательского типа - C++
Вечер добрый. Помогите с написанием кода Задание в dev c++ Описать структуру, содержащую следующие поля: • фамилия, имя; • номер...

Реализовать поиск по заданному полю в массиве объектов пользовательского типа - C++
Все сделал, в своей задачи, осталось только вот это, помогите. Вывод на экран информацию о людях, родившихся под знаком зодиака, название...

Реализовать поиск в массиве объектов пользовательского типа по заданному полю - C++
Создать типизированный файл, элементами которого являются сведения об автомобилях: марка, вместимость, год выпуска, цвет. Вывести марку...

Реализовать поиск по заданному полю в массиве объектов ползовательского типа (структуры) - C++
Здравствуйте, помогите разобраться как решать данную задачу, заранее спасибо! Дан массив записей, содержащий сведения о товарах:...

Реализовать поиск в массиве объектов пользовательского типа по заданному полю (структуры) - C++
1) В столовой предлагается N комплексных обедов, состоящих из Q блюд. Известна стоимость и калорийность каждого блюда. Сколько стоит...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2014, 22:08
Привет! Вот еще темы с ответами:

Реализовать поиск и сортировку по заданному полю в списке объектов пользовательского типа - C++
Доброго времени суток. Дали задачу &quot;Запись о багаже пассажира содержит: фамилия, номер рейса, дата время вылета, пункт назначения, кол-во...

Реализовать поиск по заданному полю в массиве объектов ползовательского типа (структуры) - C++
Задача: Используя функции и режим меню, создать файл из 10 структур, просмотреть файл, добавить в файл новую информацию и, применяя режим...

Реализовать поиск в массиве пользовательских объектов по заданному полю (использовать std::vector) - C++
помогите,пожалуйста,очень нужно!!!!!! Имеются сведения(модель-цена). Выделить заданное число самых дешевых моделей.(ЧЕРЕЗ ВЕКТОР)

Реализовать поиск по заданному полю в массиве объектов пользовательского типа (структура Student) - C++
Описать переменную студент, содержащию имя, фамилию, отчество, название учебного заведения и номер группы. Создать список студентов...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.