drop use of bounding box to determine whether an item covers a point; add Item::covers(Duple const&)

Default implementation for Item still uses bounding box, but specializations for Arc (Circle), Polygon, Line and PolyLine have been added

23 files changed, 254 insertions, 48 deletions

diff --git a/libs/canvas/arc.cc b/libs/canvas/arc.cc
index eeecd3204a..e95fbe0ad5 100644
--- a/libs/canvas/arc.cc
+++ b/libs/canvas/arc.cc
@@ -16,8 +16,11 @@
     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
 
+#include <cmath>
 #include <algorithm>
+
 #include <cairomm/context.h>
+
 #include "pbd/compose.h"
 #include "canvas/circle.h"
 #include "canvas/types.h"
@@ -97,7 +100,6 @@ Arc::set_radius (Coord r)
 	end_change ();
 }	
 
-
 void
 Arc::set_arc (double deg)
 {
@@ -121,3 +123,15 @@ Arc::set_start (double deg)
 	end_change ();
 }	
 
+bool
+Arc::covers (Duple const & point) const
+{
+	Duple p = canvas_to_item (point);
+
+	double angle_degs = atan (p.y/p.x) * 2.0 * M_PI;
+	double radius = sqrt (p.x * p.x + p.y * p.y);
+	
+	return (angle_degs >= _start_degrees) && 
+		(angle_degs <= (_start_degrees + _arc_degrees)) && 
+		(radius < _radius);
+}
diff --git a/libs/canvas/arrow.cc b/libs/canvas/arrow.cc
index f82f2d96de..55f5173253 100644
--- a/libs/canvas/arrow.cc
+++ b/libs/canvas/arrow.cc
@@ -221,3 +221,20 @@ Arrow::set_color (Color color)
 		_heads[i].polygon->set_fill_color (color);
 	}
 }
+
+bool
+Arrow::covers (Duple const & point) const
+{
+	if (_heads[0].polygon && _heads[0].polygon->covers (point)) {
+		return true;
+	}
+	if (_line && _line->covers (point)) {
+		return true;
+	}
+
+	if (_heads[1].polygon && _heads[1].polygon->covers (point)) {
+		return true;
+	}
+
+	return false;
+}
diff --git a/libs/canvas/canvas.cc b/libs/canvas/canvas.cc
index 22243edc8f..8b0586c9ae 100644
--- a/libs/canvas/canvas.cc
+++ b/libs/canvas/canvas.cc
@@ -264,36 +264,6 @@ GtkCanvas::GtkCanvas ()
 		    Gdk::ENTER_NOTIFY_MASK | Gdk::LEAVE_NOTIFY_MASK);
 }
 
-/** Handler for pointer motion events on the canvas.
- *  @param ev GDK event.
- *  @return true if the motion event was handled, otherwise false.
- */
-bool
-GtkCanvas::motion_notify_handler (GdkEventMotion* ev)
-{
-	DEBUG_TRACE (PBD::DEBUG::CanvasEvents, string_compose ("canvas motion @ %1, %2\n", ev->x, ev->y));
-
-	if (_grabbed_item) {
-		/* if we have a grabbed item, it gets just the motion event,
-		   since no enter/leave events can have happened.
-		*/
-		DEBUG_TRACE (PBD::DEBUG::CanvasEvents, string_compose ("%1 %2 (%3) was grabbed, send MOTION event there\n",
-								       _grabbed_item, _grabbed_item->whatami(), _grabbed_item->name));
-		return _grabbed_item->Event (reinterpret_cast<GdkEvent*> (ev));
-	}
-
-	Duple point (ev->x, ev->y);
-	
-	enter_leave_items (point, ev->state);
-
-	/* Now deliver the motion event.  It may seem a little inefficient
-	   to recompute the items under the event, but the enter notify/leave
-	   events may have deleted canvas items so it is important to
-	   recompute the list in deliver_event.
-	*/
-	return deliver_event (point, reinterpret_cast<GdkEvent*> (ev));
-}
-
 void
 GtkCanvas::enter_leave_items (int state)
 {
@@ -403,7 +373,7 @@ GtkCanvas::enter_leave_items (Duple const & point, int state)
 		DEBUG_TRACE (PBD::DEBUG::CanvasEvents, string_compose ("Enter %1 %2\n", new_item->whatami(), new_item->name));
 	}
 
