This is a well-studied problem, and your problem set many not even come into the category of "big" by the computational geometry mavens. Have you looked at PNPoly , Computational Geometry Algorithm Library or Graphic Gems? Another possibility would be to use a constrained Delaunay triangulation.

Of more relevance to Perl, writing a Perl extension is one way to go. I think that using a specialized computational geometry library is likely to be more satisfying, though. Try CGAL.