Checking for mouse over irregular shapes
 nevon
 Commander of the Circuloids
 Posts: 938
 Joined: Thu Feb 14, 2008 8:25 pm
 Location: Stockholm, Sweden
 Contact:
Checking for mouse over irregular shapes
I have a bunch of irregular shapes on the screen, and I want to be able to hover over them and click on them. If they were rectangles, circles or some other type of regular shape, it wouldn't be that complicated, but they aren't. So... How would I go about checking if the mouse is over a certain shape? I suppose I could divide the screen into a bunch of smaller rectangles and assign them to whatever shape is "above" them (the shapes don't move, and I know where they are), and then check the mouse position to see what rectangle it is hovering over  but that just makes me feel dirty inside.
Re: Checking for mouse over irregular shapes
First of all, making a grid that divides the space is actually a good solution. But you need to have some fancier logic to get the hit testing be pixel perfect inside the grid sections, or at leat reasonably close to pixel perfect anyway. I'll describe that a bit.
Are these shapes definable by a reasonable amount of line segments?
If so, you can use the following method. If you draw a line from the queried position to a place that is definitely outside the shape, you can tell a few things from the count of intersections between that line and the shape's defining line segments.
If you have no intersections at all, you must be outside the shape. If you have one, you are inside it. If you have two or more, you need to think a bit. There are different conventions here, but usually a good one is that if you cross the edge an even number of times, you were originally outside, otherwise inside.
Some complex shapes don't work with this rule, but in those cases you can subdivide them into simpler shapes that do follow this rule. There are actually conventions for dealing with common kinds of shapes with holes in them, and these are called winding rules. This is the first Google result:
http://www.noodlesoft.com/blog/2006/11/30/mmmdonuts/
There is also an important corner case to keep in mind. If you happen to draw the line so that it meets two line segments at their endpoints, your count may go off because of that. That case needs to be tested separately.
Useful way to pick the testing line is to have it parallel to one of the coordinate axes. This makes the intersection tests easy to write and they probably work quicker that way too. But as long as you don't have a huge mass of line segments, these intersections tests shouldn't cost you much time at all.
If you want a better explanation or some example code, do ask. I'm a bit too busy to write extra code now, but I can look into this soon. I am sure lot of other folks here can do this too.
P.S. If your shapes don't work with this kind of solution, you really need to tell us what shapes they are!
Are these shapes definable by a reasonable amount of line segments?
If so, you can use the following method. If you draw a line from the queried position to a place that is definitely outside the shape, you can tell a few things from the count of intersections between that line and the shape's defining line segments.
If you have no intersections at all, you must be outside the shape. If you have one, you are inside it. If you have two or more, you need to think a bit. There are different conventions here, but usually a good one is that if you cross the edge an even number of times, you were originally outside, otherwise inside.
Some complex shapes don't work with this rule, but in those cases you can subdivide them into simpler shapes that do follow this rule. There are actually conventions for dealing with common kinds of shapes with holes in them, and these are called winding rules. This is the first Google result:
http://www.noodlesoft.com/blog/2006/11/30/mmmdonuts/
There is also an important corner case to keep in mind. If you happen to draw the line so that it meets two line segments at their endpoints, your count may go off because of that. That case needs to be tested separately.
Useful way to pick the testing line is to have it parallel to one of the coordinate axes. This makes the intersection tests easy to write and they probably work quicker that way too. But as long as you don't have a huge mass of line segments, these intersections tests shouldn't cost you much time at all.
If you want a better explanation or some example code, do ask. I'm a bit too busy to write extra code now, but I can look into this soon. I am sure lot of other folks here can do this too.
P.S. If your shapes don't work with this kind of solution, you really need to tell us what shapes they are!
 nevon
 Commander of the Circuloids
 Posts: 938
 Joined: Thu Feb 14, 2008 8:25 pm
 Location: Stockholm, Sweden
 Contact:
Re: Checking for mouse over irregular shapes
I suppose they could be defined by line segments if need be, but I would like to avoid it if possible. The shapes I'm talking about are areas of the world, like on a Risk board. So there are a lot of rounded and strange edges that need to be dealt with.pekka wrote:First of all, making a grid that divides the space is actually a good solution. But you need to have some fancier logic to get the hit testing be pixel perfect inside the grid sections, or at leat reasonably close to pixel perfect anyway. I'll describe that a bit.
Are these shapes definable by a reasonable amount of line segments?
[...]
P.S. If your shapes don't work with this kind of solution, you really need to tell us what shapes they are!
I'm not finished with drawing the map yet, but as you can see, I might get better results from dividing the screen into a grid rather than trying to represent the areas with lines.
 kikito
 Inner party member
 Posts: 3153
 Joined: Sat Oct 03, 2009 5:22 pm
 Location: Madrid, Spain
 Contact:
Re: Checking for mouse over irregular shapes
Well, if you end up using polygons to represent the countries, Shape:testPoint will do the heavy lifting you, provided that you are willing to use the physics module.
One issue is that polygons must be concave and must have 8 sides or less. But then you can split the countries in multiple polygons.
One issue is that polygons must be concave and must have 8 sides or less. But then you can split the countries in multiple polygons.
When I write def I mean function.
Re: Checking for mouse over irregular shapes
This is actually a rather hard problem known as point location. Luckily, there are well known solutions to it.
One of them uses trapezoidal maps (look here: http://cgm.cs.mcgill.ca/~athens/cs507/P ... Kaartinen/), which is a rather fast algorithm:
With n being the number of edges, you can build the trapezoidal map in O(n logn) time (this needs only to be done once!)
The search is performed in O(logn) time, which for a large number of edges will be considerably faster than pekka's solution.
The grid approach is way easier to implement and will even be faster than trapezoidal maps, but it will also require a lot more memory.
A third solution may be this: Sorround your shapes by few simpler, convex polygons (like in the image attached). For every polygon, test if the mouse point is inside that polygon.
The pointinpolygon test is quite easy: For every edge of the polygon, look if the point is right of that edge using the cross product:
This will not be as fast as the trapezoidal map (O(n) time), but will not use as much memory as the grid. If you keep the polygons simple enough, this can be a good solution.
One of them uses trapezoidal maps (look here: http://cgm.cs.mcgill.ca/~athens/cs507/P ... Kaartinen/), which is a rather fast algorithm:
With n being the number of edges, you can build the trapezoidal map in O(n logn) time (this needs only to be done once!)
The search is performed in O(logn) time, which for a large number of edges will be considerably faster than pekka's solution.
The grid approach is way easier to implement and will even be faster than trapezoidal maps, but it will also require a lot more memory.
A third solution may be this: Sorround your shapes by few simpler, convex polygons (like in the image attached). For every polygon, test if the mouse point is inside that polygon.
The pointinpolygon test is quite easy: For every edge of the polygon, look if the point is right of that edge using the cross product:
Code: Select all
function rightOf(x1, y1, x2, y2, px, py)  x1/y1: start of edge, x2/y2: end of edge, px,py: point to test
local qx, qy = x2x1, y2y1  vector: edge start to edge end
local rx, ry = pxx1, pyy2  vector: edge start to point
return qx * ry  qy * rx >= 0
end
 Attachments

 map.jpg (20.98 KiB) Viewed 5855 times
 nevon
 Commander of the Circuloids
 Posts: 938
 Joined: Thu Feb 14, 2008 8:25 pm
 Location: Stockholm, Sweden
 Contact:
Re: Checking for mouse over irregular shapes
Ah, thank you. It was rather hard to find any resources regarding the problem, when I didn't even know what it was called.vrld wrote:This is actually a rather hard problem known as point location.
I'm going with this for now. Making all the polygons is a bitch, but hopefully it'll be easier than the other alternatives.vrld wrote:A third solution may be this: Sorround your shapes by few simpler, convex polygons (like in the image attached). For every polygon, test if the mouse point is inside that polygon.
Do you think you could explain how this works, more in depth? Math is not my strong suit, and I prefer understanding how something works, rather than just copypasting it.vrld wrote:The pointinpolygon test is quite easy: For every edge of the polygon, look if the point is right of that edge using the cross product:Code: Select all
function rightOf(x1, y1, x2, y2, px, py)  x1/y1: start of edge, x2/y2: end of edge, px,py: point to test local qx, qy = x2x1, y2y1  vector: edge start to edge end local rx, ry = pxx1, pyy2  vector: edge start to point return qx * ry  qy * rx >= 0 end
 kikito
 Inner party member
 Posts: 3153
 Joined: Sat Oct 03, 2009 5:22 pm
 Location: Madrid, Spain
 Contact:
Re: Checking for mouse over irregular shapes
Maybe you overlooked my post  I think you really should give a look at using shapes and the testPoint function.
When I write def I mean function.
 nevon
 Commander of the Circuloids
 Posts: 938
 Joined: Thu Feb 14, 2008 8:25 pm
 Location: Stockholm, Sweden
 Contact:
Re: Checking for mouse over irregular shapes
I didn't overlook it, but the mere mention of the physics module made me wet myself in fear. However, it does seem like it would be a fairly easy solution. Either way, I can go with that solution without making any modifications, as none of my polygons have more than 8 sides.kikito wrote:Maybe you overlooked my post  I think you really should give a look at using shapes and the testPoint function.
Re: Checking for mouse over irregular shapes
Googling for 'point in polygon' or '2d polygon collision' might yield some results. If you want concave polygons, things get complex. There's methods which split a polygon into triangles. One method I know of is called 'ear clipping'.
For simple polygons however this might help =]
http://locofilm.co.uk/lovesnips/Point_in_polygon
For simple polygons however this might help =]
http://locofilm.co.uk/lovesnips/Point_in_polygon
Re: Checking for mouse over irregular shapes
I think Shape:testPoint will do exactly the same: Test if the point is right of every edge in the polygon.
Anyway, for understanding the rightoftest:
The cross product of two vectors will return a vector that is orthogonal to the vectors. As this is not possible for two 2Dvectors, you have to "lift them one dimension higher", into the third dimensions:
To do this, you set the zcomponent of your 2DVectors to a fixed number, in our case 0 is just fine. The cross product of two 3DVectors is:
But as we set the z component to zero, this becomes:
Which was kind of expected, since the only way a vector can be rectangular to two vectors in a plane is to be orthogonal to that plane:
Note that there are still two possibilities: (a x b) can point "up" or "down". It points up, if x1*y2  x2*y1 >= 0.
In the polygontest, treat your monitor as the xyplane:
It is important that the polygon is convex though, otherwise a point inside the polygon might not be right of every line of the polygon:
Hope that helped.
Anyway, for understanding the rightoftest:
The cross product of two vectors will return a vector that is orthogonal to the vectors. As this is not possible for two 2Dvectors, you have to "lift them one dimension higher", into the third dimensions:
To do this, you set the zcomponent of your 2DVectors to a fixed number, in our case 0 is just fine. The cross product of two 3DVectors is:
Code: Select all
[X] [x1] [x2] [y1 * z2  y2 * z1]
[Y] = [y1] x [y2] = [z1 * x2  z2 * x1]
[Z] [z1] [z2] [x1 * y2  x2 * y1]
Code: Select all
[X] [ 0 ]
[Y] = [ 0 ]
[Z] [x1 * y2  x2 * y1]
Note that there are still two possibilities: (a x b) can point "up" or "down". It points up, if x1*y2  x2*y1 >= 0.
In the polygontest, treat your monitor as the xyplane:
It is important that the polygon is convex though, otherwise a point inside the polygon might not be right of every line of the polygon:
Hope that helped.
Who is online
Users browsing this forum: No registered users and 27 guests