{"id":1121,"date":"2019-11-10T03:11:27","date_gmt":"2019-11-10T03:11:27","guid":{"rendered":"https:\/\/muthu.co\/?p=1121"},"modified":"2021-05-24T02:39:48","modified_gmt":"2021-05-24T02:39:48","slug":"find-clusters-of-collinear-points-from-a-given-set-of-data-points","status":"publish","type":"post","link":"http:\/\/write.muthu.co\/find-clusters-of-collinear-points-from-a-given-set-of-data-points\/","title":{"rendered":"Find clusters of collinear points from a given set of data points"},"content":{"rendered":"\n<p>A set of 3 or more points are said to be collinear if they all lie on a straight line as shown in the image below.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><a href=\"https:\/\/muthu.co\/wp-content\/uploads\/2019\/11\/Snip20191109_42.png\"><img loading=\"lazy\" decoding=\"async\" width=\"562\" height=\"448\" src=\"https:\/\/muthu.co\/wp-content\/uploads\/2019\/11\/Snip20191109_42.png\" alt=\"collinear points\" class=\"wp-image-1204\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2019\/11\/Snip20191109_42.png 562w, http:\/\/write.muthu.co\/wp-content\/uploads\/2019\/11\/Snip20191109_42-300x239.png 300w\" sizes=\"(max-width: 562px) 100vw, 562px\" \/><\/a><\/figure><\/div>\n\n\n\n<p>One common way of checking if three points are collinear is by finding the area of the triangle formed by the points. The area will be zero if the points are collinear.<\/p>\n\n\n\n<p class=\"has-text-align-center\">Area(A,B,C) = 0<\/p>\n\n\n\n<p>Another way is to see if the angle formed by the three points is 180 degrees which is what I used in my number plate segmentation algorithm described in this <a href=\"https:\/\/muthu.co\/algorithm-for-detecting-and-extracting-number-plates-from-images-of-cars\/\">article<\/a>. Using the angle to find the collinearity also gives us the advantage of using intervals like:<\/p>\n\n\n\n<p class=\"has-text-align-center\">[175,185] = { angle \u2208 \u211d&nbsp; | 175 &lt;= angle &lt;=185}<\/p>\n\n\n\n<p>The interval can help us find almost collinear points as shown in the image below.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><a href=\"https:\/\/muthu.co\/wp-content\/uploads\/2019\/11\/untitled-1.jpg\"><img loading=\"lazy\" decoding=\"async\" width=\"340\" height=\"148\" src=\"https:\/\/muthu.co\/wp-content\/uploads\/2019\/11\/untitled-1.jpg\" alt=\"characters collinear\" class=\"wp-image-1205\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2019\/11\/untitled-1.jpg 340w, http:\/\/write.muthu.co\/wp-content\/uploads\/2019\/11\/untitled-1-300x131.jpg 300w\" sizes=\"(max-width: 340px) 100vw, 340px\" \/><\/a><\/figure><\/div>\n\n\n\n<p>But what about finding more than 3 points which are collinear. In this post, I will describe a good way of identifying all the clusters of collinear points in a cartesian plane using the line equation.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Algorithm<\/h2>\n\n\n\n<ul><li>initialize an array L to hold hash of line equations<\/li><li>initialize an array CL to holding clusters of lines<\/li><li>for all distinct points A, B\n<ul>\n<li>compute the line equation <em>y=mx+c<\/em> where m is slope and c is the intercept<\/li>\n<li>find the hash of the line equation <em>f(x)<\/em>, check if <em>hash(f(x))<\/em> already in L, do not proceed if already present else add it to array <em>L<\/em><\/li>\n<li>initialize an array <em>LINE<\/em> and add A, B into it.<\/li>\n<li>for all points <em>C(x<sub>3<\/sub>,y<sub>3<\/sub>)&nbsp; \u2260 {A, B}<\/em>\n<ul>\n<li>check if <em>y<sub>3<\/sub><\/em>-m<em>x<sub>3<\/sub><\/em>-c = 0, then add C to array LINE as it belongs to the same line<\/li>\n<\/ul>\n<\/li>\n<li>if the length of LINE &gt; 2, that it contains more than A, B\n<ul>\n<li>add the line into CL<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li><\/ul>\n\n\n\n<p>The algorithm complexity is less than O(n3) because of the use of hash function.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Implementation<\/h2>\n\n\n\n<p>The entire notebook implementation can<a href=\"https:\/\/github.com\/muthuspark\/ml_research\/blob\/master\/finding%20cluster%20of%20collinear%20points.ipynb\"> be found here. <\/a><\/p>\n\n\n\n<p>Let the points be:<\/p>\n\n\n\n<pre class=\"wp-block-code EnlighterJSRAW has-small-font-size\"><code>points = np.array(&#91;&#91;42,71],&#91;65,10],&#91;61,23],&#91;46,47],&#91;56,77],&#91;62,44],&#91;78,23],&#91;75,3],&#91;72,4],&#91;43,33],&#91;7,67],&#91;43,22],&#91;88,34],&#91;79,56],&#91;82,36],&#91;56,27],&#91;79,97],&#91;50,26],&#91;1,33],&#91;31,20],&#91;62,16],&#91;15,26],&#91;28,39],&#91;5,52],&#91;78,62],&#91;5,29],&#91;90,3],&#91;61,37],&#91;4,48],&#91;90,14],&#91;59,72],&#91;68,28],&#91;41,90],&#91;63,98],&#91;31,84],&#91;66,14],&#91;78,91],&#91;0,35],&#91;91,98],&#91;43,99],&#91;33,62],&#91;24,99],&#91;77,6],&#91;11,14],&#91;25,62],&#91;53,12],&#91;83,1],&#91;72,66],&#91;44,72],&#91;60,45],&#91;78,62],&#91;85,90],&#91;67,18]])<\/code><\/pre>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><a href=\"https:\/\/muthu.co\/wp-content\/uploads\/2019\/11\/points.png\"><img loading=\"lazy\" decoding=\"async\" width=\"434\" height=\"415\" src=\"https:\/\/muthu.co\/wp-content\/uploads\/2019\/11\/points.png\" alt=\"points on cartersian p;ane\" class=\"wp-image-1207\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2019\/11\/points.png 434w, http:\/\/write.muthu.co\/wp-content\/uploads\/2019\/11\/points-300x287.png 300w\" sizes=\"(max-width: 434px) 100vw, 434px\" \/><\/a><\/figure><\/div>\n\n\n\n<p>The implementation of the algorithm described above:<\/p>\n\n\n\n<pre class=\"wp-block-code EnlighterJSRAW has-small-font-size\"><code># get the y=mx+c equation from given points\ndef get_slope_and_intercept(pointA, pointB):\n    slope = (pointB&#91;1] - pointA&#91;1])\/(pointB&#91;0] - pointA&#91;0])\n    intercept = pointB&#91;1] - slope * pointB&#91;0]\n    return slope, intercept\n\n# a simple algorithm to find the hash of slope and intercept\ndef get_unique_id(slope, intercept):\n    return str(slope)+str(intercept)\n    \nlines = &#91;]\nhash_table = &#91;]\nfor A in points:\n    for B in points:\n        if A&#91;0] != B&#91;0] and A&#91;1] != B&#91;1]: #not matching the same points\n            #find the equation of line\n            slope, intercept = get_slope_and_intercept(A, B)\n            line = &#91;A, B]\n            unique_hash = get_unique_id(slope, intercept)\n            if unique_hash not in hash_table:\n                hash_table.append(unique_hash)\n                for C in points:\n                    if B&#91;0] != C&#91;0] and B&#91;1] != C&#91;1] and A&#91;0] != C&#91;0] and A&#91;1] != C&#91;1]:\n                        # check if this point lies on the same line as A and B\n                        # y - mx - c = 0\n                        rhs = C&#91;1] - slope * C&#91;0] - intercept\n                        if rhs == 0:\n                            line.append(C)\n                # finally append whatever is found to be in one line, more than 2 points\n                if len(line) &gt; 2:\n                    lines.append(line)<\/code><\/pre>\n\n\n\n<p>The output for our dataset is:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><a href=\"https:\/\/muthu.co\/wp-content\/uploads\/2019\/11\/collinear-points.png\"><img loading=\"lazy\" decoding=\"async\" width=\"434\" height=\"415\" src=\"https:\/\/muthu.co\/wp-content\/uploads\/2019\/11\/collinear-points.png\" alt=\"collinear points\" class=\"wp-image-1208\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2019\/11\/collinear-points.png 434w, http:\/\/write.muthu.co\/wp-content\/uploads\/2019\/11\/collinear-points-300x287.png 300w\" sizes=\"(max-width: 434px) 100vw, 434px\" \/><\/a><\/figure><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A set of 3 or more points are said to be collinear if they all lie on a straight line as shown in the image below. One common way of checking if three points are collinear is by finding the area of the triangle formed by the points. The area will be zero if the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":1208,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,32],"tags":[54,58],"_links":{"self":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1121"}],"collection":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/comments?post=1121"}],"version-history":[{"count":3,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1121\/revisions"}],"predecessor-version":[{"id":1853,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1121\/revisions\/1853"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media\/1208"}],"wp:attachment":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media?parent=1121"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/categories?post=1121"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/tags?post=1121"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}