[PATCH] DIX/ConfineTo: Improve algorithm to jump to the nearest point inside

[Egbert Eich]

ConfineToShape does not work well: The cursor often times doesn't jump
to the point closest to the current cursor position outside the shape.
This patch fixes this.

Signed-off-by: Egbert Eich <eich at freedesktop.org>
---
 dix/events.c | 84 +++++++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 64 insertions(+), 20 deletions(-)

diff --git a/dix/events.c b/dix/events.c
index ed3138d..40673ce 100644
--- a/dix/events.c
+++ b/dix/events.c
@@ -672,32 +672,76 @@ ConfineToShape(DeviceIntPtr pDev, RegionPtr shape, int *px, int *py)
 {
     BoxRec box;
     int x = *px, y = *py;
-    int incx = 1, incy = 1;
+    int         nbox;
+    BoxPtr      pbox;
+    int                d, min = (~0U >> 1), dx2, dy2, x_r, y_r;
 
     if (RegionContainsPoint(shape, x, y, &box))
         return;
-    box = *RegionExtents(shape);
-    /* this is rather crude */
-    do {
-        x += incx;
-        if (x >= box.x2) {
-            incx = -1;
-            x = *px - 1;
+
+    for (nbox = RegionNumRects(shape),
+             pbox = RegionRects(shape);
+         nbox--;
+         pbox++) {
+        if (pbox->x1 < x && pbox->x2 > x) {
+            d = pbox->y1 - y;
+            if (d >= 0) {
+                d *= d;
+                if (d < min) {
+                    *px = x;
+                    *py = pbox->y1 + 1;
+                    min = d;
+                }
+            } else {
+                d = pbox->y2 - y; d *= d;
+                if (d < min) {
+                    *px = x;
+                    *py = pbox->y2 - 1;
+                    min = d;
+                }
+            }
         }
-        else if (x < box.x1) {
-            incx = 1;
-            x = *px;
-            y += incy;
-            if (y >= box.y2) {
-                incy = -1;
-                y = *py - 1;
+        else if (pbox->y1 < y && pbox->y2 > y) {
+            d = pbox->x1 - x;
+            if (d >= 0) {
+                d *= d;
+                if (d < min) {
+                    *px = pbox->x1 + 1;
+                    *py = y;
+                    min = d;
+                }
+            } else {
+                d = pbox->x2 - x; d *= d;
+                if (d < min) {
+                    *px = pbox->x2 - 1;
+                    *py = y;
+                    min = d;
+                }
+            }
+        } else {
+            dx2 = pbox->x1 - x;
+            if (dx2 >= 0) {
+                dx2 *= dx2;
+                x_r = pbox->x1 + 1;
+            } else {
+                dx2 = pbox->x2 - x; dx2 *= dx2;
+                x_r = pbox->x2 - 1;
+            }
+            dy2 = pbox->y1 - y;
+            if (dy2 >= 0) {
+                dy2 *= dy2;
+                y_r = pbox->y1 + 1;
+            } else {
+                dy2 = pbox->y2 - y; dy2 *= dy2;
+                y_r = pbox->y2 - 1;
+            }
+            if ((d = dx2 + dy2) < min) {
+                *px = x_r;
+                *py = y_r;
+                min = d;
             }
-            else if (y < box.y1)
-                return;         /* should never get here! */
         }
-    } while (!RegionContainsPoint(shape, x, y, &box));
-    *px = x;
-    *py = y;
+    }
 }
 
 static void
-- 
1.8.1.4