# Which of these algorithms is best for my goal?

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:

1. A line is drawn between a pre-defined static point inside the region and the mouse's new position.
2. The point where that line intersects the edge of the allowed area is found.
3. 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;

// 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;

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];

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

-
Is there some reason you can't make use of the previous position of the mouse? Assuming the mouse is already in the valid area, can you evaluate a new position for the mouse and, if not in the area, keep the previous position of the mouse? If position updates are small moves, this should leave the mouse at the edge of the area when attempted to be moved outside it. – mgkrebbs Nov 22 '11 at 8:11
There are a couple of issues with that: A. the mouse can be moved at very fast rates, if I flick my mouse across the mouse pad as if I were going to jump from the windows start button to the exit button of a window, I can get it to jump something like 200 pixels between position updates. Issue B. I need the user to be able to move the mouse along the edge of the area smoothly, jumping it back to its previous position would keep it in one spot if the user tried to move outwards from the area at an angle (I would want it to move along the edge, but in the direction of that angle.) – JonathonG Nov 22 '11 at 8:30
This is just a quick thought, but how about instead of one static point, you use two static points. You could do a hit test based on if the mouse is closer to one point or the other? That way, instead of being bound by a circle, it would be bound by an oval, and you'd be able to make a better judgment call over where the mouse is bound to. – Tyanna Nov 22 '11 at 15:52

Assuming you have a reliable way to gather a discrete number of (x, y) points describing the border of your image, I would try using a combination of your first and third methods.

In which case, this is a classic example of computational geometry:

http://en.wikipedia.org/wiki/Closest_pair_problem#Planar_case

EDIT

Since one of your points is fixed, you may even be able to reduce the runtime to O(n) by just linearly stepping over your border points, computing the distance, e.g. distance = sqrt((x1-x2)^2 + (y1-y2)^2), and keeping track of the point who produced the minimum.

Perhaps there is some clever way to optimize the search over your border points?

All analytical methods I can imagine rely on your border points being representative of some continuous function, which they are not necessarily.

EDIT2

Of course, you should not be going into this search algorithm whatsoever unless your `is_in_area` routine fails.

-
I did this, my algorithm maps the border pixels into an array. I've tried just checking against every single one of them for the closest. Suprisingly, this actually works even though there are 2100 of them. You don't actually have to take the sqrt, becuase just adding (x1-x2)^2 + (y1-y2)^2 is enough information to determine which point is CLOSEST, you just don't know the actual distance. However, it runs a little funky. I've created an accuracy interval that lets me scale how many points on the border are actually mapped (leaving gaps inbetween them). – JonathonG Nov 23 '11 at 19:19
I think I could optimize the search if I stored the border points in the array in a contiguous order. Currently my mapping algorithm just scans the screen 1 pixel at a time checking if it has any directly adjacent white pixels, if it does, it's added to the array. This results in a rather scattered ordering of the points, but I could run through the array and re-order them based on contiguity. This would allow me to search from the pixel my original line-mapping method comes up with, and perhaps only search the nearest 100 border items, or something of that nature. – JonathonG Nov 23 '11 at 19:34

What about to remember last point when the mouse was inside and cast rays to that point but also rotated by 1, 2, 4, 8, ... degrees to both sides? Then select the nearest point at the intersection of the egde if the result is too coarse, you can repeat the procedure to "fine-tune it", now starting with the nearest point found, not with the last inside position.

-
If you see my comment on ardnew's answer, I've accomplished the border mapping. HOWEVER, it is behaving very strangely. Even if I reduce the number of border pixels to something like 50, it still launches the mouse all over the place for a split second on every mouse move... (I can draw a line and calculate the intersection point 2000 times per mouse move without visible lag, so 50 is WAY less than it needs to be in the first place.) – JonathonG Nov 23 '11 at 19:22
because I'm having problems with the border mapping, I might end up doing the raycasting method because I've done some tests and, as I said, I can cast up to 2000 rays per mousemove (this happens so fast that it looks perfeclt smooth even when you're launching the mouse around the page) . I figure that casting maybe 20 rays per side of the line is good, and then doing it again with the new point, repeated until there are no closer points found than the active one. – JonathonG Nov 23 '11 at 19:24

I have another idea. You could use a variant of your third approach. Map the border of the shape and use all this points to calculate the balance point of the figure. Once you have the balance point you can easily use it to create a line between the balance point and the mouse point to create a line. From this line you calculate the intersection with the shape.

-
What is the balance point? – JonathonG Nov 23 '11 at 19:20
the middle of the shape. I used a dictionary to translate it from German. I'll see if I find the correct term. – RoflcoptrException Nov 23 '11 at 19:23
It's called Centroid in English. Sorry. en.wikipedia.org/wiki/Centroid – RoflcoptrException Nov 23 '11 at 19:24
Thank you for helping me out! This would probably work reasonably well compared to just pre-defining a static point manually. However the more straight lines along the edge of the figure, the worse accuracy it would have. (Think rectangle. I would still be getting the same results as now.) – JonathonG Nov 23 '11 at 19:25
This would be a way to improve my current method though. – JonathonG Nov 23 '11 at 19:35