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

Geometry (being in a point and having n lines, how many lines can you see)
Автор Usu, история, 6 лет назад, По-английски

Hey! Can anybody help with this problem? This problem says that we are in a point (x,y) and we have n lines (defined by the line's equation a,b,c). How many lines can we see from that point? If we see only a point of a line, we do not consider that line at all. I think we should find the intersections of all the lines firstly, but I do not have certain ideas. The number of lines is 10.000, does anybody have ideas?

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

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

Link to the problem?

Regarding the solution, this problem can be reduced to a half plane intersection problem, you just need to know for each line, which half plane it “keeps”, and the answer is the halfplane that contains the point.

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

    I don't have a link. I just discussed this with a friend who saw it in a printed book. Can you detail more the solution?

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

      Well the reduction to a half plane intersection is somewhat straightforward. If you dont know how to do halfplane intersection you should google it, but I will give a brief explanation to how I do it. You sort the half planes (that are defined by lines) by angle and iterate over them and check if the intersection of halfplanes i and i+2 are a subset of halfplane i+1. If so, you erase halfplane i+1.

      → Ответить