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

Автор rahul_1234, история, 8 лет назад, По-английски

Given 'n' circles (each defined by center and radius) Write an algorithm to detect if given circles intersect with any other circles in the same plane

Better than O(n^2) complexity

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

If I got the problem correctly, for each circle you just need to loop though all others and compare the distance between two centers versus the sum of two radiuses. Two circles intersect if the former is not greater than the latter.

The time complexity for the above approach would be O(n^2) ______

Updated 1: Sorry the time complexity is not good enough

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

    Yes, but a better approach O(NlogN) is reqd.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

      Sweep line, make a vertical line sweep from x=-inf to x=+inf, whenever it touch a circle from left insert the Y coordinates of its center to a std::set and check if this circle intersects with the two circles which become immediately before and after this circle in the std::set, whenever the line touches from a circle from right remove that circle from set now check if the two circles which was before and after the removed circle in the std::set intersect with each other.

      UPD: I considered that intersecting of two circles means having a common area

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Can u explain using some example.

        A brief example would be very useful.

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

          Give me an example you want me to explain

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

            Any example of choice where I can visualise the algo?

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

              Maybe 4 circles like this Pic where

              1 intersects 2, 3, 4

              2 intersects 3, 4

              3 intersects 4

              or any other to get intuitive explanation.

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

                if you have 4 circles such that all pairs intersect with each other then here's how the algorithm will work:

                the sweeping line will move until it touches the first circle from the left, you will insert its Y coordinates to std::set now the line will continue sweeping until it touches another circle from left and you will add its Y coordinates to std::set, since there was only one circle in the std::set the newly added circle will come either after or before it so you have to check if those two circles intersect and they indeed intersect because all circles intersect with each other so you just return that there's intersection and terminate the algorithm.

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

              This link may help you

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

Do I have to say whether there are 2 circles that intersect or the pairs of circles that intersect?