How to determine the nearest mouse point on a specific shape?

Question

I created a program that limits the mouse to a specific area based on a black and white bitmap. The program is 100% functioning as it is, but uses an inaccurate, albeit quick, algorithm to change the position of the mouse when it goes outside the area.

Currently, when a mouse moves outside an area, basically the following happens:

• A line is drawn between the specified static point inside the area and the new mouse position.
• The point at which this line intersects the edge of the allowed region is found.
• The mouse moves to this point.

It works, but it only works for a perfect circle with a given point set in the exact center. Unfortunately, this will never happen. The application will be used with various rectangles and irregular amorphous shapes. On such shapes, the point where the line drawn intersects the edge is usually not the closest point to the mouse shape.

I need to create a new algorithm that will find the closest point to the new mouse position on the edge of the allowed area. How can i do this? Preferably, the method is performed fast enough to ensure smooth movement of the mouse while dragging the mouse to the edge of the area.

(I do this in Objective C / Cocoa in OS X 10.7, however, pseudo code is fine if you don't want to enter code or don't know Objective C / C)

Thanks!

Here is my current algorithm:

#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:xy: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 OK 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); } 

This is an example of a bitmap image of a region that can be used, black is a valid region. This shows why conversion to a polygon would not be convenient or even believable.

Answer 1

Some ideas:

• A fairly standard approach to form tasks: "given the set of two-dimensional points S (in your case, the set of edge points) and the query point P (in your case, the position of the mouse), find the nearest point to S in P" - use the quadrant. They can be considered as a generalization of binary search in 2D. Quadtrees are popular for collision detection in video games, so you can find many tutorials on google.

• Is the shape changed or is it static? In the second case, if memory is not a problem, I would just precommute the nearest edge point for each pixel and put it in the lookup table. (In practice, I just used two arrays, one for the x coordinate and the other for the y coordinate). Backup calculations can be eliminated by using something along the lines of the Floyd-Warsall algorithm, which in this case has a rather simple form.

Answer 2

If the user moves the mouse and should be limited to a certain area, then I do not think that the best solution is to find the nearest point within the region. Instead, what will seem more intuitive to the user is to return the mouse to the actual area at the time of its exit. This is much easier to implement if you can control the position of the mouse at a fairly high speed.

Now you may have reasons to do it the way you want to do it, and I respect that. In this case, I can offer the following ideas:

• if you can change the way you determine the valid mouse region from a bitmap to a polygon (a list of two-dimensional points that mark the corners of the region), then the task becomes much simpler. Just find the segment closest to the mouse position. As part of this calculation, you can get the closest point in this segment, and that is where you want to move the mouse pointer.

• a rude decision should work. Start at your current mouse position and navigate your way out. First check the eight pixels around it. Then 16 around 8 and so on. As soon as you find a point inside the valid area, write down its distance to the current position of the mouse. Continue moving looking for closer pixels, or until all pixels at the current outer level have a distance greater than your smallest recorded distance.

Hope this helps.

Answer 3

I think that in detail the problem is not very simple (at least if you need efficiency and accuracy). Qt Graphics View is rumored to do a good job of this. Perhaps using it or taking a look at its source code (this is free software) should be useful?