I decided to share a piece in AngelScript. It is useful to greatly reduce number of tests looking for neighbours.

Main code:

``````class Vertex {
Vector2 coords;
Vertex(Vector2 c)
{
this.coords = c;
}
int opCmp(Vertex@ other)
{
if (coords.x > other.coords.x)
return 1;
else if (coords.x < other.coords.x)
return -1;
else if (coords.y > other.coords.y)
return 1;
else if (coords.y < other.coords.y)
return -1;
else return 0;
}
bool opEquals(Vertex@ other)
{
if (other.coords == coords)
return true;
else
return false;
}
String ToString() {
return "Vertex [" + String(coords.x) + " " + String(coords.y) + "]";
}
};
Array<Vertex@> vertices(4);
Rect rect;
int num_stored = 0;
bool split = false;
int count()
{
int ret = num_stored;
if (split) {
for (int i = 0; i < sa.length; i++)
ret += sa[i].count();
}
return ret;
}
String ToString()
{
String rectstr = rect.ToVector4().ToString();
return rectstr;
}
private void do_split()
{
float midx = (rect.left + rect.right) / 2.0;
float midy = (rect.top + rect.bottom) / 2.0;
NE = Quadtree(Rect(midx, rect.top, rect.right, midy));
NW = Quadtree(Rect(rect.left, rect.top, midx, midy));
SW = Quadtree(Rect(rect.left, midy, midx, rect.bottom));
SE = Quadtree(Rect(midx, midy, rect.right, rect.bottom));
split = true;
sa[0] = NE;
sa[1] = NW;
sa[2] = SW;
sa[3] = SE;
}
bool insert(Vertex@ vertex)
{
if ((rect.IsInside(vertex.coords) == OUTSIDE)) {
return false;
}
if (num_stored < 4) {
vertices[num_stored] = vertex;
num_stored++;
return true;
} else {
if (!split)
do_split();
for (int i = 0; i < sa.length; i++)
if (sa[i].insert(vertex))
return true;
}
return false;
}
Array<Vertex@> search(Rect r)
{
int intersecting = 0, i, j;
Array<Vertex@> ret;
if (num_stored == 0 && !split)
return ret;
Rect tr(r);
tr.Clip(rect);
if (tr.size.length == M_INFINITY)
return ret;
ret.Resize(num_stored);
for (i = 0; i < num_stored; i++)
ret[i] = vertices[i];
if (split) {
for (i = 0; i < sa.length; i++) {
Array<Vertex@> tmp = sa[i].search(r);
int offset = ret.length;
ret.Resize(offset + tmp.length);
for (j = 0; j < tmp.length; j++) {
ret[offset + j] = tmp[j];
}
}
}
return ret;
}
Rect find_rect(Vertex@ v)
{
vertices.Resize(num_stored);
if (vertices.Find(v) >= 0)
return rect;
else if (split)
for (int i = 0; i < sa.length; i++) {
Rect r = sa[i].find_rect(v);
if (r.size.length > 0)
return r;
}
return Rect();
}
{
rect = r;
}
};``````

Test program / usage example:

``````#include "Vertex2.as"

void Start()
{
Quadtree q(Rect(-500, -500, 500, 500));
Image img;
Rect search_rect(-100, -100, 100, 100);
img.SetSize(1000, 1000, 3);
img.ClearInt(0);
int inrect = 0;
int count = 0;
Array<Vertex@> all_points;
for (int i = 0; i < 100000; i++) {
Vertex v(Vector2(Random(-500, 500), Random(-500, 500)));
if (q.insert(v)) {
count++;
if (search_rect.IsInside(v.coords) != OUTSIDE) {
all_points.Push(v);
inrect++;
img.SetPixel(v.coords.x + 500, v.coords.y + 500, Color(1.0, 1.0, 0.0));
} else
img.SetPixel(v.coords.x + 500, v.coords.y + 500, Color(1.0, 0.0, 0.0));
} else
img.SetPixel(v.coords.x + 500, v.coords.y + 500, Color(0.1, 0.1, 1.0));
}
Print("Searching");
Array<Vertex@> vs = q.search(search_rect);
Print("Search done");
for (int i = 0; i < vs.length; i++)
img.SetPixel(vs[i].coords.x + 500, vs[i].coords.y + 500, Color(0.6, 1.0, 0.6));
Print("inrect: " + String(inrect));