Usu's blog

Geometry (being in a point and having n lines, how many lines can you see)
By Usu, history, 5 years ago, In English

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?

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

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

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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.

      → Reply