Geometry Boost List: [ggl] Problems with the difference between two polygons

Subject: [ggl] Problems with the difference between two polygons
From: Enrico Leoni (lions.forever)
Date: 2011-08-03 04:19:58

Hi,

On Sun, Jul 31, 2011 at 10:25 PM, Barend Gehrels <barend_at_[hidden]> wrote:

> In the meantime I thought about this define. I think I will move the check to another point in the sources. Actually I don't like this define, people have to define something to get the full (original) speed, while in most cases they will be unaware of this.

Maybe I will wait for this change before updating my blog post.

As you asked, these are the results of the three tests with the
"define" (using Boost.Polygon, Boost.Geometry and Clipper):

1)

TS Gtl        l 050 ms/l 0000000 PS 00003 VS 00000018 PR 000002 VR 000000012
TS Gtl        l 050 ms/l 0000000 PS 00003 VS 00000018 PR 000002 VR 000000012
TS Gtl        l 050 ms/l 0000001 PS 00005 VS 00000040 PR 000006 VR 000000038
TS Gtl        l 050 ms/l 0000002 PS 00009 VS 00000068 PR 000010 VR 000000067
TS Gtl        l 050 ms/l 0000002 PS 00009 VS 00000088 PR 000014 VR 000000076
TS Gtl        l 050 ms/l 0000003 PS 00011 VS 00000106 PR 000018 VR 000000098
TS Gtl        l 050 ms/l 0000004 PS 00011 VS 00000130 PR 000022 VR 000000143
TS Gtl        l 050 ms/l 0000005 PS 00013 VS 00000152 PR 000026 VR 000000170
TS Gtl        l 050 ms/l 0000005 PS 00011 VS 00000154 PR 000030 VR 000000178
TS Gtl        l 015 ms/l 0000012 PS 00017 VS 00000304 PR 000060 VR 000000353
TS Gtl        l 015 ms/l 0000017 PS 00019 VS 00000418 PR 000090 VR 000000575
TS Gtl        l 015 ms/l 0000024 PS 00023 VS 00000550 PR 000120 VR 000000789
TS Gtl        l 015 ms/l 0000030 PS 00027 VS 00000698 PR 000150 VR 000000903
TS Gtl        l 015 ms/l 0000037 PS 00029 VS 00000808 PR 000180 VR 000001168
TS Gtl        l 015 ms/l 0000042 PS 00029 VS 00000928 PR 000210 VR 000001351
TS Gtl        l 015 ms/l 0000047 PS 00031 VS 00001054 PR 000240 VR 000001483
TS Gtl        l 015 ms/l 0000054 PS 00035 VS 00001186 PR 000270 VR 000001666
TS Gtl        l 015 ms/l 0000063 PS 00037 VS 00001328 PR 000300 VR 000001922
TS Gtl        l 005 ms/l 0000133 PS 00049 VS 00002548 PR 000600 VR 000003881
TS Gtl        l 005 ms/l 0000210 PS 00061 VS 00003780 PR 000900 VR 000005767
TS Gtl        l 005 ms/l 0000285 PS 00071 VS 00005110 PR 001200 VR 000007790
TS Gtl        l 005 ms/l 0000362 PS 00079 VS 00006318 PR 001500 VR 000009721
TS Gtl        l 005 ms/l 0000453 PS 00087 VS 00007478 PR 001800 VR 000011429
TS Gtl        l 005 ms/l 0000532 PS 00093 VS 00008740 PR 002100 VR 000013432
TS Gtl        l 005 ms/l 0000616 PS 00099 VS 00009898 PR 002400 VR 000015555
TS Gtl        l 005 ms/l 0000727 PS 00105 VS 00011128 PR 002700 VR 000017229
TS Gtl        l 005 ms/l 0000851 PS 00111 VS 00012430 PR 003000 VR 000019455
TS Gtl        l 002 ms/l 0001795 PS 00157 VS 00024488 PR 006000 VR 000038769
TS Gtl        l 002 ms/l 0004051 PS 00221 VS 00049060 PR 012000 VR 000077596
TS Gtl        l 002 ms/l 0006416 PS 00271 VS 00073166 PR 018000 VR 000116743
TS Gtl        l 002 ms/l 0009010 PS 00311 VS 00097030 PR 024000 VR 000155545
TS Gtl        l 002 ms/l 0011954 PS 00349 VS 00121448 PR 030000 VR 000195122
TS Gtl        l 001 ms/l 0026460 PS 00491 VS 00241570 PR 060000 VR 000389617
TS Gtl        l 001 ms/l 0065071 PS 00695 VS 00482326 PR 120001 VR 000779497
TS Gtl        l 001 ms/l 0104971 PS 00851 VS 00723346 PR 180021 VR 001167318
TS Ggl        l 050 ms/l 0000000 PS 00003 VS 00000018 PR 000002 VR 000000012
TS Ggl        l 050 ms/l 0000000 PS 00003 VS 00000018 PR 000002 VR 000000012
TS Ggl        l 050 ms/l 0000000 PS 00005 VS 00000040 PR 000006 VR 000000042
TS Ggl        l 050 ms/l 0000000 PS 00009 VS 00000068 PR 000010 VR 000000067
TS Ggl        l 050 ms/l 0000000 PS 00009 VS 00000088 PR 000014 VR 000000076
TS Ggl        l 050 ms/l 0000001 PS 00011 VS 00000106 PR 000018 VR 000000098
TS Ggl        l 050 ms/l 0000001 PS 00011 VS 00000130 PR 000022 VR 000000154
TS Ggl        l 050 ms/l 0000001 PS 00013 VS 00000152 PR 000026 VR 000000179
TS Ggl        l 050 ms/l 0000001 PS 00011 VS 00000154 PR 000030 VR 000000190
TS Ggl        l 015 ms/l 0000002 PS 00017 VS 00000304 PR 000060 VR 000000360
TS Ggl        l 015 ms/l 0000002 PS 00019 VS 00000418 PR 000090 VR 000000604
TS Ggl        l 015 ms/l 0000003 PS 00023 VS 00000550 PR 000120 VR 000000819
TS Ggl        l 015 ms/l 0000004 PS 00027 VS 00000698 PR 000150 VR 000000955
TS Ggl        l 015 ms/l 0000005 PS 00029 VS 00000808 PR 000180 VR 000001247
TS Ggl        l 015 ms/l 0000006 PS 00029 VS 00000928 PR 000210 VR 000001456
TS Ggl        l 015 ms/l 0000006 PS 00031 VS 00001054 PR 000240 VR 000001580
TS Ggl        l 015 ms/l 0000007 PS 00035 VS 00001186 PR 000270 VR 000001771
TS Ggl        l 015 ms/l 0000008 PS 00037 VS 00001328 PR 000300 VR 000002068
TS Ggl        l 005 ms/l 0000016 PS 00049 VS 00002548 PR 000600 VR 000004155
TS Ggl        l 005 ms/l 0000025 PS 00061 VS 00003780 PR 000900 VR 000006194
TS Ggl        l 005 ms/l 0000035 PS 00071 VS 00005110 PR 001200 VR 000008456
TS Ggl        l 005 ms/l 0000043 PS 00079 VS 00006318 PR 001500 VR 000010347
TS Ggl        l 005 ms/l 0000054 PS 00087 VS 00007478 PR 001800 VR 000012326
TS Ggl        l 005 ms/l 0000064 PS 00093 VS 00008740 PR 002100 VR 000014471
TS Ggl        l 005 ms/l 0000075 PS 00099 VS 00009898 PR 002400 VR 000016663
TS Ggl        l 005 ms/l 0000083 PS 00105 VS 00011128 PR 002700 VR 000018538
TS Ggl        l 005 ms/l 0000093 PS 00111 VS 00012430 PR 003000 VR 000021014
TS Ggl        l 002 ms/l 0000208 PS 00157 VS 00024488 PR 006000 VR 000041889
TS Ggl        l 002 ms/l 0000524 PS 00221 VS 00049060 PR 012000 VR 000083679
TS Ggl        l 002 ms/l 0000771 PS 00271 VS 00073166 PR 018000 VR 000125374
TS Ggl        l 002 ms/l 0001275 PS 00311 VS 00097030 PR 024000 VR 000167179
TS Ggl        l 002 ms/l 0001625 PS 00349 VS 00121448 PR 030000 VR 000209737
TS Ggl        l 001 ms/l 0003876 PS 00491 VS 00241570 PR 060000 VR 000420084
TS Ggl        l 001 ms/l 0007332 PS 00695 VS 00482326 PR 120000 VR 000839967
TS Ggl        l 001 ms/l 0011115 PS 00851 VS 00723346 PR 180000 VR 001256218
TS Clipper    l 050 ms/l 0000000 PS 00003 VS 00000018 PR 000002 VR 000000010
TS Clipper    l 050 ms/l 0000000 PS 00003 VS 00000018 PR 000002 VR 000000010
TS Clipper    l 050 ms/l 0000000 PS 00005 VS 00000040 PR 000006 VR 000000028
TS Clipper    l 050 ms/l 0000000 PS 00009 VS 00000068 PR 000010 VR 000000046
TS Clipper    l 050 ms/l 0000000 PS 00009 VS 00000088 PR 000014 VR 000000062
TS Clipper    l 050 ms/l 0000000 PS 00011 VS 00000106 PR 000018 VR 000000080
TS Clipper    l 050 ms/l 0000000 PS 00011 VS 00000130 PR 000022 VR 000000100
TS Clipper    l 050 ms/l 0000000 PS 00013 VS 00000152 PR 000026 VR 000000118
TS Clipper    l 050 ms/l 0000000 PS 00011 VS 00000154 PR 000030 VR 000000130
TS Clipper    l 015 ms/l 0000001 PS 00017 VS 00000304 PR 000060 VR 000000254
TS Clipper    l 015 ms/l 0000001 PS 00019 VS 00000418 PR 000090 VR 000000392
TS Clipper    l 015 ms/l 0000002 PS 00023 VS 00000550 PR 000120 VR 000000509
TS Clipper    l 015 ms/l 0000002 PS 00027 VS 00000698 PR 000150 VR 000000629
TS Clipper    l 015 ms/l 0000003 PS 00029 VS 00000808 PR 000180 VR 000000770
TS Clipper    l 015 ms/l 0000003 PS 00029 VS 00000928 PR 000210 VR 000000917
TS Clipper    l 015 ms/l 0000004 PS 00031 VS 00001054 PR 000240 VR 000001038
TS Clipper    l 015 ms/l 0000005 PS 00035 VS 00001186 PR 000270 VR 000001180
TS Clipper    l 015 ms/l 0000005 PS 00037 VS 00001328 PR 000300 VR 000001291
TS Clipper    l 005 ms/l 0000013 PS 00049 VS 00002548 PR 000600 VR 000002643
TS Clipper    l 005 ms/l 0000024 PS 00061 VS 00003780 PR 000900 VR 000004070
TS Clipper    l 005 ms/l 0000036 PS 00071 VS 00005110 PR 001200 VR 000005189
TS Clipper    l 005 ms/l 0000049 PS 00079 VS 00006318 PR 001500 VR 000006477
TS Clipper    l 005 ms/l 0000066 PS 00087 VS 00007478 PR 001800 VR 000007893
TS Clipper    l 005 ms/l 0000082 PS 00093 VS 00008740 PR 002100 VR 000008901
TS Clipper    l 005 ms/l 0000098 PS 00099 VS 00009898 PR 002400 VR 000010561
TS Clipper    l 005 ms/l 0000121 PS 00105 VS 00011128 PR 002700 VR 000011600
TS Clipper    l 005 ms/l 0000146 PS 00111 VS 00012430 PR 003000 VR 000013000
TS Clipper    l 002 ms/l 0000445 PS 00157 VS 00024488 PR 006000 VR 000026037
TS Clipper    l 002 ms/l 0001330 PS 00221 VS 00049060 PR 012000 VR 000051630
TS Clipper    l 002 ms/l 0002508 PS 00271 VS 00073166 PR 018000 VR 000076945
TS Clipper    l 002 ms/l 0003866 PS 00311 VS 00097030 PR 024000 VR 000102435
TS Clipper    l 002 ms/l 0005451 PS 00349 VS 00121448 PR 030000 VR 000127759
TS Clipper    l 001 ms/l 0015333 PS 00491 VS 00241570 PR 060000 VR 000258119
TS Clipper    l 001 ms/l 0043371 PS 00695 VS 00482326 PR 120000 VR 000520139
TS Clipper    l 001 ms/l 0079335 PS 00851 VS 00723346 PR 180000 VR 000771276

