How to detect a click on an edge of a multigraph?

I have written a win32 api-based GUI app which uses GDI+ features such as DrawCurve() and DrawLine().

This app draws lines and curves that represent a multigraph.

The data structure for the edge is simply a struct of five int's. (x1, y1, x2, y2, and id)

If there is only one edge between two vertices, a straight line segment is drawn using DrawLine(). If there are more than one edges, curves are drawn using DrawCurve() -- Here, I spread straight-line edges about the midpoint of two vertices, making them curves. A point some unit pixels apart from it is calculated using the normal line equation. If more edges are added then a pixel two unit pixels apart from the midpoint is selected, then next time 3 unit pixels, and so on.

Now I have two questions on detecting the click on edges.

In finding straight-line edges, to minimize the search time, what should I do?
It's quite simple to check if the pixel clicked is on the line segment but comparing all edges would be inefficient if the number of edges large. It seems possible to do it in O(log n), where n is the number of edges.
EDIT: at this point the edges (class Edge) are stored in std::map that maps edge id (int)'s to Edge objects and I'm considering declaring another container that maps pixels to edge id's.
I'm considering using binary search trees but what can be the key? Or should I use just a 2D pixel array?
Can I get the array of points used by DrawCurve()? If this is impossible, then I should re-calculate the cardinal spline, get the array of points, and check if the point clicked by the user matches any point in that array.

Solution

If you have complex shaped lines you can do as follows:

Create an internal bitmap the size of your graph and fill it with black.
When you render your graph also render to this bitmap the edges you want to have click-able, but, render them with a different color. Store these color values in a table together with the corresponding ID. The important thing here is that the colors are different (unique).
When the graph is clicked, transfer the X and Y co-ordinates to your internal bitmap and read the pixel. If non-black, look up the color value in your table and get the associated ID.

This way do don't need to worry about the shape at all, neither is there a need to use your own curve algorithm and so forth. The cost is extra memory, this will a consideration, but unless it is a huge graph (in which case you can buffer the drawing) it is in most cases not an issue. You can render the internal bitmap in a second pass to have main graphics appear faster (as usual).

Hope this helps!

(tip: you can render the "internal" lines with a wider Pen so it gets more sensitive).