Geometry Algorithm Difficulties

In implementing the geometry algorithms the largest problem I’ve had is overcoming the fact that floating point numbers are not numbers. This issue crops up in most of the lower level algorithms such as testing if a point is inside a polygon or doing the boolean difference of two polygons etc.

The solution is to use a fuzzy representation of polygons. That is if a point is within \epsilon of a polygon then it is inside the polygon. This method works fairly well and can be implemented but:

1. I didn’t write my functions using this method from the beginning so I’ve had to gradually retrofit my functions which is a pain and is fairly difficult because testing becomes a nightmare.

2. The implementation itself can be a bit tricky. In point of fact the selection of \epsilon depends on the scale of a polygon (e.g. If the edges of a polygon have length 1000 then \epsilon should be larger than when a polygon has edges of length 0.001)

For the above two reasons I’ve been contemplating using CGAL for implementation of low level functions. The only troubles are I’d need to rewrite my high level algorithms in C++ and debugging/testing algorithms in Python is much much better than C++.

That’s my current quandary. As of now I’m still hacking on the Python code and fixing bugs but I’ve also created a Subversion branch for future C++ development using CGAL.

Advertisements

One thought on “Geometry Algorithm Difficulties

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s