2) (only the last three iterations)

TR Gtl        l 005 ms/l 0001885 PS 03353 VS 00049544 PR 05671 VR 00048887
TR Ggl        l 005 ms/l 0000732 PS 03353 VS 00049544 PR 05672 VR 00048889
TR Clipper    l 005 ms/l 0002869 PS 03353 VS 00049544 PR 05671 VR 00043215
TR Gtl        l 005 ms/l 0001915 PS 03560 VS 00051344 PR 05886 VR 00049914
TR Ggl        l 005 ms/l 0000781 PS 03560 VS 00051344 PR 05887 VR 00049916
TR Clipper    l 005 ms/l 0003021 PS 03560 VS 00051344 PR 05886 VR 00044027
TR Gtl        l 005 ms/l 0001942 PS 03757 VS 00053078 PR 06108 VR 00050830
TR Ggl        l 005 ms/l 0000848 PS 03757 VS 00053078 PR 06109 VR 00050832
TR Clipper    l 005 ms/l 0003192 PS 03757 VS 00053078 PR 06108 VR 00044718

3)

TSW Gtl             l 0005 ms 0012479 ms/l 0002496 VS 00174239 VR 0000050197
TSW Ggl             l 0005 ms 0000533 ms/l 0000107 VS 00174239 VR 0000050197
TSW Clipper         l 0005 ms 0000853 ms/l 0000171 VS 00174239 VR 0000050186

