Skip to main content

News

Topic: How PolygonCollision() came to be. (point in polygon explained with source) (Read 1706 times) previous topic - next topic

0 Members and 1 Guest are viewing this topic.
  • FBnil
  • [*][*]
How PolygonCollision() came to be. (point in polygon explained with source)
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/, 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.
  • Last Edit: June 07, 2015, 12:58:07 pm by FBnil

  • Fat Cerberus
  • [*][*][*][*][*]
  • Global Moderator
  • miniSphere Developer
Re: How PolygonCollision() came to be. (point in polygon explained with source)
Reply #1
Note that the crossing count algorithm only works reliably with simple polygons.  It breaks down in the presence of self-intersection.
miniSphere 5.3-beta1 (stable: 5.2.13) - Cell compiler - SSj debugger
forum thread | on GitHub