Verifying an n-point polygon

*To*: mathgroup at smc.vnet.net*Subject*: [mg111978] Verifying an n-point polygon*From*: skidmarks <aschwarz at acm.org>*Date*: Mon, 23 Aug 2010 02:37:59 -0400 (EDT)

The definition I need satisfied is: "Accept an n-sided polygon containing no crossing lines." The polygon need not be convex. I have found that the sum of the interior angles = (n - 2) * 180 is necessary but not sufficient. I can detect whether any three sides are convex or concave, but I have no easy understanding of how to detect line crossing. I conjecture that if I form a convex polygon by excluding points which form concave regions, and then see if the excluded points are inside the convex polygon then that would be sufficient. I don't have the skill to determine whether this is accurate nor an easy way to check inclusiveness of a within a polygon. Can anyone point me in the right direction? Text books or relevant articles are fine. Algorithms are better. Code is best (I'm coding in Java but C/C++ or Fortran, may others, are fine). At the end, I'd like to understand what has been done and the reasoning so that I can "do it by myself". thanks art