KevLinDev Blog

I’ve started to implement the Bentley-Ottmann algorithm which is used to fairly efficiently identify all intersection points between a set of lines. I’ll be using it to improve my current brute-force polygon-polygon intersection code.

I finished up a close variant of Bentley-Ottmann today: the Shamos-Hoey algorithm. As a result of that work, I had to improve my Red-Black Tree implementation. You can find the latest implemenation of my JavaScript Red-Black Trees here on my Utilities page.

I found out that there are some special cases that Bentley-Ottmann doesn’t handle correctly. I think I’ve found a good solution to all of those exceptions. Once I feel the code is reasonably correct, I’ll post it to the site.

Literally for years now, I’ve been wanting to implement a polygon intersection algorithm that I first found at Geometry Algorithms. Well, I made the first step last weekend and implemented a Red-Black Tree in JavaScript. That can be found on my Utilities page.

Admittedly, the Red-Black Tree example is not that interesting, but it served its purpose of making sure my code was behaving properly. I’m hoping that I’ll get to the fun stuff this weekend and actually have a better polygon-polygon intersection algorithm running on my site soon…after that, boolean operators.

Jan-Klaas Kollhof was kind enough to point out a huge inefficiency in my Base64 encoder. I was concatenating strings as opposed to pushing strings onto an array and then joining at the end. Shame on me…I know better than that. I’ve updated the code and it appears to be at least one order of magnitude faster.

Thanks Jan!