-#if 0
+#if 1
 	cerr << "Within:\n";
 	for (set<Item const *>::const_iterator i = within_items.begin(); i != within_items.end(); ++i) {
 		cerr << '\t' << (*i)->whatami() << '/' << (*i)->name << endl;
@@ -565,6 +535,8 @@ GtkCanvas::on_button_release_event (GdkEventButton* ev)
 
 	GdkEvent copy = *((GdkEvent*)ev);
 	Duple where = window_to_canvas (Duple (ev->x, ev->y));
+	
+	enter_leave_items (where, ev->state);
 
 	copy.button.x = where.x;
 	copy.button.y = where.y;
@@ -587,15 +559,35 @@ GtkCanvas::on_motion_notify_event (GdkEventMotion* ev)
 	/* translate event coordinates from window to canvas */
 
 	GdkEvent copy = *((GdkEvent*)ev);
-	Duple where = window_to_canvas (Duple (ev->x, ev->y));
+	Duple point (ev->x, ev->y);
+	Duple where = window_to_canvas (point);
 
 	copy.motion.x = where.x;
 	copy.motion.y = where.y;
 
-	/* Coordinates in the event will be canvas coordinates, correctly adjusted
-	   for scroll if this GtkCanvas is in a GtkCanvasViewport.
+	/* Coordinates in "copy" will be canvas coordinates, 
+	*/
+
+	DEBUG_TRACE (PBD::DEBUG::CanvasEvents, string_compose ("canvas motion @ %1, %2\n", ev->x, ev->y));
+
+	if (_grabbed_item) {
+		/* if we have a grabbed item, it gets just the motion event,
+		   since no enter/leave events can have happened.
+		*/
+		DEBUG_TRACE (PBD::DEBUG::CanvasEvents, string_compose ("%1 %2 (%3) was grabbed, send MOTION event there\n",
+								       _grabbed_item, _grabbed_item->whatami(), _grabbed_item->name));
+		return _grabbed_item->Event (reinterpret_cast<GdkEvent*> (&copy));
+	}
+
+	enter_leave_items (where, ev->state);
+
+	/* Now deliver the motion event.  It may seem a little inefficient
+	   to recompute the items under the event, but the enter notify/leave
+	   events may have deleted canvas items so it is important to
+	   recompute the list in deliver_event.
 	*/
-	return motion_notify_handler ((GdkEventMotion*) &copy);
+
+	return deliver_event (point, reinterpret_cast<GdkEvent*> (&copy));
 }
 
 bool
diff --git a/libs/canvas/canvas/arc.h b/libs/canvas/canvas/arc.h
index fc1b72163e..c8d7f8e44f 100644
--- a/libs/canvas/canvas/arc.h
+++ b/libs/canvas/canvas/arc.h
@@ -51,6 +51,8 @@ public:
 		return _start_degrees;
 	}
 
+        bool covers (Duple const &) const;
+
 private:
         Duple  _center;
         Coord  _radius;
diff --git a/libs/canvas/canvas/arrow.h b/libs/canvas/canvas/arrow.h
index a5a338a3ba..ed3a5bb384 100644
--- a/libs/canvas/canvas/arrow.h
+++ b/libs/canvas/canvas/arrow.h
@@ -62,6 +62,8 @@ public:
 	void set_y0 (Coord);
 	void set_y1 (Coord);
 	
+        bool covers (Duple const &) const;
+
 private:
 	void setup_polygon (int);
 
diff --git a/libs/canvas/canvas/curve.h b/libs/canvas/canvas/curve.h
index f2ed6a1d0e..4cf69e19e3 100644
--- a/libs/canvas/canvas/curve.h
+++ b/libs/canvas/canvas/curve.h
@@ -29,9 +29,7 @@ public:
     Curve (Group *);
     
     void compute_bounding_box () const;
-
     void render (Rect const & area, Cairo::RefPtr<Cairo::Context>) const;
-
     void set (Points const &);
 
   protected:
diff --git a/libs/canvas/canvas/flag.h b/libs/canvas/canvas/flag.h
index 6664524a19..fe14a63d96 100644
--- a/libs/canvas/canvas/flag.h
+++ b/libs/canvas/canvas/flag.h
@@ -33,6 +33,8 @@ public:
 
 	void set_text (std::string const &);
 	void set_height (Distance);
+
+        bool covers (Duple const &) const;
 	
 private:
 	Distance _height;
diff --git a/libs/canvas/canvas/image.h b/libs/canvas/canvas/image.h
index 0dcf8e51b3..6134bb63b5 100644
--- a/libs/canvas/canvas/image.h
+++ b/libs/canvas/canvas/image.h
@@ -90,7 +90,7 @@ public:
 
     void render (Rect const &, Cairo::RefPtr<Cairo::Context>) const;
     void compute_bounding_box () const;
-    
+
 private:
     Cairo::Format            _format;
     int                      _width;
diff --git a/libs/canvas/canvas/item.h b/libs/canvas/canvas/item.h
index 7cad50e883..4ec1202644 100644
--- a/libs/canvas/canvas/item.h
+++ b/libs/canvas/canvas/item.h
@@ -75,6 +75,8 @@ public:
 		items.push_back (this);
 	}
 
+        virtual bool covers (Duple const &) const;
+
 	/** Update _bounding_box and _bounding_box_dirty */
 	virtual void compute_bounding_box () const = 0;
 
diff --git a/libs/canvas/canvas/line.h b/libs/canvas/canvas/line.h
index 36c0f48379..c22ecafc80 100644
--- a/libs/canvas/canvas/line.h
+++ b/libs/canvas/canvas/line.h
@@ -33,6 +33,7 @@ public:
 
 	void render (Rect const & area, Cairo::RefPtr<Cairo::Context>) const;
 	void compute_bounding_box () const;
+        bool covers (Duple const &) const;
 
 	void set (Duple, Duple);
 	void set_x0 (Coord);
diff --git a/libs/canvas/canvas/line_set.h b/libs/canvas/canvas/line_set.h
index cd551438b1..8fd01825df 100644
--- a/libs/canvas/canvas/line_set.h
+++ b/libs/canvas/canvas/line_set.h
@@ -34,6 +34,8 @@ public:
 	void compute_bounding_box () const;
 	void render (Rect const & area, Cairo::RefPtr<Cairo::Context>) const;
 
+        bool covers (Duple const &) const;
+
 	void set_height (Distance);
 
 	void add (Coord, Distance, Color);
diff --git a/libs/canvas/canvas/poly_line.h b/libs/canvas/canvas/poly_line.h
index 911dd140fc..830e76bae2 100644
--- a/libs/canvas/canvas/poly_line.h
+++ b/libs/canvas/canvas/poly_line.h
@@ -31,6 +31,8 @@ public:
 	PolyLine (Group *);
 
 	void render (Rect const & area, Cairo::RefPtr<Cairo::Context>) const;
+
+        bool covers (Duple const &) const;
 };
 	
 }
diff --git a/libs/canvas/canvas/polygon.h b/libs/canvas/canvas/polygon.h
index addfe48100..48eb494ae8 100644
--- a/libs/canvas/canvas/polygon.h
+++ b/libs/canvas/canvas/polygon.h
@@ -30,8 +30,18 @@ class Polygon : public PolyItem, public Fill
 {
 public:
 	Polygon (Group *);
+        virtual ~Polygon();
 
 	void render (Rect const & area, Cairo::RefPtr<Cairo::Context>) const;
+	void compute_bounding_box () const;
+        bool covers (Duple const &) const;
+
+  protected:
+    mutable float* multiple;
+    mutable float* constant;
+    mutable Points::size_type cached_size;
+    
+    void cache_shape_computation () const;
 };
 	
 }
diff --git a/libs/canvas/canvas/wave_view.h b/libs/canvas/canvas/wave_view.h
index fc39d7e555..05bd00f5ad 100644
--- a/libs/canvas/canvas/wave_view.h
+++ b/libs/canvas/canvas/wave_view.h
@@ -97,7 +97,6 @@ public:
         double gradient_depth() const { return _gradient_depth; }
         void set_shape (Shape);
 
