Блог пользователя ifsmirnov

Tangent to a convex polygon
Автор ifsmirnov, 8 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Check this link : tangent to polygon.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится -38 Проголосовать: не нравится

      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

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Три точки, говоришь? Не знаю... зато умею так.

Пусть мы строим касательную из точки P. В случае на первой картинке верхняя (левая, если смотреть из P) касательная строится простым бинпоиском.

Чтобы свести общий случай к уже разобранному, проведём луч из P в любую вершину многоугольника V[k] (пусть k=0). Пусть у нас фиксирована ориентация многоугольника cw. Можно одним векторным произведением, заранее понять, V[k] -- ближняя к P точка, или дальняя от P. Пусть V[k] -- дальняя, тогда внутри бинпоиска по вершинам мноугольника на отрезке [k..k+n) сперва идёт часть многоугольника, которая находится правее луча "P --> V[k]", её нужно пропустить. Затем ровно случай на первой картинке.

Итого, если V[0] -- дальняя точка, пишем один бинпоиск со сложным условием:

l = 0, r = n; // [l..r), k = 0, случай на второй картинке
while (r - l > 1) {
  int m = (l + r) / 2;
  if ((V[0] - P) x (V[m] - P) < 0 || (V[m+1] - V[m]) x (V[m] - P) > 0) 
    l = m;
  else
    r = m;  
}
// Answer = r

P.S. Sorry, it's hard for me to write down this description in english.

→ Ответить