What is the most efficient way to determine the closest mouse element?
I am currently working on a pet project that allows the user to create a graph (vertices / edges) on a screen in Java. I have vertices implemented as JComponents, but I have edges implemented as Line2D. When the user moves the mouse across the canvas, if it is within a certain threshold of proximity to one of the edges (or Line2D), then this edge (closest to the mouse) is highlighted.
My question is about how I am implementing which edge is closest to the mouse. Right now I have a mouselistener that detects movement; every time the mouse moves, my program loops through all the lines (edges) and determines the closest one using the Line2D ptDistSeg () function. If it is within the threshold, then it is highlighted (using a thicker stroke in the paint component).
It seems to me that this is very inefficient as it has to recalculate all the boundary distances from the mouse every time. For vertices, this is not a problem, since mouselisteners are associated with each vertex, and therefore the vertices know when they need to handle the event. Unfortunately I cannot do this with the edges as they are exposed as Line2Ds which mouseListener cannot implement.
So, is there a more efficient way to find the closest edge or should I implement edges differently?
Thank.
source to share
There is probably a better data structure for this, but one is to compute the axis bounding rectangle of each edge to get one rectangle per edge, and then store all those rectangles in the spatial data structure as an R-tree . R-trees support efficient queries of the form "give me all the rectangles that overlap some point", so you can use them to filter all line segments only for those that could potentially hit the mouse point and then just test them.
The disadvantages here are that moving nodes around will require a lot of R-tree reconstruction due to the cost of changing the bounding rectangles and that you will need to find a good R-tree library as R-trees aren't very easy to implement from scratch.
Hope this helps!
source to share