[SciPy-user] Triangulation of L-shaped domains

[Stefan van der Walt]

Hi John

On Mon, Sep 04, 2006 at 09:31:51PM -0500, John Hunter wrote:
>     Robert> Raycast with simulation of simplicity to handle degeneracy
>     Robert> is probably your best bet.
> 
>     Robert>
>     Robert> http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
> 
>     Robert> John's "add up the angles" approach is not really a good
>     Robert> one. I frequently find it referred to in the literature as
>     Robert> "the worst thing you could possibly do."  :-)
> 
> OK, I could only stand Robert's taunt for so long.  I added the pnpoly
> routine to matplotlib svn extension code: there is a function to test
> whether a a single x, y point is inside a polygon
> (matplotlib.nxutils.pnpoly) and a function which takes a list of
> points and returns a mask for the points inside
> (matplotlib.nxutils.points_inside_poly).  When profiling against my
> original "worst thing you could possibly do" implementation, this new
> version is 15-35 times faster, in addition to being a better algorithm
> in terms of handling the degenerate cases.  It is also considerably
> faster than the pure numpy pnpoly implementation, since it avoids all
> the temporaries and extra passes through the data of doing things at
> the numeric level.

I am glad to see this included.  The python implementation is my first
choice, but if you are looking for speed specifically, I also wrote
weave and ctype versions.

Regards
Stéfan