## 137 - Polygons

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rossi kamal
New poster
Posts: 14
Joined: Mon Sep 03, 2007 10:11 am
Contact:
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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am
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
New poster
Posts: 3
Joined: Sat Sep 20, 2008 6:58 pm

### 137 keep getting WA

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
New poster
Posts: 2
Joined: Tue Feb 17, 2009 3:00 am

### Re: 137 - Polygon - WA - please help

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 137 - Polygon - WA - please help

fgeo wrote: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
New poster
Posts: 2
Joined: Tue Feb 17, 2009 3:00 am

### Re: 137 - Polygon - WA - please help

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
New poster
Posts: 1
Joined: Tue Dec 21, 2010 6:15 pm

### Re: 137 - Polygon - WA - please help

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
New poster
Posts: 13
Joined: Fri Apr 27, 2007 12:03 pm
Location: The Netherlands

### Re: 137 - Polygon - WA - please help

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``````
(\__/)
(='.'=) This is Bunny. Copy and paste bunny into
(")_(") your signature to help him gain world domination.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 137 - Polygon - WA - please help

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".
Check input and AC output for thousands of problems on uDebug!

S.H.Bouwhuis
New poster
Posts: 13
Joined: Fri Apr 27, 2007 12:03 pm
Location: The Netherlands

### Re: 137 - Polygon - WA - please help

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.

(\__/)
(='.'=) This is Bunny. Copy and paste bunny into
(")_(") your signature to help him gain world domination.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 137 - Polygon - WA - please help

The problem statement requires that both polygons are convex. This input is not valid for this problem.
Check input and AC output for thousands of problems on uDebug!

S.H.Bouwhuis
New poster
Posts: 13
Joined: Fri Apr 27, 2007 12:03 pm
Location: The Netherlands

### Re: 137 - Polygon - WA - please help

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
(\__/)
(='.'=) This is Bunny. Copy and paste bunny into
(")_(") your signature to help him gain world domination.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 137 - Polygon - WA - please help

Check input and AC output for thousands of problems on uDebug!

S.H.Bouwhuis
New poster
Posts: 13
Joined: Fri Apr 27, 2007 12:03 pm
Location: The Netherlands

### Re: 137 - Polygon - WA - please help

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

Fantastic!!!!!!!!!

This is going to be INCREDIBLY useful!!!
(\__/)
(='.'=) This is Bunny. Copy and paste bunny into
(")_(") your signature to help him gain world domination.

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

### Re: 137 - Polygons

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.