For curiosity, these are obtained using TTMath (and the "define"):

1)

TS Ggl        l 050 ms/l 0000005 PS 00003 VS 00000018 PR 000002 VR 000000014
TS Ggl        l 050 ms/l 0000005 PS 00003 VS 00000018 PR 000002 VR 000000014
TS Ggl        l 050 ms/l 0000016 PS 00005 VS 00000040 PR 000006 VR 000000040
TS Ggl        l 050 ms/l 0000030 PS 00009 VS 00000068 PR 000010 VR 000000069
TS Ggl        l 050 ms/l 0000038 PS 00009 VS 00000088 PR 000014 VR 000000093
TS Ggl        l 050 ms/l 0000052 PS 00011 VS 00000106 PR 000018 VR 000000123
TS Ggl        l 050 ms/l 0000063 PS 00011 VS 00000130 PR 000022 VR 000000144
TS Ggl        l 050 ms/l 0000075 PS 00013 VS 00000152 PR 000026 VR 000000164
TS Ggl        l 050 ms/l 0000080 PS 00011 VS 00000154 PR 000030 VR 000000206
TS Ggl        l 015 ms/l 0000161 PS 00017 VS 00000304 PR 000060 VR 000000396
TS Ggl        l 015 ms/l 0000237 PS 00019 VS 00000418 PR 000090 VR 000000645
TS Ggl        l 015 ms/l 0000318 PS 00023 VS 00000550 PR 000120 VR 000000818
TS Ggl        l 015 ms/l 0000399 PS 00027 VS 00000698 PR 000150 VR 000001011
TS Ggl        l 015 ms/l 0000480 PS 00029 VS 00000808 PR 000180 VR 000001225
TS Ggl        l 015 ms/l 0000552 PS 00029 VS 00000928 PR 000210 VR 000001498
TS Ggl        l 015 ms/l 0000630 PS 00031 VS 00001054 PR 000240 VR 000001707
TS Ggl        l 015 ms/l 0000716 PS 00035 VS 00001186 PR 000272 VR 000001904
TS Ggl        l 015 ms/l 0000803 PS 00037 VS 00001328 PR 000302 VR 000002089
TS Ggl        l 005 ms/l 0001582 PS 00049 VS 00002548 PR 000600 VR 000004196
TS Ggl        l 005 ms/l 0002356 PS 00061 VS 00003780 PR 000900 VR 000006304
TS Ggl        l 005 ms/l 0003198 PS 00071 VS 00005110 PR 001200 VR 000008489
TS Ggl        l 005 ms/l 0003977 PS 00079 VS 00006318 PR 001506 VR 000010316
TS Ggl        l 005 ms/l 0004743 PS 00087 VS 00007478 PR 001806 VR 000012655
TS Ggl        l 005 ms/l 0005562 PS 00093 VS 00008740 PR 002102 VR 000014709
TS Ggl        l 005 ms/l 0006364 PS 00099 VS 00009898 PR 002400 VR 000016763
TS Ggl        l 005 ms/l 0007147 PS 00105 VS 00011128 PR 002702 VR 000018401
TS Ggl        l 005 ms/l 0007986 PS 00111 VS 00012430 PR 003004 VR 000021541
TS Ggl        l 002 ms/l 0016003 PS 00157 VS 00024488 PR 006002 VR 000041232
TS Ggl        l 002 ms/l 0032616 PS 00221 VS 00049060 PR 012016 VR 000085618
TS Ggl        l 002 ms/l 0049787 PS 00271 VS 00073166 PR 018015 VR 000123666
TS Ggl        l 002 ms/l 0066128 PS 00311 VS 00097030 PR 024001 VR 000170175
TS Ggl        l 002 ms/l 0082892 PS 00349 VS 00121448 PR 030018 VR 000205083
TS Ggl        l 001 ms/l 0168037 PS 00491 VS 00241570 PR 060001 VR 000425578
TS Ggl        l 001 ms/l 0340312 PS 00695 VS 00482326 PR 120062 VR 000841221
TS Ggl        l 001 ms/l 0517213 PS 00851 VS 00723346 PR 180044 VR 001285744

2) (only the last three iterations, and the polygons, being generated
randomly, are not the same of the test executed with "double"
coordinates)

TR Ggl        l 005 ms/l 0013940 PS 03444 VS 00049272 PR 05786 VR 00049204
TR Ggl        l 005 ms/l 0014394 PS 03618 VS 00051004 PR 05996 VR 00050232
TR Ggl        l 005 ms/l 0014842 PS 03813 VS 00052834 PR 06213 VR 00051214

3)

TSW Ggl             l 0005 ms 0005568 ms/l 0001114 VS 00174239 VR 0000050197

> I understand. Great you consider adding SqlGeometry/GEOS. If you want, I can put your sources (when you're ready with them) there, I've an account, so they are saved, at a central place, and waiting for a future someone continuing the research.

Accorded!

Regards, Enrico