MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Verifying an n-point polygon

  • To: mathgroup at
  • Subject: [mg111978] Verifying an n-point polygon
  • From: skidmarks <aschwarz at>
  • 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

At the end, I'd like to understand what has been done and the
reasoning so that I can "do it by myself".


  • Prev by Date: Re: Filling from x_1 to x_2
  • Next by Date: Re: NonLinearModelFit crash (restart) the mathematica (v7.0) kernel.
  • Previous by thread: Re: All componens different
  • Next by thread: Specifying absolute Tick lengths