-        
         /* currently missing because we don't need them (yet):
 	   set_shape_independent();
 	   set_logscaled_independent()
diff --git a/libs/canvas/flag.cc b/libs/canvas/flag.cc
index 8eb320e74b..756b54545f 100644
--- a/libs/canvas/flag.cc
+++ b/libs/canvas/flag.cc
@@ -66,3 +66,13 @@ Flag::set_height (Distance)
 {
 	_line->set (Duple (0, 0), Duple (0, _height));
 }
+
+bool
+Flag::covers (Duple const & point) const
+{
+	if (_rectangle) {
+		return _rectangle->covers (point);
+	} 
+
+	return false;
+}
diff --git a/libs/canvas/item.cc b/libs/canvas/item.cc
index 534ae6d52e..3c3816881a 100644
--- a/libs/canvas/item.cc
+++ b/libs/canvas/item.cc
@@ -546,6 +546,24 @@ Item::depth () const
 	return d;
 }
 
+bool
+Item::covers (Duple const & point) const
+{
+	Duple p = canvas_to_item (point);
+
+	if (_bounding_box_dirty) {
+		compute_bounding_box ();
+	}
+
+	boost::optional<Rect> r = bounding_box();
+
+	if (!r) {
+		return false;
+	}
+
+	return r.get().contains (p);
+}
+
 ostream&
 ArdourCanvas::operator<< (ostream& o, const Item& i)
 {
diff --git a/libs/canvas/line.cc b/libs/canvas/line.cc
index af2a0e47db..fcc190a705 100644
--- a/libs/canvas/line.cc
+++ b/libs/canvas/line.cc
@@ -147,3 +147,24 @@ Line::set_y1 (Coord y1)
 
 	DEBUG_TRACE (PBD::DEBUG::CanvasItemsDirtied, "canvas item dirty: line change\n");
 }
+
+bool
+Line::covers (Duple const & point) const
+{
+	Duple p = canvas_to_item (point);
+
+	/* compute area of triangle computed by the two line points and the one
+	   we are being asked about. If zero (within a given tolerance), the
+	   points are co-linear and the argument is on the line.
+	*/
+
+	double area = fabs (_points[0].x * (_points[0].y - p.y)) + 
+                           (_points[1].x * (p.y - _points[0].y)) + 
+		           (p.x * (_points[0].y - _points[1].y));
+
+	if (area < 0.001) {
+		return true;
+	}
+
+	return false;
+}
diff --git a/libs/canvas/line_set.cc b/libs/canvas/line_set.cc
index dc9f54e10b..1625e0478d 100644
--- a/libs/canvas/line_set.cc
+++ b/libs/canvas/line_set.cc
@@ -104,3 +104,9 @@ LineSet::clear ()
 	_bounding_box_dirty = true;
 	end_change ();
 }
+
+bool
+LineSet::covers (Duple const & /*point*/) const
+{
+	return false;
+}
diff --git a/libs/canvas/lookup_table.cc b/libs/canvas/lookup_table.cc
index 38b8be4afb..0cae7c9c4f 100644
--- a/libs/canvas/lookup_table.cc
+++ b/libs/canvas/lookup_table.cc
@@ -62,13 +62,9 @@ DumbLookupTable::items_at_point (Duple point) const
 		if (!(*i)->visible()) {
 			continue;
 		}
-
-		boost::optional<Rect> item_bbox = (*i)->bounding_box ();
-
-		if (item_bbox) {
-			if ((*i)->item_to_canvas (item_bbox.get ()).contains (point)) {
-				vitems.push_back (*i);
-			}
+		
+		if ((*i)->covers (point)) {
+			vitems.push_back (*i);
 		}
 	}
 
diff --git a/libs/canvas/poly_item.cc b/libs/canvas/poly_item.cc
index 2500ac90e2..b054b70bbf 100644
--- a/libs/canvas/poly_item.cc
+++ b/libs/canvas/poly_item.cc
@@ -38,7 +38,6 @@ void
 PolyItem::compute_bounding_box () const
 {
 	bool have_one = false;
-
 	Rect bbox;
 
 	for (Points::const_iterator i = _points.begin(); i != _points.end(); ++i) {
diff --git a/libs/canvas/poly_line.cc b/libs/canvas/poly_line.cc
index bdc4af9c10..2441e4e3dc 100644
--- a/libs/canvas/poly_line.cc
+++ b/libs/canvas/poly_line.cc
@@ -37,3 +37,37 @@ PolyLine::render (Rect const & area, Cairo::RefPtr<Cairo::Context> context) cons
 		context->stroke ();
 	}
 }
