Which of these algorithms is best for my goal?
- by JonathonG
I have created a program that restricts the mouse to a certain region based on a black/white bitmap. The program is 100% functional as-is, but uses an inaccurate, albeit fast, algorithm for repositioning the mouse when it strays outside the area.
Currently, when the mouse moves outside the area, basically what happens is this:
A line is drawn between a pre-defined static point inside the region and the mouse's new position.
The point where that line intersects the edge of the allowed area is found.
The mouse is moved to that point.
This works, but only works perfectly for a perfect circle with the pre-defined point set in the exact center. Unfortunately, this will never be the case. The application will be used with a variety of rectangles and irregular, amorphous shapes. On such shapes, the point where the line drawn intersects the edge will usually not be the closest point on the shape to the mouse.
I need to create a new algorithm that finds the closest point to the mouse's new position on the edge of the allowed area. I have several ideas about this, but I am not sure of their validity, in that they may have far too much overhead.
While I am not asking for code, it might help to know that I am using Objective C / Cocoa, developing for OS X, as I feel the language being used might affect the efficiency of potential methods.
My ideas are:
Using a bit of trigonometry to project lines would work, but that would require some kind of intense algorithm to test every point on every line until it found the edge of the region... That seems too resource intensive since there could be something like 200 lines that would have each have to have as many as 200 pixels checked for black/white....
Using something like an A* pathing algorithm to find the shortest path to a black pixel; however, A* seems resource intensive, even though I could probably restrict it to only checking roughly in one direction. It also seems like it will take more time and effort than I have available to spend on this small portion of the much larger project I am working on, correct me if I am wrong and it would not be a significant amount of code (100 lines or around there).
Mapping the border of the region before the application begins running the event tap loop. I think I could accomplish this by using my current line-based algorithm to find an edge point and then initiating an algorithm that checks all 8 pixels around that pixel, finds the next border pixel in one direction, and continues to do this until it comes back to the starting pixel. I could then store that data in an array to be used for the entire duration of the program, and have the mouse re-positioning method check the array for the closest pixel on the border to the mouse target position.
That last method would presumably execute it's initial border mapping fairly quickly. (It would only have to map between 2,000 and 8,000 pixels, which means 8,000 to 64,000 checked, and I could even permanently store the data to make launching faster.) However, I am uncertain as to how much overhead it would take to scan through that array for the shortest distance for every single mouse move event... I suppose there could be a shortcut to restrict the number of elements in the array that will be checked to a variable number starting with the intersecting point on the line (from my original algorithm), and raise/lower that number to experiment with the overhead/accuracy tradeoff.
Please let me know if I am over thinking this and there is an easier way that will work just fine, or which of these methods would be able to execute something like 30 times per second to keep mouse movement smooth, or if you have a better/faster method.
I've posted relevant parts of my code below for reference, and included an example of what the area might look like. (I check for color value against a loaded bitmap that is black/white.)
//
// This part of my code runs every single time the mouse moves.
//
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);
}
Here is "is_in_area(int x, int y)" :
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;
}
