Page 3 of 3

Posted: Tue Oct 09, 2007 8:22 am
by 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?

Posted: Wed Oct 10, 2007 9:41 pm
by 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."

137 keep getting WA

Posted: Thu Oct 09, 2008 11:56 am
by 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

Re: 137 - Polygon - WA - please help

Posted: Tue Feb 17, 2009 3:12 am
by 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?

Re: 137 - Polygon - WA - please help

Posted: Tue Feb 17, 2009 4:51 am
by mf
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...

Re: 137 - Polygon - WA - please help

Posted: Tue Feb 17, 2009 6:26 am
by 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.

Re: 137 - Polygon - WA - please help

Posted: Tue Dec 21, 2010 6:22 pm
by 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 :)

Re: 137 - Polygon - WA - please help

Posted: Sat Mar 31, 2012 3:59 pm
by 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

Re: 137 - Polygon - WA - please help

Posted: Mon Apr 02, 2012 9:25 pm
by 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".

Re: 137 - Polygon - WA - please help

Posted: Tue Apr 03, 2012 4:29 pm
by 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.

Image

Re: 137 - Polygon - WA - please help

Posted: Wed Apr 04, 2012 1:15 am
by brianfry713
The problem statement requires that both polygons are convex. This input is not valid for this problem.

Re: 137 - Polygon - WA - please help

Posted: Sat Aug 11, 2012 3:10 pm
by 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 :( :-? :x

Re: 137 - Polygon - WA - please help

Posted: Mon Aug 13, 2012 11:09 pm
by brianfry713

Re: 137 - Polygon - WA - please help

Posted: Tue Aug 14, 2012 11:08 am
by S.H.Bouwhuis
Oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooohhhhhhhhhhhhhhhhhhhhhhhhhh!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Fantastic!!!!!!!!!

This is going to be INCREDIBLY useful!!!

Re: 137 - Polygons

Posted: Sat Jul 15, 2017 2:23 pm
by 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.