In a world gone mad..

For the project mentioned in my previous post, I needed a way to ‘clip’ polygons. Polygons had to be intersected with a ‘bounding box/shape’ and they had to be triangulated.

I was faced with the decision to either implement one of the known algorithms, find a Ruby polygon clipper, use an external implementation, write a Ruby extension providing access to one of the available c/c++ implementations.

Performance is/was an issue. Geo data polygons can contain a large number of coordinates. And many polygons have to be processed.

I immediately dropped the idea of writing a pure Ruby implementation. Mainly because I’m new to Ruby and I don’t dig math at all.. :/

I found no Ruby implementation after a few hours of searching the web.

Then I started calling external implementations of ‘hgrd’, ‘gpc’ and some other polygon clippers via a primitive ‘exec’ call from Ruby. Obviously the performance was lousy. But I was able to deliver some first results quickly.

I also realized that there a huge differences in clipping quality. And I finally settled for the ‘GPC’ from Alan Murta: http://www.cs.man.ac.uk/~toby/alan/software/

After a few days I had to improve performance. So I started looking a ‘extending Ruby’.

I needed a few hours and a look at swig to finally ‘grok’ the way extending Ruby works. My first approaches – before swig – failed badly. I tried to map all ‘native’ objects’ to Ruby somehow, providing all functions somehow.. a total mess..

Looking at swig I was shocked by the ugly code. But at least I was able to derive some ideas. Interestingly enough, the swig code didn’t really work. It didn’t ‘understand’ the ‘pointers’ as ‘arrays’ used by the GPC. Or to be more precise: I didn’t understand how to tell swig what to do..

Anyway, after playing around with this code a few hours it finally clicked. It was then a matter of a few more hours to finish the extension using very simple – imho – code.

Here’s the code in case you’re interested:
http://www.berlinfactor.com/blogging/files/gpc_ruby.c

I should probably send this to Alan Murta. But for now it’s to ‘raw’. No index/error checking at all..

tfdj

Filed by The.French.DJ at 12:59 pm under Development,Ruby
2 Comments