rumman_sust's blog

By rumman_sust, history, 3 years ago, , UPD: I just solved Robert Hood from Kattis online judge. After spending almost a week I've understood the process of rotating calipers. It feels really great to learn a new problem solving technique. I recommend everyone to read this book and visit this site (provided by SuprDewd) for umderstanding rotating calipers technique. Here you can find a basic implementation of rotating calipers for finding diameter of a convex polygon. Also don't forget to look at SuprDewd's comment. Thank you all for helping and encouraging me all the time :)  Comments (14)
 » I've found this but I think it's not enough. Moreover, it's in Russian language.
 » Rotating Calipers is a very useful technique. So it would be really great If we could discuss about the Topic and related problems here. Following this important thread :)
 » Could you please write a detailed blog on it, if you have learned it well.
•  » » I'll try thanks.
 » I studied the technique some months ago. Unfortunately I don't have all the resources I used while learning, but I remember that the following three links were useful: There are many applications of rotating calipers, but I think the most basic one is to find the diameter of a convex polygon*. Conceptually it's very simple. We put the polygon between the two jaws of a caliper, and tighten. We then rotate the calipers a full circle around the polygon, while keeping the caliper tight at all times. The answer is then the maximum distance between the two jaws at any point during the procedure.The rotating calipers technique is basically just an "angle-sweep-line" version of this. We have two parallel lines that are on either side of the polygon, representing the jaws of the caliper. Initially we could, for example, let one of the lines touch the leftmost point of the polygon and the other line touch the rightmost point of the polygon, and say they are completely vertical (i.e. at an angle pi/2). We then simulate this procedure by rotating the two lines at the same speed, keeping track of which two points the two lines are touching, and then only stopping at the moments these points change.This can then be easily generalized to many applications: Minimum rectangle enclosing a convex polygon: Now we have two calipers that are orthogonal to each other, and again we rotate them around the polygon. This corresponds to having four lines in the simulation, i.e. two pairs of parallel lines, which are then orthogonal to each other so that the interior forms a rectangle. Minimum distance between two convex polygons: Now one of the lines touches one of the polygons, and the other line touches the other polygon. Furthermore, we will initially let one of the lines touch the leftmost point of the corresponding polygon, while the other line touches the rightmost point of the corresponding polygon, and again the lines start out vertical. See the links above for further applications and more detailed explanations.For some example code you can look at my implementation. I have a class that represents a single jaw of the caliper (i.e. a single line), and then below (commented out) is how I use that class to find the diameter of an arbitrary polygon. Note that the code uses doubles and angles (as that was more intuitive for me at the time), but a more robust implementation would only use integers.Finally, here are some practice problems: Would love to hear if others have more problems.*) Finding the diameter of an arbitrary polygon can be reduced to this problem by first taking the convex hull. The same is true for many other applications.
•  » » 3 years ago, # ^ | ← Rev. 3 →   Thank you so much SuprDewd. It's a great help. I've found the book named "COMPUTATIONAL GEOMETRY WITH THE ROTATING CALIPERS" written by Pirzadeh, Hormoz just before your reply. That's why I didn't check my blog post to see if anyone place a comment or not. Sorry for the late response. I'm reading the book written by Pirzadeh, Hormoz now. Hopefully I'll understand the technique soon and will be able to solve some problems related to it. Thanks again.PS: If you have enough time you can add those resources at here. It will be easy to find for the future problem solvers.
•  » » The link SuprDewd gave for COMPUTATIONAL GEOMETRY WITH THE ROTATING CALIPERS is not working anymore. Can someone please provide the pdf ( I assume it was a link to a pdf) of the link ? And thanks SuprDewd, I learnt a lot of things from the links you provided.
•  » » » Googling the title gives this page. Can you open the PDF from there?
•  » » » » Yes, I can. Thanks.
 » Auto comment: topic has been updated by bekar13 (previous revision, new revision, compare).
 » 16 months ago, # | ← Rev. 3 →   Can we use the intuitive two pointers technique for finding antipodal pairs in convex polygon? Like: j<-0 for i in [0,n): while distance(p[j+1], p[i]) >= distance(p[j+1], p[i]) and j < i: if distance(p[j+1], p[I]) == distance(p[j+1], p[I]): store (p[I],p[j+1]) in cache else: clean cache j += 1 yield points in cache (obviously all incrementation done modulo n)It worked on Robin Hood, but it fells like it has too simple tests. Any pitfalls? Thank you!UPD: Both implementations for robin hood are given here
•  » » There is a negative example from this Chinese blog The O point won't find it's antipodal point A because the of the B point. It may stuck on the C point.
•  » » » Isn't that true, that the diameter of the figure on the set equals to the distance between point A and that unnamed point between O and C? If yes (and it seems to be like that), the "wrong" algorithm would actually find the correct answer, and it don't need the length of segment "OA" at all.
•  » » » » Yes, I think you're right. But I thought the figure show that you can't find the antipodal point using the binary search approach. For the global diameter, we should find another negative example :)