# How to detect the presence one- and two-dimensional patterns in distributions of spatial points?

I have many point patterns, and I want to detect those patterns that have points arranged in lines that may be curved, intersected or broken. For example, on the following picture, the upper left pattern is not interesting but other three patterns are those that I want to detect.

Not all points in the interesting patterns are aligned. Some points in those patterns are still random. The lines do not have any parametric form, so I cannot use the Hough transform. I searched some literature on spatial statistics, for example this one and only found metrics for assessing spatial uniformity and detecting clusters such as the index of dispersion. Which metrics exist for detecting the presence of not only clusters but curved lines?

I also need to do the same analysis for three-dimensional points. How to detect those 3D patterns that have points roughly arranged in lines and surfaces that can be wiggly?

• interesting problem! Especially considering the probabilistic model beneath! Out of interest: have you tried throwing PCA at your problem? If that works for the very "linear" distribution in the bottom right, but not for the top right, maybe with locally chosen subsets of your points? Feb 14 at 10:48
• I am not an image processing expert but would guess that 2D and 3D correlations would be effective at detecting these as long as offset parameters are swept (such as rotation and gain). Further each reference pixel could be enlarged (with less weight at the perimeters) to allow for robust detection even in the presence of small localized offset variation for each pixels location (displacement noise). Feb 14 at 17:05
• Why don't you make a connected graph of the points by using a greedy algorithm. Just connect points to the nearest neighbor until the whole set of points are connected. (Add the shortest edges in order.) Then you could do some analysis on the graph. One measure would be checking the angles made. When there is a line or a curve, then angle stays similar.
– IanJ
Feb 14 at 20:02
• @MarcusMüller I did PCA after reading your comment. Thanks! Combining with clustering suggested in the answer found more or less flat/straight patterns. Mar 24 at 8:26
• @IanJ Applying graph theory. Thanks! As to angles: most of the data are 3D, many patterns with points arranged in curved surfaces. Mar 24 at 8:29

Another classic algorithm that can cluster points based on their geodesic structure rather than just the distance would be DBSCAN, choosing a suitable $$\epsilon$$ for your dataset as the points that belong to the pattern are rather close to each other. A more complex classical machine learning algorithm is ISOMAP, it can also cluster points that based on geodesic properties