Re: GnomeCanvasLine

[Gustavo Joćo Alves Marques Carneiro <ee96090 fe up pt>]

On Wed, 3 May 2000, Lauris Kaplinski wrote:

> 
> On Wed, 3 May 2000, Gustavo Joćo Alves Marques Carneiro wrote:
> 
> >   Because of a school project I'm working on (a 3D modeler using
> > GnomeCanvas), I need to make sure that the routine that checks if a point
> > belongs to an item. I'm using exclusively GnomeCanvasLine. 
> >   gnome_canvas_get_item_at  calls the function
> > gnome_canvas_item_invoke_point, which calls the item's point virtual
> > function.  This function calculates the distance between the point and
> > each of the item's edges, using formulas like 			
> > 	dist = sqrt (dx * dx + dy * dy) - width / 2.0;
> > 
> >   This is very slow; my teacher says we should use something like
> > 	dist = dx; if the line's inclination is < 1.0, or
> > 	dist = dy; otherwise.
> > 
> >   gnome_canvas_item_invoke_point is also invoked as the pointer moves
> > across the canvas, to synthesize enter/leave notify events to canvas
> > items. This is also very slow. Amazingly, I don't notice it being slow. I
> > must be reading the code wrong. If not, can I make a patch to GnomeCanvas?
> 
> Depending on CPU, you probably lose about 20-200 cycles (my estimate).
> Even with 100MHz CPU you can get 500000 calculations per second. As canvas
> will execute ::point method only if coordinates are inside objects binding
> box, it is probably sufficent even for complex drawings. If not, you
> should better implement your own line item, which checks segment binding
> boxes, before calculating distance.
> 
> As much, as I know, the new approach of canvas will be to use all/nothing
> approach, i.e. it is no more interested in actual distance, only if point
> is inside object, or not. If you still want to speed this up, save

  Yes! I think that would be the best choice. It doesn't matter the exact
distance to the line, only if it is sufficiently close or not. That's why
calculating the square root is an overkill just to find out if a point  is
close to a line.

> (width * width / 4.0)
> during ::update and compare this to
> (dx * dx + dy * dy)
> 
> If you really need distance, you can find smallest squared value and
> take square root of this once.

  No square roots please! :) I mean, calculating a square root each time
the pointer moves across the canvas is not a good idea.

> 
> Calculating line inclination is probably not much faster, and
> abovementioned algorithm generates visible errors with fat lines near 45
> degrees angle.

  I don't agree. With 45 degrees angle, dx is equal to dy -- there's no
error (if you just want to find out if a point is close to a line).

> 
> Regards,
> Lauris Kaplinski
> 
> > 
> > -- 
> > Gustavo J.A.M. Carneiro
> > [reinolinux.fe.up.pt/~ee96090]
> >                                        
> 

-- 
Gustavo J.A.M. Carneiro
[reinolinux.fe.up.pt/~ee96090]