I_love_tigersugar's blog

By I_love_tigersugar, 6 years ago, In English

Given a non self-intersect polygon and a line. How can I calculate the total length of parts of line which are inside the polygon? I need an O(NlogN) or faster algorithm, where N is the number of vertices of polygon.

For example, below is the polygon ABCDEFGH.

With line y = 0, no parts inside the polygon.

With line y = 2, the parts inside the polygon are IJ and KL, and the total length is 2.5.

With line y = 3, the part inside the polygon is BC, which has length 1,

Image and video hosting by TinyPic

I'm looking for your answers. Thanks for your help.

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

»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

I'm also !

»
6 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

Do you know how to cut a polygon with a line? It is similar. The main idea is to keep track of where you are respectively to the line while going through vertices of the polygon.

If you do this properly, you get 2k points of intersection between the line and the polygon. Then you can easily get the total length.

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

I think that we can sort the intersections of the given line with the polygon's edges by their X-coordinate (tie by Y-coordinate). Then the result should be the total distance between every pair of points i and (i+1) (with i%2=1)

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

    Can you explain more about your solution? I'm afraid it doesn't work in case y=0 or y=3 above.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I think it still work. You should not eliminate intersections which have the same X and Y coordinates then it would work.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        How about y = 1 ?

        The intersections are (0, 1), H, D, and F. All segments are inside the polygon.

        Your answer is (0, 1) -> H + D -> F. It's wrong.

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

          It should be (0,1)->H+H->D+D->F? :-?

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

            how about y = 2 ?

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it -10 Vote: I do not like it

              It's kinda obvious with y=2 you know. And I am really frustrated since I am just sharing my thoughts and all I got is down votes? So like only people with top ranks should have the right to vote hah?

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +13 Vote: I do not like it

    You can't consider the segments of the polygon separatedly. Counter example:

    Counterexample

    On the left, you need to remove the intersection. On the right, you must not. Both have 2 segments touching the line.

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

      We could however resolve this issue by looking at the other segment sharing the vertex/point/endpoint (when the line intersects the polygon at an endpoint). If both segments have their other endpoint on the same side of the line, then the intersection should be removed, otherwise it should not.

      (Your main point is still valid though, i.e., we can't consider segments individually. But TiChuot97's solution is quite appealing in its logical simplicity, so I think we should try to save it. =D )

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        You're right. Actually my previous comment "keep track of where you are respectively to the line while going through vertices of the polygon" means the same as what you said (though probably I made it sounds scarier).

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Yeah I got it now, but I think that I've read an article somewhere which approached the problem similarly to what I did. So thanks for the counter example.

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

Let's divide the polygon trapeze height 1 (h = 1)

For trapeze as AQH (point Q(0;1) ) or GHF we consider that the base is 0 (points A or G)

Let's count areas of all trapeze (S (trapeze) = h * (a + b) / 2, h = 1 => S (trapeze) = (a + b) / 2)

S(AQH) = QH / 2, S(GHF) = FH / 2 = (HD + DF) / 2 S(QIJD) = (IJ + QD) / 2 = (IJ + QH + HD) / 2 S(DKLF) = (KL + DF) / 2 S(IBCJ) = (BC + IJ) / 2, S(KEL) = KL / 2

if we sum all areas, we'll have: 1)area of polygon 2)QH + HD + DF + IJ + KL + BC/2 BC — horizontal side

So we should count half-sum of all horizontal sides of the polygon, because we consider them once

So ans = Area of polygon + Half-sum of all horizontal sides of the polygon

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

I'm looking for a site where I can submit my solution. Would you help providing the link?

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

    I ask this in order to solve a problem with Vietnamese statement. Unfortunately, I don't know any other problems using this one.

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

    Here's a link to an exactly identical problem (maybe it's not the "same problem" but the problem statement is the same ^^).

    https://open.kattis.com/problems/cuttingpolygon

    The problem is essentially just a variation of the ray-casting algorithm for the point in polygon problem, so I guess it's present at other online judges as well.

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

      Yeah, I found the problem in UVA too. Thanks for the information.

»
6 years ago, # |
Rev. 5   Vote: I like it +2 Vote: I do not like it

Edit: sorry, misread the statement.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Poor you =))

    Just to explain why flashmt is explaining solution of non-related problem: skyvn97 used the example figure of this famous problem in Vietnamese OJ, so flashmt probably did not read the statement again and write solution.

    The problem statement of this problem goes like this:

    • You're given a polygon with N vertices (N <= 1000)
    • You need to answer Q queries (Q <= 50,000) of form: yi, where you need to calculate the length of the intersections between line y=yi and the given polygon.