Spherical forums

Sphere Development => Sphere General => Topic started by: FBnil on June 07, 2015, 12:55:28 pm

Title: How PolygonCollision() came to be. (point in polygon explained with source)
Post by: FBnil on June 07, 2015, 12:55:28 pm
Polygon() existed back in the old 1.5 version. But there was no easy way to detect if one polygon was touching another polygon. There also is no polygon editor. And so, nobody really used it.
Until I found a fast algorithm for http://www.visibone.com/inpoly/ (http://www.visibone.com/inpoly/), published in 97 in the Linux Journal. In fact, the article contains several of these algorithms and puts them somewhat side by side. The code is small, fast and brilliant. And fortunately, still around. And worth the read, so check the URL out.

At that moment in time, I was more concerned with writing good interface code, than understanding the algorithm, that is why in the sources you still can see this comment:

Code: [Select]
inside=!inside; // I nod and smile...


Yes. It is not always easy to "understand" the code. The focus and effort was more on following all JS guidelines to not leak memory (it does not leak). And getting all glue functions, documentation, testing, etc. together to add a function. At a mere 173 lines of code, it was the stepping stone for the much bigger sfxr sound generator, that was added later on.
Title: Re: How PolygonCollision() came to be. (point in polygon explained with source)
Post by: Fat Cerberus on June 07, 2015, 01:22:48 pm
Note that the crossing count algorithm only works reliably with simple polygons.  It breaks down in the presence of self-intersection.