Open YJack0000 opened 3 months ago
/**
* @brief Updates the position of an object in the spatial index.
*
* @param object The object to update.
* @param newX The new x-coordinate of the object.
* @param newY The new y-coordinate of the object.
*/
template <typename T>
void OptimizedSpatialIndex<T>::update(const T& object, float newX, float newY) {
if (!inBounds(std::make_pair(newX, newY))) {
std::stringstream ss;
ss << "Update coordinates (" << newX << ", " << newY << ") out of bounds. ";
ss << "Size: " << size;
throw std::out_of_range(ss.str());
return;
}
remove(object);
insert(object, newX, newY);
}
The remove
and insert
cost a lot of time
Comparing to the DefaultSpatialIndex.cpp
For n Organism, Default approach can cost O(n) for update all of the organism QuadTree approach can cost O(n) * (O(log n) + O (logn)) => O(n logn)
But the total time consumption can be O(n^3) for Default approach And O(nlogn) for QuadTree approach
It's weird that the postIteration
in OptimizedSpatialIndex
cost more time than the time DefaultSpatialIndex
spend on query.
However, when the amount of organism is large enough, we can observer extreme lower query time reduction by using quadtree.
As I demonstrated in the presentation, the post iteration phase is excessively time-consuming, making the quadtree solution slower than the brute force approach. To resolve this issue, additional profiling is needed. Currently, using the optimized solution does not make sense due to its inefficiency.