Libraion's blog

[Help] Sum Length of Inner Segments !?
By Libraion, history, 4 years ago, In English

Given a polygon $$$n (n \leq 10 ^ 5) $$$ vertices on a 2D Descartes plane. $$$(|x_i|,|y_i| \leq 5. 10^8)$$$. This polygon is not self-intersecting, 2 consecutive edges have only 1 common point (which is the vertex). Find the sum of all segments of the 2D plane lie completely inside the polygon. (can be a real number).

Input:

5

0 0

-2 2

-2 -1

2 -2

2 0

Output: 12.5

Explain: The answer is the sum of all the red segments. The middle point is $$$(0,0)$$$.

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

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

Do a sweepline for both directions.

Going from bottom to top, keep all active segments in a sorted container. We will now process events and lazily add up the contribution of each line. For this you also need some meta information for each line, whether the polygon is to the right, or left and upto which height its contribution has already been added.

An event is either the start/end of two neighboring segments or replacing a line by another line. You can now update the sorted container. When doing this remember to add up the remaining contribution of previous segment at this position. This is just arithmetic so I won't go into detail. Furthermore don't forget to handle the case of a line parallel to the x-Axis.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Thanks for answering! Could you elaborate your idea with the above test case please? Appreciate!

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

      Ok I first lets go from left to right.

      Initially we add the lines (-2, 2)->(0,0) and (-2,1)->(2,-2). Remember vertical/horizontal lines need to be special cased. Next the line (0,0)->(2,0) will start. This line replaces (-2, 2)->(0,0), so we have to add its contribution. In this case this is the segment (-1,1)->(-1, -1.25).

      Now we have [(-2, 2)->(0,0); (-2, 2)->(0,0)] in our container and know between them is the polygon and we need to start counting at x = 0.

      Then we consider the segment (2,0)->(2,-2) which merges (i.e. removes) the lines (-2, 2)->(0,0) and (-2, 2)->(0,0). Therefore we have to add their remaining contribution, which are the segments (0,0)->(0,-1.5) and (1,0)->(1,-1.75). Since we considered all lines we are done.

      Remember, we can't add all contributing lines one by on. Instead we have to compute the current contribution in O(1). For this let $$$\Delta y$$$ denote the left most distance between the segemnts and let $$$\Delta y_1$$$ denote the difference in distance per step. Then if $$$l$$$ is the length we have

      $$$Contribution = \sum_{i = 0}^{l-1} (\Delta y - i*\Delta y_1) = (l-1)*\Delta_y - \binom{l-1}{2} \Delta y_1$$$

      .

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

        Sorry but may I have a few absurd question?

        1. When do we add/delete/replace lines in our container?

        2. How that there is 2 same lines in our container [(-2, 2)->(0,0); (-2, 2)->(0,0)] ?

        3. $$$\Delta y$$$ denote the left most distance... What do you mean by left most distance? (A real example would be great.)

        4. $$$\Delta y_1$$$ is the distance per step. I don't understand. Could you give an example?.

        5. Is $$$l$$$ the difference of x coordinate between the current event and the last one?

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

I think you can use something similar to the calculation of the area of a polygon using trapezoids. We calculate what the signed sum of the lengths of all the vertical lines that lie inside or on the right boundary of a trapezoid is.

Picture

The formula is $$$sgn \cdot ( W \cdot P.y + (W+1) \cdot (Q.y-P.y)/2 )$$$, where $$$W = abs(Q.x-P.x)$$$ and $$$sgn$$$ corresponds to the sign of the area of the trapezoid.

If for every edge in the polygon we add the signed sum of lines of its trapezoid up, I think we get the answer. Vertical edges are a special case and sometimes we have to subtract them out, to stop overcounting of right boundaries of trapezoids. This only counts the vertical lines, so we rotate the polygon 90 degrees and do it again.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    It seems to me that your solution won't be able to pass the below case. Sorry if I missed something.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      I think my approach could work on your test, because when you calculate the contribution of a trapezoid formed by an edge of the polygon and the x-axis, sometimes this contribution is positive, sometimes negative which cancels all the lines outside the polygon and sums precisely the line segments inside the polygon. I made a program implementing my idea for this problem. It works on your example, but I didn't test it further:

      Program
      → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you share the problem link?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    I don't know if it is online or not. I have about 20 local tests for this problem.

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

Thanks for everybody. Using your ideas and suggestions, I have come up with a weird solution. (It outputs correct for 17/20 test cases — the 3 remaining are huge ones and I don't know what to do — maybe just assume that the test output is wrong by float/double/long double reasons).

At first I think about sweepline 2 directions and calculate like Veladus ideas. But I stucked at the polygon which is like the picture below. As we each time we get to an event there can be O(n) different trapezoids (and it seems that there is hardly a way to manage every trapezoid and sum up all of them at once).

So I changed the idea a bit. First I took the convex hull of the polygon. And calculate with the above idea. But it will be redundant of course. So I just iterate through the polygon again and find which inner-polygon is redundant and recursively solve it again then minus the redundant part. It is a lot of implementation, though.

I thought it would be slow, but in fact it was fast but it was WA.

I'm looking for a way to generate testcase for this problem. But the restrictions of polygon which is not self-intersecting and the input have to be ccw/cw order, makes it really hard. Not only that I don't know how to have correct output for that generated testcases :'(.

I'd appreciate if anyone suggest me a way to generate test and help debug my code.

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

What about triangulation?
As I see you can easily calculate answer for triangle in $$$O(1)$$$. Then find any triangulation and sum up all the answers. The only case is when sides are parallel to axis (e.g. square, rotated pi/4)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    That's an idea to consider. However, as I'm fed up with this problem, you can try to implement your approach and check the above 3 big testcases google drive link. (If you are successful, please show me your code <3. Thanks)

    → Reply