One solution is to split the concave polygon into convex segments then use cobbal's link.
Since you really have two different fundamental problems, have you considered other alternatives to the hit test problem, such as using a BSP tree? You can speed that up further by laying a grid over the poly and constructing a BSP tree for each grid square. Or a kd-tree with at most one edge in each leaf?
Edit: I'll ellaborate on the kd-tree (out of boredom, even if it might be of any use to anyone):
kd-trees have the following properties:
- They are binary
- Each non-leaf node splits space along a plane perpendicular to an axis, one side per child. E.g. root splits space into x < x0 and x >= x0
- Tree levels take turns splitting along different axes, e.g. level 0 (root) splits perpendicular to X, level 1 -> Y, etc.
To use this for the polygon hit detection, construct the tree as follows:
- Pick a vertex to split along. (Preferrably somewhere close to middle for a balanced tree).
- Split other vertices into two sets, one for either side of the split. The above vertex doesn't go into either set.
- Place edges into the sets as well. Any edge that intersects the split line goes into both sets.
- Construct children recursively from the above groups.
If the split vertex is chosen appropriately, the tree should have depth close to log(N), where N is the number of vertices. Each leaf node will have at most one edge going through it. To do the hit detection:
- Find the leaf that the point falls into.
- If there's an edge in the leaf, compare point to it. If not, it should be obvious whether the point is inside or outside (store this information in such leaves when constructing the tree).
