137 - Polygons

[rossi kamal]

I am getting problem in finding the intersection of two polygons

can any one tell which algorithm should be choosen here...

would u please give some test cases of finding the intersection of two polygons?

[baodog]

For algorithm see

O'Rourke, J. Computational Geometry in C, 2nd ed. Cambridge, England: Cambridge University Press, 1998.

Mount, D. M. "geometric Intersection." Ch. 33 in Handbook of Discrete and Computational Geometry (Ed. J. E. and J. O'Rourke). Boca Raton, FL: CRC Press, pp. 615-630, 1997.

Suri, S. "Polygon Intersection."

[cs_lyxab]

I have already search the board. I think my algorithm is the same with what it is said in this board. I also used the test cases here but I find there are some problems(the polygon is not convex, and I passed other cases). Anyone else can give me some other different test case? I really want to AC this problem because it is related to my course score. Or you can send me e-mail: cs_lyxab@stu.ust.hk

[fgeo]

Keep getting WA, same algorithm as lmnop: compute the intersection of polygons A and B by taking the convex hull of all vertices of A in B, all vertices of B in A, intersections of edges of A and B. On all of the posted test cases that aren't broken, my code gets the right answer. Which one is broken: the algorithm, my implementation of that algorithm, or the judge?

[mf]

Keep getting WA, same algorithm as lmnop: compute the intersection of polygons A and B by taking the convex hull of all vertices of A in B, all vertices of B in A, intersections of edges of A and B. On all of the posted test cases that aren't broken, my code gets the right answer. Which one is broken: the algorithm, my implementation of that algorithm, or the judge?

Algorithm's good; the judge is fine, I believe; so that leaves only your implementation...

[fgeo]

I just finished another algorithm based on a sweep-line approach, without reusing any code at all, and the two agree to within 0.01 on every single random input I've tried. I know how annoying singular cases can be, so I chose the random parameters in such a way that they would occur non-trivially often. I've eyeballed hundreds of intersected polygons -- no problems. Both codes agree with every posted test case, so I'm pretty sure I'm not in orbit. The only possibility left is that I'm getting killed by round-off error, which I consider to be judge breakage. I'm declaring this correct and moving on.

[tmt]

I was getting WA because of forgetting newline character at the end of the output...
(I've got AC now!)
Hope this information helps

[S.H.Bouwhuis]

I keep getting WA for this problem.
Could someone please provide outputs for my inputs?

My inputs

Code: Select all

3 0 1 3 4 6 1
3 0 3 6 3 3 0
4 0 0 0 10 10 10 10 0
4 2 2 2 7 7 7 7 2
4 2 2 2 7 7 7 7 2
4 0 0 0 10 10 10 10 0
4 0 0 0 10 10 10 10 0
4 0 0 0 5 5 5 5 0
2 5 10 10 11
2 16 4 10 16
1 0 0
1 0 0
4 20 82 97 93 80 19 37 1
5 31 53 18 63 11 86 76 93 66 46
8 1 46 3 87 21 90 71 88 95 79 96 67 92 2 18 1
9 1 25 11 84 13 86 82 96 92 96 96 70 98 37 92 27 71 6
10 4 6 3 76 11 93 52 99 70 95 92 64 99 50 81 7 67 3 34 3
10 68 2 25 11 1 45 1 63 4 92 37 98 71 89 89 61 97 10 86 1
10 41 2 2 14 9 81 12 83 73 92 99 82 96 52 90 3 74 1 67 1
11 5 15 4 28 1 85 26 95 67 95 93 88 98 85 99 29 98 9 91 8 41 3
1 42 73
1 22 29
11 6 10 3 39 6 71 10 95 42 98 96 95 99 73 99 69 93 21 65 4 51 1
9 30 5 1 17 3 42 8 91 77 90 99 73 99 69 98 23 61 4
7 18 33 20 52 25 90 59 96 96 84 98 19 41 9
6 2 13 8 46 53 88 70 94 79 66 76 2
7 12 78 13 92 38 96 94 72 95 23 94 1 11 1
10 2 5 2 34 11 96 17 98 95 86 98 43 99 22 97 4 80 1 16 1
10 4 9 2 72 37 83 84 95 95 90 98 19 94 11 86 7 75 3 17 2
11 64 6 6 24 5 40 4 86 66 94 74 95 86 78 96 52 96 35 89 14 79 4
9 10 18 4 24 6 62 15 98 32 98 99 93 97 59 82 2 40 2
9 40 5 9 16 3 27 1 40 11 89 88 93 96 51 86 22 57 3
8 9 7 2 79 9 93 55 97 67 98 95 75 98 56 60 1
10 27 11 14 81 57 97 88 94 96 90 98 80 99 42 93 10 72 7 45 4
8 13 6 5 42 2 59 6 88 96 99 99 37 87 12 80 2
7 3 4 7 99 34 98 70 95 95 91 79 30 61 1
9 23 2 6 47 3 57 13 91 38 94 87 95 96 62 99 9 31 1
10 23 9 7 22 2 73 8 81 35 99 78 90 94 38 99 20 88 2 36 2
9 3 19 1 95 17 98 76 95 91 87 97 78 93 30 90 18 68 2
8 1 10 3 85 23 95 47 98 82 96 92 82 94 6 41 6
7 35 7 21 40 4 83 49 95 88 65 99 17 68 6
5 2 5 12 91 64 91 67 84 92 1
9 59 17 5 36 14 94 38 94 83 92 93 89 93 69 91 20 84 12
8 13 36 13 72 16 86 84 86 99 68 98 63 69 28 26 5
4 12 51 7 88 67 33 42 17
6 5 25 17 83 67 92 99 28 81 13 5 12
12 8 17 1 50 1 66 12 87 70 99 91 91 96 68 90 34 80 7 33 2 17 1 12 1
10 11 16 2 37 1 58 11 82 15 89 97 97 97 34 84 15 57 4 37 1
12 66 4 2 12 4 82 8 92 21 96 79 99 97 96 99 95 99 68 98 23 86 14 71 5
8 88 2 4 30 5 47 19 85 28 96 86 99 99 82 95 29
6 56 19 24 24 4 70 16 82 43 82 71 37
6 47 7 10 22 3 37 34 68 89 44 79 8
3 1 9 6 18 63 22
3 32 36 26 54 66 91
8 72 3 22 5 18 9 7 44 26 98 80 95 94 52 97 8
11 50 11 28 16 8 21 1 57 9 69 11 71 34 93 49 96 74 99 99 87 79 18
11 48 6 20 8 2 13 2 52 13 64 33 84 42 90 59 99 90 73 93 18 80 8
10 69 3 9 3 2 22 8 81 13 99 59 94 86 89 96 85 96 59 93 27
11 44 1 9 4 7 23 1 89 23 98 79 98 90 86 94 75 96 30 89 5 81 4
11 47 1 27 3 4 7 3 57 3 93 49 97 91 90 98 80 98 30 96 19 93 4
7 26 8 12 38 11 69 11 96 44 91 99 77 96 21
4 55 1 2 29 1 78 96 94
8 94 2 9 12 7 19 3 33 8 99 33 96 52 90 97 71
10 90 6 37 6 13 19 10 23 1 51 12 77 27 90 48 97 81 87 93 53
5 6 3 20 97 38 96 69 87 90 28
6 80 9 35 17 21 64 14 94 61 90 96 83
9 12 2 9 19 2 72 3 81 5 84 20 94 74 83 88 67 59 4
7 23 3 13 3 2 91 18 91 89 90 91 52 88 14
7 45 1 32 43 25 91 55 98 77 79 87 44 87 8
9 36 1 22 3 1 82 9 97 68 99 92 95 94 75 81 38 68 17
10 61 1 3 11 9 96 15 99 43 99 97 95 98 63 94 14 91 9 80 6
8 67 2 14 2 5 12 1 89 24 98 75 99 98 97 99 11
1 35 63
1 57 90
9 35 1 9 8 3 37 16 95 91 99 96 97 99 59 96 26 89 4
12 45 2 29 2 6 4 3 9 2 91 26 97 60 95 76 91 83 89 96 56 94 13 81 4
8 54 2 7 45 8 82 14 93 37 98 92 89 98 69 90 3
10 7 2 5 68 19 81 38 96 89 95 98 94 95 34 72 7 52 5 27 3
9 87 2 57 5 19 12 7 18 5 73 12 99 86 82 89 73 93 17
10 71 4 34 4 5 26 2 68 11 98 73 98 92 86 96 79 94 28 88 7
8 86 13 30 21 21 27 17 55 27 72 36 87 50 81 71 61
5 43 19 27 27 4 58 98 97 97 23
8 22 2 4 5 7 32 13 65 21 71 79 92 92 38 87 3
5 4 6 12 55 51 84 96 35 91 9
6 6 3 8 2 8 1 4 1 4 2 5 3
4 1 2 1 4 5 4 5 2
6 6 3 8 2 8 1 4 1 4 2 5 3
5 1 2 1 4 5 4 5 3 4 2
5 1 2 1 4 5 4 5 3 4 2
6 6 3 8 2 8 1 4 1 4 2 5 3
6 6 3 8 2 8 1 4 1 4 2 5 3
6 1 2 1 4 5 4 5 3 4 3 4 2
6 1 2 1 4 5 4 5 3 4 3 4 2
6 6 3 8 2 8 1 4 1 4 2 5 3
4 0 1 0 2 3 2 3 1
4 1 0 1 3 2 3 2 0
4 1 0 1 3 2 3 2 0
4 0 1 0 2 3 2 3 1
4 1 0 1 3 2 1 2 0
4 0 1 0 2 3 2 3 1
4 0 1 0 2 3 2 3 1
4 1 0 1 3 2 1 2 0
3 5 5 8 1 2 3
3 5 5 8 1 2 3
4 1 2 1 4 5 4 5 2
6 6 3 8 2 8 1 4 1 4 2 5 3
12 8 17 1 50 1 66 12 87 70 99 91 91 96 68 90 34 80 7 33 2 17 1 12 1 
10 11 16 2 37 1 58 11 82 15 89 97 97 97 34 84 15 57 4 37 1 
6 6 3 8 2 8 1 4 1 4 2 5 3 
4 1 2 1 4 5 4 5 2 
6 6 3 8 2 8 1 4 1 4 2 5 3 
5 1 2 1 4 5 4 5 3 4 2 
5 1 2 1 4 5 4 5 3 4 2 
6 6 3 8 2 8 1 4 1 4 2 5 3 
4 0 1 0 2 3 2 3 1 
4 1 0 1 3 2 3 2 0 
4 1 0 1 3 2 3 2 0 
4 0 1 0 2 3 2 3 1 
4 1 0 1 3 2 1 2 0 
4 0 1 0 2 3 2 3 1 
4 0 1 0 2 3 2 3 1 
4 1 0 1 3 2 1 2 0 
12 66 4 2 12 4 82 8 92 21 96 79 99 97 96 99 95 99 68 98 23 86 14 71 5 
8 88 2 4 30 5 47 19 85 28 96 86 99 99 82 95 29 
6 56 19 24 24 4 70 16 82 43 82 71 37 
6 47 7 10 22 3 37 34 68 89 44 79 8 
3 1 9 6 18 63 22 
3 32 36 26 54 66 91 
8 72 3 22 5 18 9 7 44 26 98 80 95 94 52 97 8 
11 50 11 28 16 8 21 1 57 9 69 11 71 34 93 49 96 74 99 99 87 79 18 
11 48 6 20 8 2 13 2 52 13 64 33 84 42 90 59 99 90 73 93 18 80 8 
10 69 3 9 3 2 22 8 81 13 99 59 94 86 89 96 85 96 59 93 27 
11 44 1 9 4 7 23 1 89 23 98 79 98 90 86 94 75 96 30 89 5 81 4 
11 47 1 27 3 4 7 3 57 3 93 49 97 91 90 98 80 98 30 96 19 93 4 
7 26 8 12 38 11 69 11 96 44 91 99 77 96 21 
4 55 1 2 29 1 78 96 94 
8 94 2 9 12 7 19 3 33 8 99 33 96 52 90 97 71 
10 90 6 37 6 13 19 10 23 1 51 12 77 27 90 48 97 81 87 93 53 
5 6 3 20 97 38 96 69 87 90 28 
6 80 9 35 17 21 64 14 94 61 90 96 83 
9 12 2 9 19 2 72 3 81 5 84 20 94 74 83 88 67 59 4 
7 23 3 13 3 2 91 18 91 89 90 91 52 88 14 
7 45 1 32 43 25 91 55 98 77 79 87 44 87 8 
9 36 1 22 3 1 82 9 97 68 99 92 95 94 75 81 38 68 17 
10 61 1 3 11 9 96 15 99 43 99 97 95 98 63 94 14 91 9 80 6 
8 67 2 14 2 5 12 1 89 24 98 75 99 98 97 99 11 
1 35 63 
1 57 90 
9 35 1 9 8 3 37 16 95 91 99 96 97 99 59 96 26 89 4 
12 45 2 29 2 6 4 3 9 2 91 26 97 60 95 76 91 83 89 96 56 94 13 81 4 
8 54 2 7 45 8 82 14 93 37 98 92 89 98 69 90 3 
10 7 2 5 68 19 81 38 96 89 95 98 94 95 34 72 7 52 5 27 3 
9 87 2 57 5 19 12 7 18 5 73 12 99 86 82 89 73 93 17 
10 71 4 34 4 5 26 2 68 11 98 73 98 92 86 96 79 94 28 88 7 
8 86 13 30 21 21 27 17 55 27 72 36 87 50 81 71 61 
5 43 19 27 27 4 58 98 97 97 23 
8 22 2 4 5 7 32 13 65 21 71 79 92 92 38 87 3 
5 4 6 12 55 51 84 96 35 91 9 
1 0 0 
1 0 0 
4 20 82 97 93 80 19 37 1 
5 31 53 18 63 11 86 76 93 66 46 
8 1 46 3 87 21 90 71 88 95 79 96 67 92 2 18 1 
9 1 25 11 84 13 86 82 96 92 96 96 70 98 37 92 27 71 6 
10 4 6 3 76 11 93 52 99 70 95 92 64 99 50 81 7 67 3 34 3 
10 68 2 25 11 1 45 1 63 4 92 37 98 71 89 89 61 97 10 86 1 
10 41 2 2 14 9 81 12 83 73 92 99 82 96 52 90 3 74 1 67 1 
11 5 15 4 28 1 85 26 95 67 95 93 88 98 85 99 29 98 9 91 8 41 3 
1 42 73 
1 22 29 
11 6 10 3 39 6 71 10 95 42 98 96 95 99 73 99 69 93 21 65 4 51 1 
9 30 5 1 17 3 42 8 91 77 90 99 73 99 69 98 23 61 4 
7 18 33 20 52 25 90 59 96 96 84 98 19 41 9 
6 2 13 8 46 53 88 70 94 79 66 76 2 
7 12 78 13 92 38 96 94 72 95 23 94 1 11 1 
10 2 5 2 34 11 96 17 98 95 86 98 43 99 22 97 4 80 1 16 1 
10 4 9 2 72 37 83 84 95 95 90 98 19 94 11 86 7 75 3 17 2 
11 64 6 6 24 5 40 4 86 66 94 74 95 86 78 96 52 96 35 89 14 79 4 
9 10 18 4 24 6 62 15 98 32 98 99 93 97 59 82 2 40 2 
9 40 5 9 16 3 27 1 40 11 89 88 93 96 51 86 22 57 3 
8 9 7 2 79 9 93 55 97 67 98 95 75 98 56 60 1 
10 27 11 14 81 57 97 88 94 96 90 98 80 99 42 93 10 72 7 45 4 
8 13 6 5 42 2 59 6 88 96 99 99 37 87 12 80 2 
7 3 4 7 99 34 98 70 95 95 91 79 30 61 1 
9 23 2 6 47 3 57 13 91 38 94 87 95 96 62 99 9 31 1 
10 23 9 7 22 2 73 8 81 35 99 78 90 94 38 99 20 88 2 36 2 
9 3 19 1 95 17 98 76 95 91 87 97 78 93 30 90 18 68 2 
8 1 10 3 85 23 95 47 98 82 96 92 82 94 6 41 6 
7 35 7 21 40 4 83 49 95 88 65 99 17 68 6 
5 2 5 12 91 64 91 67 84 92 1 
9 59 17 5 36 14 94 38 94 83 92 93 89 93 69 91 20 84 12 
8 13 36 13 72 16 86 84 86 99 68 98 63 69 28 26 5 
4 12 51 7 88 67 33 42 17 
6 5 25 17 83 67 92 99 28 81 13 5 12 
12 8 17 1 50 1 66 12 87 70 99 91 91 96 68 90 34 80 7 33 2 17 1 12 1 
10 11 16 2 37 1 58 11 82 15 89 97 97 97 34 84 15 57 4 37 1 
0

My outputs

Code: Select all

    6.00   75.00   75.00   75.00    0.00    0.00 3350.18 1866.41 1458.18 1272.38    0.00 1027.32 309
2.04 1315.82 1915.00 1129.05 2688.32 2015.90 1184.53  931.58 2407.83 2095.03 4248.67  881.23 1639.87
 2568.05  717.50 2109.92 1692.83  725.81 2777.31 1332.75 2248.29 1540.76 3641.56  776.28    0.00 125
3.74 1953.81 1199.71 2517.67 1496.87   13.50   14.00   14.00   13.50   13.50    4.00    4.00    3.50
    3.50    0.00   13.50  881.23   13.50   14.00   14.00    4.00    4.00    3.50    3.50 1639.87 256
8.05  717.50 2109.92 1692.83  725.81 2777.31 1332.75 2248.29 1540.76 3641.56  776.28    0.00 1253.74
 1953.81 1199.71 2517.67 1496.87    0.00 3350.18 1866.41 1458.18 1272.38    0.00 1027.32 3092.04 131
5.82 1915.00 1129.05 2688.32 2015.90 1184.53  931.58 2407.83 2095.03 4248.67  881.23

[brianfry713]

AC output for your input:

Code: Select all

    6.00   75.00   75.00   75.00    0.00    0.00 3350.18 1866.41 1458.18 1272.38    0.00 1027.32 3092.04 1315.82 1915.00 1129.05 2688.32 2015.90 1184.53  931.58 2407.83 2095.03 4248.67  881.23 1639.87 2568.05  717.50 2109.92 1692.83  725.81 2777.31 1332.75 2248.29 1540.76 3641.56  776.28    0.00 1253.74 1953.81 1199.71 2517.67 1496.87   13.50   14.00   14.00   14.50   14.50    4.00    4.00    3.50    3.50    0.00   13.50  881.23   13.50   14.00   14.00    4.00    4.00    3.50    3.50 1639.87 2568.05  717.50 2109.92 1692.83  725.81 2777.31 1332.75 2248.29 1540.76 3641.56  776.28    0.00 1253.74 1953.81 1199.71 2517.67 1496.87    0.00 3350.18 1866.41 1458.18 1272.38    0.00 1027.32 3092.04 1315.82 1915.00 1129.05 2688.32 2015.90 1184.53  931.58 2407.83 2095.03 4248.67  881.23

This should all be one line. The difference is two "13.50"'s should be "14.50".

[S.H.Bouwhuis]

I don't understand that.

The input is:
6 6 3 8 2 8 1 4 1 4 2 5 3
6 1 2 1 4 5 4 5 3 4 3 4 2

Please explain how your AC program calculates it to be 14.50.
Looking at my thumbnail you can see I would expect 13.50.

[brianfry713]

The problem statement requires that both polygons are convex. This input is not valid for this problem.

[S.H.Bouwhuis]

Yes, I realized that after BrianFry pointed me to that. But, my solution works with convex, concave, clockwise and counter-clockwise polygons. Yet there still is some sneaky input which makes my code give an incorrect answer.
I've been staring on and off at this problem for about 10 years now, and I really don't know what to change.

If someone could send me their AC app then I could run it with thousands, or if need be, millions of inputs to see where our applications differ. Only then will I be able to solve this.
This seemingly simple problem is a thorn in my eye and makes me a sad panda

[brianfry713]

http://www.uvatoolkit.com/problemssolve.php

[S.H.Bouwhuis]

Oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooohhhhhhhhhhhhhhhhhhhhhhhhhh!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Fantastic!!!!!!!!!

This is going to be INCREDIBLY useful!!!

[rafastv]

Hi, some tips for you. There are several methods to approach this problem, but I recommend:

1) Implement a method for triangulation. Some triangles will belong to the intersection and some to the union (you'll need a way to find out which ones are in one or the other).

2) Implement a method for triangle or segment intersection.

3) Implement a method to calculate the area of a triangle.

4) The intersection and the union are not necessarily convex.

5) Code or use some program to plot whatever you are doing.