+
+bool
+PolyLine::covers (Duple const & point) const
+{
+	Duple p = canvas_to_item (point);
+
+	const Points::size_type npoints = _points.size();
+	
+	if (npoints < 2) {
+		return false;
+	}
+
+	Points::size_type i;
+	Points::size_type j;
+
+	/* repeat for each line segment */
+	
+	for (i = 1, j = 0; i < npoints; ++i, ++j) {
+
+		/* compute area of triangle computed by the two line points and the one
+		   we are being asked about. If zero (within a given tolerance), the
+		   points are co-linear and the argument is on the line.
+		*/
+
+		double area = fabs (_points[j].x * (_points[j].y - p.y)) + 
+  			           (_points[i].x * (p.y - _points[j].y)) + 
+			           (p.x * (_points[j].y - _points[i].y));
+		if (area < 0.001) {
+			return true;
+		}
+	}
+
+	return false;
+}
diff --git a/libs/canvas/polygon.cc b/libs/canvas/polygon.cc
index 1103cedbee..37046f4d4a 100644
--- a/libs/canvas/polygon.cc
+++ b/libs/canvas/polygon.cc
@@ -25,10 +25,19 @@ Polygon::Polygon (Group* parent)
 	: Item (parent)
 	, PolyItem (parent)
 	, Fill (parent)
+	, multiple (0)
+	, constant (0)
+	, cached_size (0)
 {
 
 }
 
+Polygon::~Polygon ()
+{
+	delete [] multiple;
+	delete [] constant;
+}
+
 void
 Polygon::render (Rect const & area, Cairo::RefPtr<Cairo::Context> context) const
 {
@@ -51,3 +60,72 @@ Polygon::render (Rect const & area, Cairo::RefPtr<Cairo::Context> context) const
 	}
 }
 
+void 
+Polygon::cache_shape_computation () const
+{
+	Points::size_type npoints = _points.size();
+
+	if (npoints == 0) {
+		return;
+	}
+
+	Points::size_type i;
+	Points::size_type j = npoints -1;
+
+	if (cached_size < npoints) {
+		cached_size = npoints;
+		delete [] multiple;
+		multiple = new float[cached_size];
+		delete [] constant;
+		constant = new float[cached_size];
+	}
+
+	for (i = 0; i < npoints; i++) {
+		if (_points[j].y == _points[i].y) {
+			constant[i] = _points[i].x;
+			multiple[i] = 0; 
+		} else {
+			constant[i] = _points[i].x-(_points[i].y*_points[j].x)/(_points[j].y-_points[i].y)+(_points[i].y*_points[i].x)/(_points[j].y-_points[i].y);
+			multiple[i] = (_points[j].x-_points[i].x)/(_points[j].y-_points[i].y); 
+		}
+
+		j = i; 
+	}
+}
+
+bool 
+Polygon::covers (Duple const & point) const
+{
+	Duple p = canvas_to_item (point);
+
+	Points::size_type npoints = _points.size();
+
+	if (npoints == 0) {
+		return false;
+	}
+
+	Points::size_type i;
+	Points::size_type j = npoints -1;
+	bool oddNodes = false;
+	
+	if (_bounding_box_dirty) {
+		compute_bounding_box ();
+	}
+	
+	for (i = 0; i < npoints; i++) {
+		if (((_points[i].y < p.y && _points[j].y >= p.y) || (_points[j].y < p.y && _points[i].y >= p.y))) {
+			oddNodes ^= (p.y * multiple[i] + constant[i] < p.x); 
+		}
+		j = i; 
+	}
+	
+	return oddNodes; 
+} 
+
+void
+Polygon::compute_bounding_box () const
+{
+	PolyItem::compute_bounding_box ();
+	cache_shape_computation ();
+}
+
diff --git a/libs/canvas/wave_view.cc b/libs/canvas/wave_view.cc
index 4ea9ff9fd3..3467672b88 100644
--- a/libs/canvas/wave_view.cc
+++ b/libs/canvas/wave_view.cc
@@ -686,3 +686,4 @@ WaveView::set_global_show_waveform_clipping (bool yn)
 		VisualPropertiesChanged (); /* EMIT SIGNAL */
 	}
 }
+