I'm current working on a pet project that allows a user to create a graph (vertices/edges) on screen in Java. I have the vertices implemented as JComponents but I have the edges implemented as Line2D's. When a user is moving the mouse across the canvas, if it is within a certain threshold of proximity to one of the edges (or Line2D's) that edge (the closest to the mouse) is highlighted.
My question deals with the way I implement which edge is closest to the mouse. Right now I have a mouselistener that detects movement; every time the mouse is moved my program cycles through all the lines (edges) and determines the closest one using Line2D's ptDistSeg() function. If this is within the threshold, then it is highlighted (using a thicker stroke in the paintcomponent).
To me this seems very inefficient as it has to recalculate all edge distances from the mouse every time it is moved. For the vertices this isn't a problem as the mouselisteners are associated with each vertex and therefore the vertices know when they need to handle the event. Unfortunately I can't do this with the edges as they are represented as Line2D's which can't implement a mouseListener.
So is there a more efficient way to find the closest edge or should I implement the edges a different way?
Thanks.
There's probably a better data structure for this out there somewhere, but one option would be to compute the axis-aligned bounding box of each edge to get one rectangle per edge, then to store all of these rectangles in a spatial data structure like an R-tree. R-trees support efficient queries of the form "give me all rectangles overlapping some point," so you could use that to filter down all the line segments to just those that might potentially hit the mouse point, then just test those.
The drawbacks here are that moving nodes around will require a lot of R-tree rebuilding due to the cost of changing the bounding boxes and that you'd need to find a good R-tree library, since R-trees aren't very easy to implement from scratch.
Hope this helps!