<\/a><\/figure><\/div>\n\n\n\nanchor_point = datapoints[0]\nfor _, point in enumerate(datapoints):\n if point[1] < anchor_point[1]:\n anchor_point = point\n elif point[1] == anchor_point[1] and point[0] < anchor_point[0]:\n anchor_point = point\nprint(anchor_point)<\/code><\/pre>\n\n\n\nStep 2: <\/h3>\n\n\n\nSort all the points based on the polar angle they make with the anchor point. If two points make the same angle with Anchor Point P, then sort it by distance from P<\/h4>\n\n\n\nfrom math import atan2\n\ndef polar_angle(p0, p1):\n y_span=p0[1]-p1[1]\n x_span=p0[0]-p1[0]\n return atan2(y_span,x_span)\n\n# find the angle\ndatapoints_angles = []\norigin = [0,0]\nfor _, point in enumerate(datapoints):\n datapoints_angles.append([point[0],point[1], polar_angle(anchor_point, point)])\n\ndatapoints_angles = np.array(datapoints_angles) \ndatapoints_angles = datapoints_angles[datapoints_angles[:,2].argsort()]\nsorted_datapoints = datapoints_angles[:,(0,1)]<\/code><\/pre>\n\n\n\nStep 3: <\/h3>\n\n\n\nInitialize the convex hull array with the anchor point and the first element in the sorted array.<\/h4>\n\n\n\nconvex_hull = [anchor_point, sorted_datapoints[0]]<\/code><\/pre>\n\n\n\nStep 4: Iterate over each point in the sorted array and see if traversing to a point from the previous two points makes a clockwise or a counter-clockwise direction. If clockwise then reject the point and move on to the next point. Continue this till the end of the sorted array.<\/h4>\n\n\n\ndef ccw(a, b, c):\n return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])\n \nfor point in sorted_datapoints[1:]:\n while ccw(convex_hull[-2],convex_hull[-1], point)<=0:\n del convex_hull[-1] # backtrack\n convex_hull.append(point)<\/code><\/pre>\n\n\n\nThat’s all!<\/p>\n\n\n\n
PS: Code I wrote for sorting the array at step 2 doesn’t sort the array if there are duplicate angles. I have to update the code.<\/em><\/p>\n\n\n\nReferences:<\/h2>\n\n\n\n- https:\/\/en.wikipedia.org\/wiki\/Convex_hull_algorithms<\/li>
- http:\/\/mathworld.wolfram.com\/PolarAngle.html<\/li><\/ol>\n","protected":false},"excerpt":{"rendered":"
Convex Hull is one of the fundamental algorithms in Computational geometry used in many computer vision applications like Collision avoidance in Self Driving Cars, Shape analysis and Hand Gesture-recognition, etc. By Definition, A Convex Hull is the smallest convex set that encloses a given set of points. For Example, Given a set of points P […]<\/p>\n","protected":false},"author":1,"featured_media":1261,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[38,6,32],"tags":[47,54,58],"_links":{"self":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1253"}],"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=1253"}],"version-history":[{"count":3,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1253\/revisions"}],"predecessor-version":[{"id":1851,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1253\/revisions\/1851"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media\/1261"}],"wp:attachment":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media?parent=1253"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/categories?post=1253"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/tags?post=1253"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}