如何确定鼠标在某个形状上的最近点？

Question

我已经创建了一个程序，将鼠标限制在基于黑色/白色位图的特定区域。该程序是100％原样运行的，但是使用不准确但快速的算法来重新定位鼠标，使其在区域外飘荡。

目前，在区外的移动鼠标，基本上会发生什么情况是这样的：

1. 一条线的区域和鼠标的新位置内预先定义的静点之间绘制。
2. 其中该行相交所允许的区域的边缘点被找到。
3. 鼠标移动到那一点。

这工作，但只适用完美与在正中央设置预先定义的点一个完美的圆。不幸的是，这绝不会是这样。该应用程序将使用各种矩形和不规则，无定形的形状。在这样的形状上，绘制的线与边相交的点通常不会是形状上与鼠标最近的点。

我需要创建一个新的算法，找到最接近的指向鼠标在允许区域边缘的新位置。我怎样才能做到这一点？优选地，该方法应该能够足够快地执行，以在将鼠标拖曳到该区域的边缘时给予平滑的鼠标移动。

（我这样做在OS目标C /可可X 10.7，但是，伪码是好的，如果你不想输入代码或者不知道目标C/C）

谢谢！

这是我目前的算法：

#import <Cocoa/Cocoa.h> 
#import "stuff.h" 
#import <CoreMedia/CoreMedia.h> 




bool 
is_in_area(NSInteger x, NSInteger y, NSBitmapImageRep *mouse_mask){ 

    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init]; 

    NSUInteger pixel[4]; 
    [mouse_mask getPixel:pixel atX:x y:y]; 

    if(pixel[0]!= 0){ 
     [pool release]; 
     return false; 
    } 
    [pool release]; 
    return true; 
} 

CGEventRef 
mouse_filter(CGEventTapProxy proxy, CGEventType type, CGEventRef event, NSBitmapImageRep *mouse_mask) { 


    CGPoint point = CGEventGetLocation(event); 


    float tX = point.x; 
    float tY = point.y; 

    if(is_in_area(tX,tY, mouse_mask)){ 

     // target is inside O.K. area, do nothing 
    }else{ 

    CGPoint target; 

    //point inside restricted region: 
    float iX = 600; // inside x 
    float iY = 500; // inside y 


    // delta to midpoint between iX,iY and tX,tY 
    float dX; 
    float dY; 

    float accuracy = .5; //accuracy to loop until reached 

    do { 
     dX = (tX-iX)/2; 
     dY = (tY-iY)/2; 

     if(is_in_area((tX-dX),(tY-dY),mouse_mask)){ 

      iX += dX; 
      iY += dY; 
     } else { 

      tX -= dX; 
      tY -= dY; 
     } 

    } while (abs(dX)>accuracy || abs(dY)>accuracy); 

     target = CGPointMake(roundf(tX), roundf(tY)); 
     CGDisplayMoveCursorToPoint(CGMainDisplayID(),target); 

    } 


    return event; 
} 




int 
main(int argc, char *argv[]) { 


    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init]; 

    stuff *stuff_doer = [[stuff alloc] init]; 

    NSBitmapImageRep *mouse_mask= [stuff_doer get_mouse_mask]; 


    CFRunLoopSourceRef runLoopSource; 
    CGEventMask event_mask; 
    event_mask = CGEventMaskBit(kCGEventMouseMoved) | CGEventMaskBit(kCGEventLeftMouseDragged) | CGEventMaskBit(kCGEventRightMouseDragged) | CGEventMaskBit(kCGEventOtherMouseDragged); 

     CGSetLocalEventsSuppressionInterval(0); 

    CFMachPortRef eventTap = CGEventTapCreate(kCGHIDEventTap, kCGHeadInsertEventTap, 0, event_mask, mouse_filter, mouse_mask); 

    if (!eventTap) { 
     NSLog(@"Couldn't create event tap!"); 
     exit(1); 
    } 

    runLoopSource = CFMachPortCreateRunLoopSource(kCFAllocatorDefault, eventTap, 0); 

    CFRunLoopAddSource(CFRunLoopGetCurrent(), runLoopSource, kCFRunLoopCommonModes); 

    CGEventTapEnable(eventTap, true); 

    CFRunLoopRun(); 

    CFRelease(eventTap); 
    CFRelease(runLoopSource); 
    [pool release]; 

    exit(0); 
} 

这是可能被使用的区域位图的示例中，黑色是允许的区域。 这说明了为什么转换为多边形不方便或者甚至是合理的。

Answer 1

一些想法：

• 相当标准的做法，以表格的问题：“给定一组2D点S的（在你的情况下，设置的边缘点），和查询点P（在你的情况下，鼠标位置），找到P中最靠近S的点“，就是使用四叉树。它们可以被看作是二进制搜索到二维的一种普遍化。 Quadtrees在电子游戏中受到碰撞检测的欢迎，所以你可以在谷歌找到很多教程。

• 形状是否改变或是静态的？在第二种情况下，如果内存不是问题，我只是预先计算每个像素的最近边缘点并将其放入查找表中。 （实际上，我只使用两个数组，一个用于x坐标，另一个用于y坐标）。冗余计算可以通过使用Floyd-Warshall算法中的某些东西来消除，在这种情况下，它具有非常简单的形式。

Answer 2

我认为详细的问题不是很简单（至少如果你想效率&精度）。有传言说Qt Graphics View做得很好。也许使用它，或者看一看它的源代码（它是免费软件）应该会有帮助吗？

Answer 3

如果用户正在移动鼠标指针并需要被限制到某个区域，那么我认为最好的解决方案不是找到该区域内的最近点。相反，用户看起来更直观的是在退出时将鼠标带回到有效区域。如果您可以以足够快的速度监视鼠标位置，这将更容易实现。

现在，您可能有理由按照您想要的方式去做，我尊重这一点。在这种情况下，我可以建议以下思路：

1. 如果你可以改变有效鼠标区域由一个位图定义为一个多边形（即标志着该地区的角落2D点的列表）的方式那么任务变得更简单。只需找到最接近鼠标位置的段即可。作为该计算的一部分，您可以获得该段内最近的点，这就是您想要重新定位鼠标指针的位置。

2. 蛮力解决方案也应该工作。从当前鼠标位置开始，向外发展。首先检查它周围的八个像素。然后在8点左右，等等。一旦找到有效区域内的点，记录它到当前鼠标位置的距离。继续前进，仍在寻找更近的像素，或者直到当前外层的所有像素的距离都大于最小记录距离。

我希望这有助于。