[SciPy-user] Triangulation of L-shaped domains

[Robert Kern]

Rob Hetland wrote:
> 
> I have a feeling that there *might* be a way to tease out which 
> triangles are inside the set of points you give, and which are outside.  
> However, I have to say, that I thought about this for a while, and then 
> gave up.

It wouldn't necessarily work. The Delaunay triangulation performed by 
scipy.sandbox.delaunay is not constrained to require the edges of your 
non-convex boundary. But supposing you did have a constrained Delaunay 
triangulation, you could pick a triangle that is known to be outside and then 
push its neighbors onto a stack if the edge that joins them is not a boundary 
edge. Pop a triangle from the stack and repeat. (More or less; there are some 
details you need to fill in). You will have to put multiple "seed" triangles to 
initialize the stack if there are multiple "outside" regions (including holes!).

> More generally:  Is there a good utility for finding points inside an 
> arbitrary polygon?  I, for one, could really use such a utility.

Raycast with simulation of simplicity to handle degeneracy is probably your best 
bet.

   http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

John's "add up the angles" approach is not really a good one. I frequently find 
it referred to in the literature as "the worst thing you could possibly do."  :-)

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco