Hi, I would like to share a wrapper for RTree. It is a great structure, if you need to keep track of a lot of geometric structures, such as rectangles, polygons etc.
I used it to enhance a sound system. I dont have much time to guide you through entire solution, but I believe that if you are curious enough, you will make a nice use of it
rtree.h
rtree.cpp
It works nice with otclient, all you need to do now is to add api to luafunction.cpp like follows :
Also if you need, I wrote some tests using Google Tests libs
Then if you success, you can use RTree in lua scripts, like this :
You might ask what is the advantage of this? if you want to find all areas, which are in neightbourhood of some point,
and you have already a lot of zones, you should get response FASTER than iterating over an array with those zones
Have fun with experimenting
I used it to enhance a sound system. I dont have much time to guide you through entire solution, but I believe that if you are curious enough, you will make a nice use of it
rtree.h
Code:
#ifndef STDEXT_RTREE_H
#define STDEXT_RTREE_H
#include <boost/geometry.hpp>
#include <deque>
#include <boost/geometry/index/rtree.hpp>
#include <framework/luaengine/luaobject.h>
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
namespace bgm = boost::geometry::model;
typedef bgm::point<int, 3, bg::cs::cartesian> BoostPoint;
typedef bgm::box<BoostPoint> BoundingBox;
typedef bgm::polygon<BoostPoint, false, true> BoostClosedPolygon;
class Shape : public LuaObject
{
public:
Shape() {}
virtual ~Shape() {}
virtual const BoundingBox& getBoundingBox() const {return m_boundingBox; }
virtual void updateBoundaryBox(){return;}
virtual void addPoint(int x, int y, int z);
virtual bool contains(int x, int y, int z) {return false;}
virtual void translate(int x, int y, int z) = 0;
protected:
std::deque<BoostPoint> m_points;
BoundingBox m_boundingBox;
};
class Polygon : public Shape {
public:
Polygon() { m_floor = 7;}
Polygon(int floor) { m_floor = floor;}
void addInnerPoint(int x, int y);
void addOuterPoint(int x, int y);
virtual const BoundingBox& getBoundingBox() const;
void normalize();
bool contains(int x, int y, int z);
virtual void translate(int x, int y, int z);
protected :
int m_floor;
BoostClosedPolygon m_polygon;
};
class Cuboid : public Shape {
};
typedef stdext::shared_object_ptr<Shape> ShapePtr;
typedef stdext::shared_object_ptr<Polygon> PolygonPtr;
namespace boost { namespace geometry { namespace index {
template<>
struct indexable<ShapePtr> {
typedef BoundingBox const& result_type;
result_type operator()(ShapePtr const &v) const { return v->getBoundingBox(); }
};
}
}
}
class RTree : public LuaObject {
public:
void insert(const ShapePtr& shp){
rt.insert(shp);
}
void insertMany(const std::vector<ShapePtr>& v){
for(auto it : v){
rt.insert(it);
}
}
void remove(const ShapePtr& v){
rt.remove(v);
}
std::vector<ShapePtr> intersects(int x, int y, int z){
std::vector<ShapePtr> result;
rt.query(bgi::intersects(BoostPoint(x,y,z)), std::back_inserter(result));
return result;
}
private:
bgi::rtree< ShapePtr, bgi::rstar<32> > rt;
};
typedef stdext::shared_object_ptr<RTree> RTreePtr;
#endif //STDEXT_RTREE_Hrtree.cpp
Code:
#include "rtree.h"
#include "math.h"
#include <boost/geometry/strategies/transform.hpp>
#include <boost/geometry/strategies/transform/matrix_transformers.hpp>
namespace bgst = boost::geometry::strategy::transform;
void Shape::addPoint(int x, int y, int z){
return;
};
void Polygon::addInnerPoint(int x, int y){
//TODO : ADD HOLES TO THE POLYGON
// m_polygon.inners().push_back(BoostPoint(x,y, m_floor));
}
void Polygon::addOuterPoint(int x, int y){
m_polygon.outer().push_back(BoostPoint(x,y, m_floor));
m_boundingBox = bg::return_envelope<BoundingBox>(m_polygon);
}
const BoundingBox& Polygon::getBoundingBox() const {
return m_boundingBox;
};
bool Polygon::contains(int x, int y, int z){
BoostPoint p = BoostPoint(x,y,z);
return bg::within(p, m_polygon) && m_floor == z;
}
void Polygon::translate(int dx, int dy, int dz){
bgst::translate_transformer<int, 3, 3> translate(dx, dy, dz);
BoostClosedPolygon new_polygon;
bg::transform(m_polygon, new_polygon, translate);
m_floor += dz;
m_polygon = new_polygon;
m_boundingBox = bg::return_envelope<BoundingBox>(m_polygon);
}It works nice with otclient, all you need to do now is to add api to luafunction.cpp like follows :
Code:
g_lua.registerClass<Polygon>();
g_lua.bindClassStaticFunction<Polygon>("create", [](int floor){ return PolygonPtr(new Polygon(floor)); });
g_lua.bindClassMemberFunction<Polygon>("addPoint", &Polygon::addOuterPoint);
g_lua.bindClassMemberFunction<Polygon>("contains", &Polygon::contains);
g_lua.bindClassMemberFunction<Polygon>("translate", &Polygon::translate);
// Rtree
g_lua.registerClass<RTree>();
g_lua.bindClassStaticFunction<RTree>("create", []{ return RTreePtr(new RTree); });
g_lua.bindClassMemberFunction<RTree>("intersects", &RTree::intersects);
g_lua.bindClassMemberFunction<RTree>("insert", &RTree::insert);
g_lua.bindClassMemberFunction<RTree>("remove", &RTree::remove);Also if you need, I wrote some tests using Google Tests libs
Code:
#include "gtest/gtest.h"
#include <framework/stdext/rtree.h>
class RtreeUnit : public ::testing::Test {
};
TEST_F(RtreeUnit, TestPolygon) {
Polygon p;
p.addOuterPoint(0,0);
p.addOuterPoint(0,2);
p.addOuterPoint(2,2);
p.addOuterPoint(2,0);
bool contains = p.contains(1,1,7);
EXPECT_TRUE(contains);
bool above = p.contains(1,1,6);
EXPECT_FALSE(above);
bool outside = p.contains(1,3,7);
EXPECT_FALSE(outside);
}
TEST_F(RtreeUnit, TestRTree) {
PolygonPtr p = PolygonPtr(new Polygon(7));
p->addOuterPoint(0,0);
p->addOuterPoint(0,2);
p->addOuterPoint(2,2);
p->addOuterPoint(2,0);
RTree rt;
rt.insert(p);
auto result = rt.intersects(1,1,7);
EXPECT_EQ(1, result.size());
auto result2 = rt.intersects(1,16,7);
EXPECT_EQ(0, result2.size());
//Check if finds intersection
p->addOuterPoint(1, -5);
auto result3 = rt.intersects(1,-3,7);
EXPECT_EQ(1, result3.size());
p->translate(10, 10, 0);
auto result4 = rt.intersects(1,1,7);
EXPECT_NE(1, result4.size());
auto result5 = rt.intersects(11,11,7);
EXPECT_EQ(1, result5.size());
rt.remove(p);
auto result6 = rt.intersects(11,11,7);
EXPECT_EQ(0, result6.size());
}Then if you success, you can use RTree in lua scripts, like this :
Code:
local SoundZoneTree = RTree.create();
local SoundZone = Polygon.create(7)
SoundZone.addPoint(0,0)
SoundZone.addPoint(1,0)
SoundZone.addPoint(1,1)
SoundZone.addPoint(0,1)
SoundZone.addPoint(0,0)
SoundZoneTree.insert(SoundZone)You might ask what is the advantage of this? if you want to find all areas, which are in neightbourhood of some point,
and you have already a lot of zones, you should get response FASTER than iterating over an array with those zones
Have fun with experimenting
