ifsmirnov's blog

Tangent to a convex polygon
By ifsmirnov, 7 years ago, In English

Several months ago I've seen a comment on Codeforces which explained a method of finding a tangent from a point to a polygon. This problem is rather hard and if you try the first implementation which comes to your mind, it probably will not work. That comment explained a tricky binary search where you should store not two endpoints of a segment, but three, and which was easy to implement.

However, now I cannot neither recall the idea nor find the comment itself. Could anyone help me with either?

  • Vote: I like it
  • +46
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Check this link : tangent to polygon.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Thanks, but that's not what I need. This is exactly an implementation which first comes to mind :) And there are some pitfalls you may encounter while implementing it. I'm searching for a simpler way.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it -38 Vote: I do not like it

      The concept is that you take projection of all points of polygon on a vertical line(by joining point on polygon and the point from where you want to find tangent the point of intersection of vertical line and above line is the projection) after that you can take the projected point with maximum and minimum values of projected y and connect with given point to get tangents.

      vertical line must lie between polygon and point

      Edit : you could optimize it by using ternary search and computing the projection when required

      → Reply