Select a canvas line "point"
Gerhard Reithofer
I've written an application which draws line charts which represent the
usage of computer resources that are collected periodically.
The chart uses a time value for x and the collected value for y.
I. e. that each endpoint of a canvas line represents a specific
discrete value. To visualize (ballonhelp) the corresponding discrete
value I use the canvas bind command (c=canvas, l=line):
$c bind $l <Enter> "[namespace current]::balloonhelp %W %x %y $l"
My problem is, that I get the mouse cursor value (%x %y), but this
represents only a "near" value where the line has been selected.
I need the nearest exact endpoint (coord) to that selection-point.
I plan to implement a geometric distance analyze function to get the
"nearest" value, but due to the amount of data (200 points per curve or
more) it might be a very time consuming process.
My questions:
Does anyone have an idea, to solve this without analyzing any single
coord of the line?
Does anyone have a simple solution which may reduce the time consuming
per point analyzation?
PS: I've searched the Wiki but haven't found anything for that problem.
Thanks in advance,
--
Gerhard Reithofer
Tech-EDV Support Forum - http://support.tech-edv.co.at
Arjen Markus
wrote:
Have you tried the [$canvas find closet] subcommand?
I have little experience with it myself, but my guess is
that that is what you are looking for.
Regards,
Arjen
suchenwi
> Have you tried the [$canvas find closet] subcommand?
That will return the id of the closest canvas item. If it's a line
with 200 points, you'd still have to iterate over them and determine
closeness to %x %y (which is most efficiently done with the hypot()
function).
Uwe Klein
> On 24 Aug., 09:12, Arjen Markus <arjen.mar...@wldelft.nl> wrote:
>
>
>>Have you tried the [$canvas find closet] subcommand?
>
>
> That will return the id of the closest canvas item. If it's a line
> with 200 points, you'd still have to iterate over them and determine
> closeness to %x %y (which is most efficiently done with the hypot()
> function).
In a similar situation I had created tagged canvas items
for every point to achieve this.
set idx 0
foreach {x y} $coords {
set coord [ list ....]
.$canv create oval $coord -tags "$line $line.$idx"
incr idx
}
>
uwe
Uwe Klein
Apropos:
the BLT vector type and the graph widget would
make this even easyier.
uwe
Joe English
>My problem is, that I get the mouse cursor value (%x %y), but this
>represents only a "near" value where the line has been selected.
>I need the nearest exact endpoint (coord) to that selection-point.
>
>I plan to implement a geometric distance analyze function to get the
>"nearest" value, but due to the amount of data (200 points per curve or
>more) it might be a very time consuming process.
~200 points sounds like a reasonable number to test to me;
it shouldn't be too slow even for a <Motion> binding.
A rule of thumb: anything a GUI does that takes less
than 10 milliseconds is the same as instantaneous.
Trying it to see:
% for {set i 0} {$i < 200} {incr i} { lappend pts [expr rand()] [expr rand()] }
% time { nearest $pts 0.5 0.5 } 1000
330 microseconds per iteration
YMMV, of course, but it looks like there's plenty of headroom
to accomodate more points per curve and/or slower machines.
>My questions:
>Does anyone have an idea, to solve this without analyzing any single
>coord of the line?
You could use a quadtree or other space-partitioning data
structure to get an O(log N) algorithm, but from the looks
of things you won't need one.
>Does anyone have a simple solution which may reduce the time consuming
>per point analyzation?
Just one suggestion: when searching for the minimum, compare the
squares of the distances instead of the distances; the former
is less effort to calculate. (This is a standard optimization
that, it would appear, not everbody knows about.)
--Joe English
Alexandre Ferrieux
edv.co.at> wrote:
>
> I. e. that each endpoint of a canvas line represents a specific
> discrete value. To visualize (ballonhelp) the corresponding discrete
> I need the nearest exact endpoint (coord) to that selection-point.
Since the graph is that of a function (at most one Y per X), maybe the
simplest would be to select the data point whose X value is that of
the mouse pointer: instead of projecting orthogonally on the curve,
you're projecting along the Y direction. A kind of "vertical
crosswire".
Guess I don't need to tell you why it is easier on the algorithmic
side...
Notice also that for certain fairly chaotic functions, the vertical
crosswire is the only one able to select all data points without
glueing the mouse to the legs of an atomic force microscope ;-)
-Alex
suchenwi
> Just one suggestion: when searching for the minimum, compare the
> squares of the distances instead of the distances; the former
> is less effort to calculate.
I'd however expect that hypot() as a single function call will be
faster than two multiplications and one addition on the Tcl side...
Gerhard Reithofer
thanks all for your valuable hints,.
After some testing I implemented a simple "nearest" calculation using
the hypoth() function point by point (thank's RS), no problem by 200
points.
Another approach by creating single line segemnts for each line pair
was abolished because many objects created many <Enter>/<Leave> events
as the apperance was "flickering", the performance was great.
BLT was rejected, because the application is running on several unix
platforms and it is not ensured, that this binary extension is always
present.
If the perfomance is lacking sometime, optimizations will be implemented
(e.g. crosswire algorithm, thx Uwe).