如何確定鼠標在某個形狀上的最近點？

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點左右，等等。一旦找到有效區域內的點，記錄它到當前鼠標位置的距離。繼續前進，仍在尋找更近的像素，或者直到當前外層的所有像素的距離都大於最小記錄距離。

我希望這有助於。