Having Issues getting the right performance
Closed this issue · 4 comments
I must be doing this wrong, I am doing a quick test (could be off) to get back a group of items
And I am finding it faster to do sphare checks for coillsion deteciton then using this, and everything i read online suggest QuadTree should be faster.
Am I doing this wrong?
` static void Test()
{
QuadTrees.QuadTreePoint<QPointObject> qtree = new QuadTrees.QuadTreePoint<QPointObject>();
List<QPointObject> items = new List<QPointObject>();
Random random = new Random();
//Create Items
for(int i = 0; i < 10000000; i++)
{
items.Add(new QPointObject(new PointF(random.Next(0,100), random.Next(0, 100))));
}
qtree.AddBulk(items);
//Search Rect
var serachRect = new RectangleF(9, 9, 10, 10);
//Get Items
Stopwatch sw = new Stopwatch();
sw.Start();
var listOne = new List<QPointObject>();
qtree.GetObjects(serachRect, listOne);
sw.Stop();
Console.WriteLine("1 Elapsed={0}", sw.Elapsed);
//Get Items Via Sphare
sw = new Stopwatch();
sw.Start();
var listTwo = new List<QPointObject>();
float deltaXSquared = 0;
float deltaYSquared = 0;
float sumRadiiSquared = 0;
float width = 10;
for (int i = 0; i < 10000000; i++)
{
deltaXSquared = serachRect.X - items[i].Point.X; // calc. delta X
deltaXSquared *= deltaXSquared; // square delta X
deltaYSquared = serachRect.Y - items[i].Point.Y; // calc. delta Y
deltaYSquared *= deltaYSquared; // square delta Y
// Calculate the sum of the radii, then square it
sumRadiiSquared = width;
sumRadiiSquared *= sumRadiiSquared;
if (deltaXSquared + deltaYSquared <= sumRadiiSquared)
{
listTwo.Add(items[i]);
}
}
sw.Stop();
Console.WriteLine("2 Elapsed={0}", sw.Elapsed);
}
}
public class QPointObject : QuadTrees.QTreePoint.IPointQuadStorable
{
public QPointObject(PointF point)
{
this.point = point;
}
private PointF point;
public PointF Point { get { return point; } }
}`
My use case would only have 1-50k items. I am using really high numbers just to test.
We found the performance acceptable and faster than all comparable libraries with node counts in the 100k range. Searching 10 million objects is not going to be particularly fast no matter which library you choose.
Perhaps a quad tree is not the library for you, or perhaps you should look into ways to reduce the number of nodes in a tree. Or even optimization methods (space distribution etc) that are not implemented.
Point taken. I attempted with
100k and Got these results. (Some times it showed 1 to be faster, but most it did not)
1 Elapsed=00:00:00.0053232
2 Elapsed=00:00:00.0039484
But it sounds like i am using it correctly, it just may not fit my use case like you mentioned.
I Thought it made sense in my case as I thought i could avoid N checks for collsion detection.
My real use case is 1000-10000 node range.
Thanks for the reply
I wrote another test to compare performance cleaned up. and i must have had my tests wrong before.
On avg I am geting 3.3-3.5 if i use 1000 vs 10000 points doing 1000 tests for each and avg them.
Looks like this is user Error. I just wanted to be sure to add this note.
class Program
{
static void Main(string[] args)
{
List<double> differnce = new List<double>();
for(int x = 0; x < 1000; x++)
{
QuadTrees.QuadTreePoint<PointItem> tree = new QuadTrees.QuadTreePoint<PointItem>();
List<PointItem> items = new List<PointItem>();
List<PointItem> foundQuad = new List<PointItem>();
List<PointItem> foundBase = new List<PointItem>();
int count = 1000;
Random random = new Random();
Stopwatch stopwatch = new Stopwatch();
for (int i = 0; i < count; i++)
{
items.Add(new PointItem(new PointF(random.Next(0, 2500), random.Next(0, 2500))));
}
tree.AddBulk(items);
RectangleF searchRect = new RectangleF(random.Next(0, 2500), random.Next(0, 2500), 10, 10);
stopwatch.Start();
foundQuad = tree.GetObjects(searchRect);
stopwatch.Stop();
var t1 = stopwatch.Elapsed;
Console.WriteLine("FindIntersections With Quad Tree Elapsed={0}", t1);
stopwatch.Start();
foundBase = FindIntersections(items, searchRect);
stopwatch.Stop();
var t2 = stopwatch.Elapsed;
Console.WriteLine("FindIntersections Elapsed={0}", t2);
differnce.Add(t2.TotalMilliseconds / t1.TotalMilliseconds);
}
double avgDiffernce = Convert.ToDouble(differnce.Sum()) / Convert.ToDouble(differnce.Count());
Console.WriteLine("Quad Tree avgDiffernce Is {0}x Faster", Math.Round(avgDiffernce, 4));
Console.ReadKey();
}
public static List<PointItem> FindIntersections(List<PointItem> items, RectangleF searchRect)
{
List<PointItem> found = new List<PointItem>();
float deltaXSquared = 0;
float deltaYSquared = 0;
float sumRadiiSquared = 0;
for (int i = 0; i < items.Count; i++)
{
deltaXSquared = searchRect.X - items[i].Point.X; // calc. delta X
deltaXSquared *= deltaXSquared; // square delta X
deltaYSquared = searchRect.Y - items[i].Point.Y; // calc. delta Y
deltaYSquared *= deltaYSquared; // square delta Y
// Calculate the sum of the radii, then square it
sumRadiiSquared = searchRect.Width;
sumRadiiSquared *= sumRadiiSquared;
if (deltaXSquared + deltaYSquared <= sumRadiiSquared)
{
found.Add(items[i]);
}
}
return found;
}
}
class PointItem : QuadTrees.QTreePoint.IPointQuadStorable
{
public PointItem(PointF point)
{
this.point = point;
}
private PointF point;
public PointF Point { get { return this.point; } }
}
I have researched a bit
it's NOT a normal performance, due to bug in implementation
#11