Confused101's blog

Random point.
By Confused101, history, 7 years ago, In English

Given N rectangles which may or may not intersect. Report a random point Inside any rectangle. (probability of every point chosen must be equal). How to solve this problem?

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

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

Points that appear in more that one rectangle have more probability or not?

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

    No, every point should have same probability of being chosen irrespective of numbers of rectangles it appears in.

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

      One more question :)...

      Could a rectangle have two or more of these N points in it?

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

        There are N rectangles, you have to report random points inside any of these rectangles. Sorry if I was unclear, See image you need to report any random point from blue region. Image

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

Partition the rectangle union into area-disjoint rectangles, choose a rectangle randomly accordingly to ratio of its area to sum of areas. Choose random (x,y) coordinate inside.

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

    Looks good to me. Can you tell how can I "Partition the rectangle union into area-disjoint rectangles"? (algorithm)

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

If coordinates are not big, you can get any random point until you get one which is inside one of the rectangles. That will still give you a uniform distribution although at a time complexity cost.

→ Reply