Summary

This week we continued to look at computational geometry. First, we mathematically defined lines (line-segments / polylines) and polygons, desribing a few different types of the latter. Next, the line sweep was introduced and a line sweep algorithm for polygon intersection was described. Line intersection is an important attribute to be able to compute for some spatial analysis algorithm, topology checking, and data validation (for example of contours). Next, we reviewed the area of basic geometries and introduced Green's Theorem for simple polygons. A GIS is most likley making use of Green's Theorem when computing polygon area. We concluded with a discussion of trees. A model widely used in computational geometry and 'under-the-hood' in GISystems. We demonstrated the creation of a kd-tree (binary tree) decomposing a point pattern into a new representation.

The goal of these two weeks was to very broadly cover some of the underlying mathematics of GISystems that leverage computational geometry. Computational geometry is a massive field spanning university and research laboratory Computer Science and Mathematics departments. For those of you interested in the types of questions that CG addresses I would definitely suggest digging deeper. CG is a remarkable field.

Additional References

*