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:

Post by rossi kamal » Tue Oct 09, 2007 8:22 am

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

Post by baodog » Wed Oct 10, 2007 9:41 pm

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

Post by cs_lyxab » Thu Oct 09, 2008 11:56 am

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

Post by fgeo » Tue Feb 17, 2009 3:12 am

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

Post by mf » Tue Feb 17, 2009 4:51 am

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

Post by fgeo » Tue Feb 17, 2009 6:26 am

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

Post by tmt » Tue Dec 21, 2010 6:22 pm

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

Post by S.H.Bouwhuis » Sat Mar 31, 2012 3:59 pm

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

Post by brianfry713 » Mon Apr 02, 2012 9:25 pm

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

Post by S.H.Bouwhuis » Tue Apr 03, 2012 4:29 pm

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.

Image
(\__/)
(='.'=) 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

Post by brianfry713 » Wed Apr 04, 2012 1:15 am

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

Post by S.H.Bouwhuis » Sat Aug 11, 2012 3:10 pm

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 :( :-? :x
(\__/)
(='.'=) 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

Post by brianfry713 » Mon Aug 13, 2012 11:09 pm

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

Post by S.H.Bouwhuis » Tue Aug 14, 2012 11:08 am

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

Post by rafastv » Sat Jul 15, 2017 2:23 pm

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.

Post Reply

Return to “Volume 1 (100-199)”