Checking for mouse over irregular shapes

[nevon]

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.

[pekka]

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!

[nevon]

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 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.

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]

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.

[vrld]

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 point-in-polygon 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 = x2-x1, y2-y1 -- vector: edge start to edge end
    local rx, ry = px-x1, py-y2 -- vector: edge start to point
    return qx * ry - qy * rx >= 0
end

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.

[nevon]

This is actually a rather hard problem known as point location.

Ah, thank you. It was rather hard to find any resources regarding the problem, when I didn't even know what it was called.

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.

I'm going with this for now. Making all the polygons is a bitch, but hopefully it'll be easier than the other alternatives.

The point-in-polygon 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 = x2-x1, y2-y1 -- vector: edge start to edge end
    local rx, ry = px-x1, py-y2 -- vector: edge start to point
    return qx * ry - qy * rx >= 0
end

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.

[kikito]

Maybe you overlooked my post - I think you really should give a look at using shapes and the testPoint function.

[nevon]

Maybe you overlooked my post - I think you really should give a look at using shapes and the testPoint function.

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.

[ljdp]

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

[vrld]

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 right-of-test:
The cross product of two vectors will return a vector that is orthogonal to the vectors. As this is not possible for two 2D-vectors, you have to "lift them one dimension higher", into the third dimensions:

jAj02.png (7.88 KiB) Viewed 450 times

To do this, you set the z-component of your 2D-Vectors to a fixed number, in our case 0 is just fine. The cross product of two 3D-Vectors 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]

But as we set the z component to zero, this becomes:

Code: Select all

[X]   [        0        ]
[Y] = [        0        ]
[Z]   [x1 * y2 - x2 * y1]

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:

2gbUa.png (4.4 KiB) Viewed 450 times

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 polygon-test, treat your monitor as the x-y-plane:

1vFxk.png (28.01 KiB) Viewed 450 times

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:

g0Fy3.png (3.85 KiB) Viewed 450 times

Hope that helped.