# Point Pattern Analysis Algorithms

I'm looking for point pattern analysis algorithms and literature on point pattern analysis, online resources and book titles welcome. The topics may range from general descriptions of algorithms to concrete use cases in any field of research.

Update Jul 31, 15:54:

I'd be especially interested in local methods to detect linear features in point patterns. e.g. create road/track geometries from gps points.

-

Spatial Statistics is probably classic example here. Also Spatial Data Analysis offers solid overview

Statistical Methods for Spatial Data Analysis, Geospatial Analysis - a comprehensive guide and Geographic Information Analysis will give you nice overview as well.

Another, more practical oriented way to go would be to look at R. Have a look at CRAN spatial tasks view for general overview of resources. Most of the packages come with good documentation and examples.

There is a pretty good set of notes here, focusing mostly on spatstat package. Also Applied Spatial Data Analysis with R book might come handy.

-
Thanks! www.spatialanalysisonline.com looks like a great resource to get started. – underdark Jul 26 '10 at 23:01

I hate to trudge up the past, but I would suggest anyone interested in point pattern analysis in general to check out Ned Levine's references for the CrimeStat program. It is a huge reference for a wide variety of point pattern analysis aimed at laymen (its much more generalizable than to simply crime analysis). Programmers may also be interested in the libraries (all dll's) for the various programs implemented in Crimestat. I also agree people should check out the Geospatial Analysis online e-book already mentioned as well.

Although the routines in Crimestat will probably not be much help for identifying linear features in point patterns, it is definitely a good intro text for a boat-load of point pattern analysis techniques.

-

Two common point clustering methods are the Hierarchical clustering and the k-means clustering. See also on wikipedia.

If you are interested in the way spatial structures of points are perceived, have a look at the so-called "gestalt perception laws".

A concrete use case is in cartography. Spatial structures of map symbols have to be detected and assessed in order to be automatically represented in a proper way. This article gives the example of a method to detect alignments of map symbols in order to represent them at several smaller scales.

-
Thank you, especially for the article on alignments, really interesting! – underdark Jul 26 '10 at 22:53

This depends on whether you want to look at "global" or "local" point patterns? You probably need to give us more details of your problem space before you can get a good answer (unless this is just a homework question).

-
I'm looking for general knowledge mostly but I have one use case in mind where I'm looking for local point patterns representing line features, probably even extracting vector lines from point patterns. – underdark Jul 30 '10 at 11:33