Thanks to Boyko for the link http://erich.realtimerendering.com/ptinpoly/ with the old article. (1994).
It is fair to assume that Dan Bron, when asking the J Programming Forum "to check whether a point falls within an arbitrary polygon", wants a short J-program rather than optimized assembler code. The vertices of an "arbitrary polygon" does not have integer coordinates. -Bo --- Den tors 22/4/10 skrev Boyko Bantchev <[email protected]>: Fra: Boyko Bantchev <[email protected]> Emne: Re: [Jprogramming] Polygon containment Til: "Programming forum" <[email protected]> Dato: torsdag 22. april 2010 12.13 On 22 April 2010 09:59, Bo Jacoby <[email protected]> wrote: > Boyko Bantchev wrote: "The winding number method ... is computationally awful > and for this reason not much used." > > Nobody really knows how much it is used, I guess. If you mean a precise number of uses or users, then yes, ‘nobody really knows’. But do google for "worst algorithm in the world for testing points" and see who the champion is. > I find the winding number formula > W=.(%&0j2p1)@(+/)@:^.@(% _1&|.) > short and simple and computationally quite OK. > It is, (divided by 2 pi i), the sum of the logarithm > of the quotients between each corner and its predecessor. Angles? Quotients? Even logarithms? How is this simpler and more robust than only using addition and multiplication? Specifically, why should one, given integer coordinates, use complicated floating-point calculations to obtain the result? That would be both prone to errors and less efficient. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
