OctTree not returning all close objects

[davidebazzi]

trafficstars

I found this situation where not all the curves near to e1 are returned. Ellipse e1 = Ellipse.Construct(); e1.SetArcPlaneCenterRadiusAngles(Plane.XYPlane, new GeoPoint(-2.6645352591003757E-15, -0.00061799183524513523, -1.4186852022952081E-11), 3.2542739087564954, 1.5707963267948966, 0.78526360536556272); Ellipse e2 = Ellipse.Construct(); e2.SetArcPlaneCenterRadiusAngles(Plane.XYPlane, new GeoPoint(0.00043698863923324893, 0.00043698863923324893, -1.2655946892266502E-11), 3.2531320020360277, 0.78539843638719131, 0.78553221540911267); Line l3 = Line.Construct(); l3.SetTwoPoints(new GeoPoint(-10.8194119352, 10.8194119352, -1.8179609362265755E-11), new GeoPoint(-2.30074868929, 2.30074868929, -1.7698803840286583E-11)); Line l4 = Line.Construct(); l4.SetTwoPoints(new GeoPoint(2.30074868929, 2.30074868929, -1.2655946856715126E-11), new GeoPoint(10.8194119379, 10.8194119379, 5.5347351477650072E-12));

GeoObjectList list = new GeoObjectList(e1, e2, l3, l4);

OctTree<IGeoObject> tree = new OctTree<IGeoObject>(list.GetExtent(), 0.001); tree.AddObject(e2); tree.AddObject(l3); tree.AddObject(l4);

IGeoObject[] nearObjects = tree.GetObjectsCloseTo(e1);

nearObjects contains only l4, but I expect also e2.

If I use this code, then I get both. BoundingCube bc = e1.GetBoundingCube(); bc.Expand(0.0001); IGeoObject[] nearObjects2 = tree.GetObjectsFromBox(bc);

The "problem" is that the OctTree nodes are splitted right on the extrema of e1 and e2. In blue the 4 curves. Red lines is the bounding cube of the 4 curves. Green lines are the bounding cubes of the nodes of the octtree Result.cdb.json

1. Is that correct?
2. There is a way to get the objects of the "near" node without increasing the size of the BoundingCube? Because I don't know it a priori that I am in this situation.

[dsn27]

As no one has answered this question yet, I'll give it a try.

There are several places in the source code where the BoundingCube is intentionally expanded. For example: https://github.com/FriendsOfCADability/CADability/blob/573df1370880b52420b31dc25b8d8c0308fd9c3e/CADability/BRepIntersection.cs#L1782-L1792

This suggests that expanding the BoundingCube slightly (e.g. with a tolerance) is the intended and correct way to ensure nearby objects are included in queries like OctTree.GetObjectsWithin.

So I believe adjusting the bounding cube is a valid and reasonable solution here.