I haven't come across a library method ... or potted solution to the problem. I think that the reason is that the problem is fundamentally impossible to solve exactly.
The GeneralPath
class inherits a method called getPathIterator
from Shape2D
. If you look at the javadoc, you will see that the PathIterator
object models the path as a sequence of straight line segments. And the getPathIterator
method takes a flatness
parameter specified as follows:
"flatness - the maximum distance that the line segments used to approximate the curved segments are allowed to deviate from any point on the original curve."
Now, if the shape you are looking at consists of straight line segments, there is a good chance that the path iterator will give you those line segments. But if the shape has curved segments, then the line segments are only an approximation. And it is clearly impossible to test if a point is exactly on a boundary if you don't know what the exact boundary is.
Even assuming that the line segments exactly model the real curve, you still have the problem that (except for special cases), most of the points on the real curve cannot be represented exactly using Java primitive datatypes (int, double, etc). So once again "exactness" is problematic.
I think that the best you can hope for is to test whether your point is within some small delta of the boundary ... and choose a flatness
value that is less than that delta, iterate the path line segments, and test the tangential distance of the point from each segment.
Note: if you make flatness
very small, you can expect to have to test a very large number of line segments. I don't think there is any way around this computational concern while sticking to the GeneralPath API.
If you restrict the problem to true (i.e. straight-sided) polygons, then you simply need to iterate the line segments, and for each one test to see if the distance from the point to the line is less than some suitable epsilon. This Wikipedia entry gives you the mathematics. Note that exactness is still going to be a concern here ...
You don't have an enormously costly computation, but computing an accurate square-root doesn't come for free, and you have to do it up to N times for an N-sided polygon.
Doing better than that (i.e. getting better than O(N)
) is going to be difficult. However, if the polygon is fixed and you are going to be testing a huge number of points against it, then you could consider using a pre-computing a quad-tree data structure to do the resolution. Precomputing the quad-tree will be expensive, but if N is large enough testing a a point will be cheaper. (Roughly O(log(1/epsilon))
in the worst case, instead of O(N)
on average. And the further away from the boundary a point is, the cheaper the answer.)
But as I said, quad-trees will only help in limited situations ...