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

[Keith Packard]

Egbert Eich <eich at freedesktop.org> writes:

> 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.

I came up with something a bit simpler which confines the point to each
box in the region and then picks the result which moves the cursor the
shortest distance. I think it would generate the same result, but I
stuck a bunch of range tests in the distance computation to avoid
overflow in weird cases. Dunno if you like this better or not?

commit d8a52a3a3b5bc4a1ff0a986e87dd6c36366e531b
Author: Keith Packard <keithp at keithp.com>
Date:   Fri Oct 4 16:00:49 2013 -0700

    Improved ConfineToShape
    
    Find the box within the region which is closest to the point and move
    there.
    
    Signed-off-by: Keith Packard <keithp at keithp.com>

diff --git a/dix/events.c b/dix/events.c
index 086601a..8610e60 100644
--- a/dix/events.c
+++ b/dix/events.c
@@ -667,37 +667,62 @@ SetCriticalEvent(int event)
     criticalEvents[event >> 3] |= 1 << (event & 7);
 }
 
+static uint32_t
+ConfineToBox(int x, int y, BoxPtr box, int *px, int16_t *py)
+{
+    int dx, dy;
+
+    *px = x;
+    *py = y;
+
+    if (*px < box->x1)
+        *px = box->x1;
+    else if (*px >= box->x2)
+        *px = box->x2 - 1;
+
+    if (*py < box->y1)
+        *py = box->y1;
+    else if (*py >= box->y2)
+        *py = box->y2 - 1;
+
+    dx = x - *px;
+    if (dx < 0) dx = -dx;
+    if (dx > 32767)
+        dx = 32767;
+    dy = y - *py;
+    if (dy < 0) dy = -dy;
+    if (dy > 32767)
+        dy = 32767;
+
+    return (uint32_t) dx * (uint32_t) dx + (uint32_t) dy * (uint32_t) dy;
+}
+
 void
 ConfineToShape(DeviceIntPtr pDev, RegionPtr shape, int *px, int *py)
 {
-    BoxRec box;
+    BoxPtr box;
+    int nbox;
     int x = *px, y = *py;
-    int incx = 1, incy = 1;
+    int bx, by;
+    uint32_t box_dist_2;
+    int best_x, best_y;
+    uint32_t best_dist_2;
+    int i;
 
-    if (RegionContainsPoint(shape, x, y, &box))
+    if (RegionContainsPoint(shape, x, y, NULL))
         return;
-    box = *RegionExtents(shape);
-    /* this is rather crude */
-    do {
-        x += incx;
-        if (x >= box.x2) {
-            incx = -1;
-            x = *px - 1;
-        }
-        else if (x < box.x1) {
-            incx = 1;
-            x = *px;
-            y += incy;
-            if (y >= box.y2) {
-                incy = -1;
-                y = *py - 1;
-            }
-            else if (y < box.y1)
-                return;         /* should never get here! */
+    box = REGION_RECTS(shape);
+    for (i = 0; i < REGION_NUM_RECTS(shape); i++) {
+        box_dist_2 = ConfineToBox(x, y, &box[i], &bx, &by);
+        if (i == 0 || box_dist_2 < best_dist_2) {
+            best_dist_2 = box_dist_2;
+            best_x = bx;
+            best_y = by;
         }
-    } while (!RegionContainsPoint(shape, x, y, &box));
-    *px = x;
-    *py = y;
+    }
+
+    *px = best_x;
+    *py = best_y;
 }
 
 static void

-- 
keith.packard at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: not available
URL: <http://lists.x.org/archives/xorg-devel/attachments/20131004/8c01c601/attachment.pgp>