[metapost] point "inside" cycle

[mskala at ansuz.sooke.bc.ca]

On Mon, 22 Apr 2013, Troy Henderson wrote:
> Does MetaPost have a clever way of determining whether a point z is "inside"
> a closed path (cycle) p?

I don't think there's any easy way that will always be correct.

You can approximate it by testing whether the point is inside the bounding
box of the curve - that is often correct, but of course, not always.

You can draw a path (maybe just a single straight line segment) from z to
some other point that you know is outside; then test whether the new path
intersects with p.  That is very often correct, especially if you check
the bounding box first and maybe try it more than once with a couple of
different known-outside points.  However, it's still vulnerable to false
positives in the case of p being very complicated.

To really get it right you have to first define what you think the "right"
answer actually is; it's not obvious what should or shouldn't count in the
case of self-intersecting figure-8 kinds of curves.  I don't know of a
nice clean simple solution.  Most people make do with approximations.

-- 
Matthew Skala
mskala at ansuz.sooke.bc.ca                 People before principles.
http://ansuz.sooke.bc.ca/