summaryrefslogtreecommitdiff
AgeCommit message (Collapse)Author
2021-10-20Update OWNERS am: f8f41f2483 am: 3a963d93f0 am: 1658bacbc0 am: 3df186b85a ↵t_frc_odp_330442040t_frc_odp_330442000t_frc_con_330443020t_frc_cbr_330443000t_frc_ase_330444010t_frc_art_330443060t_frc_adb_330444000android-13.0.0_r83android-13.0.0_r82android-13.0.0_r81android-13.0.0_r80android-13.0.0_r79android-13.0.0_r78android-13.0.0_r77android-13.0.0_r76android-13.0.0_r75android-13.0.0_r74android-13.0.0_r73android-13.0.0_r72android-13.0.0_r71android-13.0.0_r70android-13.0.0_r69android-13.0.0_r68android-13.0.0_r67android-13.0.0_r66android-13.0.0_r65android-13.0.0_r64android-13.0.0_r63android-13.0.0_r62android-13.0.0_r61android-13.0.0_r60android-13.0.0_r59android-13.0.0_r58android-13.0.0_r57android-13.0.0_r56android-13.0.0_r55android-13.0.0_r54android-13.0.0_r53android-13.0.0_r52android-13.0.0_r51android-13.0.0_r50android-13.0.0_r49android-13.0.0_r48android-13.0.0_r47android-13.0.0_r46android-13.0.0_r45android-13.0.0_r44android-13.0.0_r43android-13.0.0_r42android-13.0.0_r41android-13.0.0_r40android-13.0.0_r39android-13.0.0_r38android-13.0.0_r37android-13.0.0_r36android-13.0.0_r35android-13.0.0_r34android-13.0.0_r33android-13.0.0_r32android-13.0.0_r30android-13.0.0_r29android-13.0.0_r28android-13.0.0_r27android-13.0.0_r24android-13.0.0_r23android-13.0.0_r22android-13.0.0_r21android-13.0.0_r20android-13.0.0_r19android-13.0.0_r18android-13.0.0_r17android-13.0.0_r16aml_uwb_331910010aml_uwb_331820070aml_uwb_331613010aml_uwb_331611010aml_uwb_331410010aml_uwb_331310030aml_uwb_331115000aml_uwb_331015040aml_uwb_330810010aml_tz4_331910000aml_tz4_331314030aml_tz4_331314020aml_tz4_331314010aml_tz4_331012050aml_tz4_331012040aml_tz4_331012000aml_go_wif_330911000aml_go_uwb_330912000aml_go_tz4_330912000aml_go_tet_330914010aml_go_swc_330913000aml_go_sta_330911000aml_go_sdk_330810000aml_go_sch_330911000aml_go_res_330912000aml_go_per_330912000aml_go_odp_330913000aml_go_odp_330912000aml_go_neu_330912000aml_go_net_330913000aml_go_mpr_330912000aml_go_ase_330913000aml_go_ads_330915100aml_go_ads_330915000aml_go_ads_330913000aml_go_adb_330913000aml_ase_331311020aml_ase_331112000aml_ase_331011020aml_ads_331920180aml_ads_331814200aml_ads_331710270aml_ads_331611190aml_ads_331511020aml_ads_331418080aml_ads_331131000android13-qpr3-s9-releaseandroid13-qpr3-s8-releaseandroid13-qpr3-s7-releaseandroid13-qpr3-s6-releaseandroid13-qpr3-s5-releaseandroid13-qpr3-s4-releaseandroid13-qpr3-s3-releaseandroid13-qpr3-s2-releaseandroid13-qpr3-s14-releaseandroid13-qpr3-s13-releaseandroid13-qpr3-s12-releaseandroid13-qpr3-s11-releaseandroid13-qpr3-s10-releaseandroid13-qpr3-s1-releaseandroid13-qpr3-releaseandroid13-qpr3-c-s8-releaseandroid13-qpr3-c-s7-releaseandroid13-qpr3-c-s6-releaseandroid13-qpr3-c-s5-releaseandroid13-qpr3-c-s4-releaseandroid13-qpr3-c-s3-releaseandroid13-qpr3-c-s2-releaseandroid13-qpr3-c-s12-releaseandroid13-qpr3-c-s11-releaseandroid13-qpr3-c-s10-releaseandroid13-qpr3-c-s1-releaseandroid13-qpr2-s9-releaseandroid13-qpr2-s8-releaseandroid13-qpr2-s7-releaseandroid13-qpr2-s6-releaseandroid13-qpr2-s5-releaseandroid13-qpr2-s3-releaseandroid13-qpr2-s2-releaseandroid13-qpr2-s12-releaseandroid13-qpr2-s11-releaseandroid13-qpr2-s10-releaseandroid13-qpr2-s1-releaseandroid13-qpr2-releaseandroid13-qpr2-b-s1-releaseandroid13-qpr1-s8-releaseandroid13-qpr1-s7-releaseandroid13-qpr1-s6-releaseandroid13-qpr1-s5-releaseandroid13-qpr1-s4-releaseandroid13-qpr1-s3-releaseandroid13-qpr1-s2-releaseandroid13-qpr1-s1-releaseandroid13-qpr1-releaseandroid13-mainline-uwb-releaseandroid13-mainline-tzdata4-releaseandroid13-mainline-go-wifi-releaseandroid13-mainline-go-uwb-releaseandroid13-mainline-go-tzdata4-releaseandroid13-mainline-go-tethering-releaseandroid13-mainline-go-sdkext-releaseandroid13-mainline-go-scheduling-releaseandroid13-mainline-go-resolv-releaseandroid13-mainline-go-permission-releaseandroid13-mainline-go-os-statsd-releaseandroid13-mainline-go-odp-releaseandroid13-mainline-go-neuralnetworks-releaseandroid13-mainline-go-networking-releaseandroid13-mainline-go-mediaprovider-releaseandroid13-mainline-go-media-swcodec-releaseandroid13-mainline-go-appsearch-releaseandroid13-mainline-go-adservices-releaseandroid13-mainline-go-adbd-releaseandroid13-mainline-appsearch-releaseandroid13-mainline-adservices-releaseandroid13-frc-odp-releaseandroid13-frc-conscrypt-releaseandroid13-frc-cellbroadcast-releaseandroid13-frc-art-releaseandroid13-frc-adbd-releaseandroid13-devandroid13-d4-s2-releaseandroid13-d4-s1-releaseandroid13-d4-releaseandroid13-d3-s1-releaseandroid13-d2-releaseNeil Fuller
am: 45b25db709 Original change: https://android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/1864565 Change-Id: I5fa30fd27927a2081204a13a07e34909b21011fb
2021-10-20Update OWNERS am: f8f41f2483 am: 3a963d93f0 am: 1658bacbc0 am: 3df186b85aNeil Fuller
Original change: https://android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/1864565 Change-Id: Iffae9486b9e55265fa0ac6ed811ee82518b1dfea
2021-10-20Update OWNERS am: f8f41f2483 am: 3a963d93f0 am: 1658bacbc0Neil Fuller
Original change: https://android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/1864565 Change-Id: I6c8086611b2fc9c83996f972d3397720d80b81a8
2021-10-20Update OWNERS am: f8f41f2483 am: 3a963d93f0Neil Fuller
Original change: https://android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/1864565 Change-Id: I1060d8ca3a58eb5e7a2f65952e8f90781e3b7371
2021-10-20Update OWNERS am: f8f41f2483Neil Fuller
Original change: https://android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/1864565 Change-Id: Ia72d9900eb3467e2ea22f36795db5413511c0558
2021-10-20Update OWNERSNeil Fuller
This project is used by the packages/modules/GeoTZ code so point the OWNERS there. Test: None Change-Id: I9342f5c2af51d0f87b9b6ca5e9d5381405e50f6c
2021-06-02Merge sc-mainline-prodXin Li
Bug: 189946434 Change-Id: Iff3ab8b537d9acf885657cfc4923b3315b5d671b
2021-03-09Merge "Update s2-geometry-library-java-tests to not run in TEST_MAPPING" ↵android-mainline-12.0.0_r99android-mainline-12.0.0_r98android-mainline-12.0.0_r97android-mainline-12.0.0_r96android-mainline-12.0.0_r95android-mainline-12.0.0_r94android-mainline-12.0.0_r93android-mainline-12.0.0_r92android-mainline-12.0.0_r91android-mainline-12.0.0_r90android-mainline-12.0.0_r9android-mainline-12.0.0_r89android-mainline-12.0.0_r88android-mainline-12.0.0_r87android-mainline-12.0.0_r86android-mainline-12.0.0_r85android-mainline-12.0.0_r84android-mainline-12.0.0_r83android-mainline-12.0.0_r82android-mainline-12.0.0_r81android-mainline-12.0.0_r80android-mainline-12.0.0_r8android-mainline-12.0.0_r79android-mainline-12.0.0_r78android-mainline-12.0.0_r77android-mainline-12.0.0_r76android-mainline-12.0.0_r75android-mainline-12.0.0_r74android-mainline-12.0.0_r73android-mainline-12.0.0_r72android-mainline-12.0.0_r71android-mainline-12.0.0_r70android-mainline-12.0.0_r7android-mainline-12.0.0_r69android-mainline-12.0.0_r68android-mainline-12.0.0_r67android-mainline-12.0.0_r66android-mainline-12.0.0_r65android-mainline-12.0.0_r64android-mainline-12.0.0_r63android-mainline-12.0.0_r62android-mainline-12.0.0_r61android-mainline-12.0.0_r60android-mainline-12.0.0_r6android-mainline-12.0.0_r59android-mainline-12.0.0_r58android-mainline-12.0.0_r57android-mainline-12.0.0_r56android-mainline-12.0.0_r53android-mainline-12.0.0_r52android-mainline-12.0.0_r51android-mainline-12.0.0_r50android-mainline-12.0.0_r5android-mainline-12.0.0_r49android-mainline-12.0.0_r48android-mainline-12.0.0_r47android-mainline-12.0.0_r46android-mainline-12.0.0_r45android-mainline-12.0.0_r44android-mainline-12.0.0_r43android-mainline-12.0.0_r42android-mainline-12.0.0_r41android-mainline-12.0.0_r40android-mainline-12.0.0_r39android-mainline-12.0.0_r38android-mainline-12.0.0_r37android-mainline-12.0.0_r35android-mainline-12.0.0_r34android-mainline-12.0.0_r33android-mainline-12.0.0_r32android-mainline-12.0.0_r31android-mainline-12.0.0_r30android-mainline-12.0.0_r3android-mainline-12.0.0_r29android-mainline-12.0.0_r28android-mainline-12.0.0_r27android-mainline-12.0.0_r26android-mainline-12.0.0_r25android-mainline-12.0.0_r24android-mainline-12.0.0_r23android-mainline-12.0.0_r22android-mainline-12.0.0_r21android-mainline-12.0.0_r20android-mainline-12.0.0_r2android-mainline-12.0.0_r19android-mainline-12.0.0_r18android-mainline-12.0.0_r17android-mainline-12.0.0_r16android-mainline-12.0.0_r15android-mainline-12.0.0_r14android-mainline-12.0.0_r13android-mainline-12.0.0_r126android-mainline-12.0.0_r125android-mainline-12.0.0_r124android-mainline-12.0.0_r123android-mainline-12.0.0_r122android-mainline-12.0.0_r121android-mainline-12.0.0_r120android-mainline-12.0.0_r12android-mainline-12.0.0_r119android-mainline-12.0.0_r118android-mainline-12.0.0_r117android-mainline-12.0.0_r116android-mainline-12.0.0_r115android-mainline-12.0.0_r114android-mainline-12.0.0_r113android-mainline-12.0.0_r110android-mainline-12.0.0_r11android-mainline-12.0.0_r109android-mainline-12.0.0_r108android-mainline-12.0.0_r107android-mainline-12.0.0_r106android-mainline-12.0.0_r105android-mainline-12.0.0_r104android-mainline-12.0.0_r103android-mainline-12.0.0_r102android-mainline-12.0.0_r101android-mainline-12.0.0_r100android-mainline-12.0.0_r10android-mainline-12.0.0_r1aml_wif_311811030aml_tz3_311312010aml_tet_311811050aml_sdk_311710000aml_pco_311011000aml_mpr_311911090aml_doc_310851020android12-mainline-wifi-releaseandroid12-mainline-tethering-releaseandroid12-mainline-statsd-releaseandroid12-mainline-sdkext-releaseandroid12-mainline-resolv-releaseandroid12-mainline-permission-releaseandroid12-mainline-neuralnetworks-releaseandroid12-mainline-networkstack-releaseandroid12-mainline-mediaprovider-releaseandroid12-mainline-media-swcodec-releaseandroid12-mainline-media-releaseandroid12-mainline-ipsec-releaseandroid12-mainline-extservices-releaseandroid12-mainline-documentsui-releaseandroid12-mainline-conscrypt-releaseandroid12-mainline-cellbroadcast-releaseandroid12-mainline-captiveportallogin-releaseandroid12-mainline-art-releaseandroid12-mainline-adbd-releaseTreeHugger Robot
into sc-dev am: 68ec31df9a Original change: https://googleplex-android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/13775503 MUST ONLY BE SUBMITTED BY AUTOMERGER Change-Id: I1b9a1769543f749d25a1714023030f96460e21c3
2021-03-09Merge "Update s2-geometry-library-java-tests to not run in TEST_MAPPING" ↵TreeHugger Robot
into sc-dev am: 68ec31df9a Original change: https://googleplex-android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/13775503 MUST ONLY BE SUBMITTED BY AUTOMERGER Change-Id: I856a82853d9aad8e498451b99711e5eecc28a287
2021-03-09Merge "Update s2-geometry-library-java-tests to not run in TEST_MAPPING" ↵android-mainline-12.0.0_r4android-mainline-12.0.0_r36android-12.1.0_r9android-12.1.0_r8android-12.1.0_r7android-12.1.0_r26android-12.1.0_r25android-12.1.0_r24android-12.1.0_r23android-12.1.0_r22android-12.1.0_r21android-12.1.0_r20android-12.1.0_r19android-12.1.0_r18android-12.1.0_r17android-12.1.0_r16android-12.1.0_r15android-12.1.0_r14android-12.1.0_r13android-12.1.0_r12android-12.1.0_r11android-12.1.0_r10android-12.0.0_r32android-12.0.0_r29android-12.0.0_r28android-12.0.0_r27android-12.0.0_r26android-12.0.0_r21android-12.0.0_r20android-12.0.0_r19android-12.0.0_r18android-12.0.0_r16android12L-devandroid12L-d2-s8-releaseandroid12L-d2-s7-releaseandroid12L-d2-s6-releaseandroid12L-d2-s5-releaseandroid12L-d2-s4-releaseandroid12L-d2-s3-releaseandroid12L-d2-s2-releaseandroid12L-d2-s1-releaseandroid12L-d2-releaseandroid12-qpr3-s7-releaseandroid12-qpr3-s6-releaseandroid12-qpr3-s5-releaseandroid12-qpr3-s4-releaseandroid12-qpr3-s3-releaseandroid12-qpr3-s2-releaseandroid12-qpr3-s1-releaseandroid12-qpr3-releaseandroid12-qpr1-releaseandroid12-qpr1-d-s3-releaseandroid12-qpr1-d-s2-releaseandroid12-qpr1-d-s1-releaseandroid12-qpr1-d-releaseandroid12-devandroid12--mainline-releaseTreeHugger Robot
into sc-dev
2021-03-04Update s2-geometry-library-java-tests to not run in TEST_MAPPINGJulien Desprez
With b/180736967, java_test_host unit tests are automatically running in presubmit and do not need an explicit TEST_MAPPING. Change-Id: I3e26866a73336ef60fcfe7289414b1e496067d48 Test: presubmit Bug: 180736967
2021-03-02[LSC] Add LOCAL_LICENSE_KINDS to external/s2-geometry-library-java am: ↵Bob Badour
dae5745741 Original change: https://googleplex-android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/13741148 MUST ONLY BE SUBMITTED BY AUTOMERGER Change-Id: I0c2b27d8a8445deb8e4c082570abd9779b6e2f57
2021-03-02[LSC] Add LOCAL_LICENSE_KINDS to external/s2-geometry-library-java am: ↵Bob Badour
dae5745741 Original change: https://googleplex-android-review.googlesource.com/c/platform/external/s2-geometry-library-java/+/13741148 MUST ONLY BE SUBMITTED BY AUTOMERGER Change-Id: Ic929705b8bb15730a9299595da3bdfebbf2c35bc
2021-03-01[LSC] Add LOCAL_LICENSE_KINDS to external/s2-geometry-library-javaBob Badour
Added SPDX-license-identifier-Apache-2.0 to: Android.bp Bug: 68860345 Bug: 151177513 Bug: 151953481 Test: m all Exempt-From-Owner-Approval: janitorial work Change-Id: I380c23d63e58e94b66ae44db5f4e8e5420869d28
2020-11-20Changes to enable inclusion in the geotz apexNeil Fuller
Anchor the API level the library is compiled against and allow the library to be included in the geotz APEX. The choice of API level 30 is arbitrary - it could be lower but it doesn't need to be. Bug: 152746105 Test: build Change-Id: I7a4cd0b476a8829cd3ff0e88441cc3398268d9fb
2020-08-05Remove a visibility restrictionNeil Fuller
Test: build Bug: 152747091 Change-Id: I34a876afbddc02d4a3a5477a41f2a4590c56b07a
2020-07-20Revert "Remove TEST_MAPPING"Neil Fuller
This corrects the Android.bp and returns the TEST_MAPPING. This reverts commit 081ad246e6d9559f8e5d8d5df99c1edf8515f597. Bug: 161459805 Test: treehugger Change-Id: Iac8c4ae4db4434cf1c2c36b0254363a051fc7c56
2020-07-16Remove TEST_MAPPINGNeil Fuller
The project was just added and it looks like the TEST_MAPPING is causing problems. Removing to fix presubmit. Bug: 161459805 Test: None Change-Id: I2060d2537254f01e91fb31ba89524d6b2fb3d1f9
2020-07-15Add Android files / remove prebuiltsNeil Fuller
Add the license files needed by Android, add Android build rules and remove prebuilts. The build rules include test targets. One of the tests fails already so it is "suppressed" here. Bug: 152746105 Test: atest --host s2-geometry-library-java-tests Test: atest S2GeometryLibraryJavaTests Change-Id: Iaa7033e866a7897dd6ced01ac72b3df051a9975f
2020-07-15Merge remote-tracking branch 'goog/upstream-master' into FirstCommits2Neil Fuller
The initial check-in of upstream code from master. Bug: 152746105 Test: None Change-Id: Ia3e6e5d3ec6f5f2d202d49b295296aaac7a790e1
2020-07-07Initial empty repositoryInna Palant
2011-11-21Inline checkEqualsAndHashCodeMethods calls in preparation for deprecating ↵Chris Povirk
the method. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=25471702
2011-11-21Per discussion with kirilll, some checks that we desire to run at debug time ↵Eric Engle
only have been converted to asserts, and commented out pending an answer from the java libraries team on how best to handle debug time only checks. One of these changes overlaps a change started by ikaushan in CL 25025671 -- hopefully he beats me to the punch. S2EdgeIndex incorrectly copied the S2 Minimum Width metric, rather than referring to the metric in S2Projections. This change should have no effect, except in the case that the projection in S2 is changed, in which case it may work fine now, but would certainly have been incredibly wrong before. Vital performance fixes: - Several classes and methods are now final, to avoid subclasses tampering with them and/or to allow the jvm to apply additional runtime optimizations. - Fixed performance of S2PolygonBuilder#assembleLoop(), which was removing N vertices from the start of an ArrayList *one at a time*, by calling ArrayList.remove(0) N times. Which of course takes N*list.size() steps, aka very quadratic performance in the common case of many loops in the builder. Instead we now call list.subList(n, list.size()), to just skip past the vertices we don't care about. - Fixed S2Polygon.S2PolygonIndex creating a copy of the whole array of vertices in *every call* to edgeFromTo(), because S2Loop's copy constructor was being used, for no apparent reason, which clones the vertices. Since edgeFromTo() is called twice per vertex to create the polygon index, a polygon with N vertices was inadverdantly copying 2*N^2 vertices to build the polygon index. - Fixed performance of S2Polygon#clipBoundary(), which was testing every vertex of a polygon b for containment in polygon a, only to emit a log message that essentially never occurs. In C++, this check is a debug time only check, so the pattern has been followed of making this a commented-out assertion instead of doing this extremely expensive check in production code. Also greatly simplified the addition of edges to the S2PolygonBuilder by relying on the checks already being done in the builder. - Fixed performance of S2Loop#vertex(int), which was doing a check before indexing into the vertices array, which itself does a range check. Since we don't need or want want both checks, the array dereference exception is caught and rethrown so the external behavior of the method is unchanged, but it is now significantly faster. - Fixed performance of S2Polygon.S2LoopSequenceIndex, which was suffering from using List<Integer>. By using int[] instead, we save extra method calls and a lot of boxing/unboxing in this performance critical area. - S2EdgeIndex now stores cells and edges more efficiently in parallel arrays, and edge lookups have been made significantly faster by a local implementation of binary search. - S2EdgeIndex methods getEdgesInParentCells and getEdgesInChildrenCells now take a Set instead of a List that is then filtered through a set. This saves an extra copy of all the edges, and keeps us from accumulating redundant copies of the same edge as the search progresses. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=25397727
2011-11-08Removing very slow precondition checks. Removing these yields 10%Ilyia Kaushansky
speedup of S2Polygon.isValid(). This particular hot spot was identified using YourKit profiler. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=25256987
2011-11-08Split S2Edge and UndirectedEdge up to make equals() method correct.David Beaumont
Before this CL it was possible to have instances of S2Edge such that: a.equals(b) ==/==> b.equals(a) b.equals(a) && b.equals(c) ==/==> a.equals(c) Undirected edges are just fundamentally a different type to an S2Edge and should be treated as such. Additionally they are only used privately in one place and never using polymorphic behaviour. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=25140523
2011-11-08Automatic refactoring to encapsulate fields of R2Vector.David Beaumont
------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=25130844
2011-10-31Made S1Interval and R1Interval immutable.David Beaumont
------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=25081675
2011-10-31Made 'constant' classes fully immutable by either removing or wrapping finalDavid Beaumont
static arrays. The IJ_TO_POS array was never being called so for now I removed it. We can trivially add it back (with appropriate lookup function) if we need it later. The other arrays were wrapped and given (hopefully) better JavaDoc. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=25078833
2011-10-31A tidyup CL for the geometry package. Each change in the CL is isolated to theDavid Beaumont
file it is in, so each file can be reviewed independantly. Basically this tackles some very low hanging fruit with respect to immutability and some minor style issues. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24987273
2011-10-31Needing owners approval for removing final keyword from S2LatLngRect in order toMoritz Neun
fix broken build (http://test/ui#p=geo.gt) of java/com/google/geo/gt/geometry/GTLatLngRect.java (introduced by CL 24952612) Tested: javatests/com/google/common/geometry:all ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24955423
2011-10-31A more complex CL to avoid exposing the 'bounds' arrays from several of theDavid Beaumont
geometry class (paving the way for them to be made immutable later). ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24952612
2011-10-31Removed DoubleMath from geometry package and inlined the one function that wasDavid Beaumont
actually ever being invoked into S2.java. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24952377
2011-10-31The checkEdgeCrossings() method now uses the edge index of the context loop, ↵Eric Engle
instead of iterating over the product of all edges against all other edges filtered only by bounding volume. This method is integral to the performance of intersects(), contains(), containsOrCrosses(), etc. This matches the c++ algorithm in the corresponding method S2Loop::AreBoundariesCrossing. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24938116
2011-10-31Use PrimitiveType.valueOf() or autoboxing (which uses #valueOf) instead of ↵Kurt Kluever
new PrimitiveType(primitive) to enable caching of common primitive values. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24780147
2011-10-31Modify S2EdgeIndex to prune in "XYZ" instead of longitude as it is muchFrank Warmerdam
cheaper to compute from S2Point x/y/z. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24686270
2011-10-14This CL replaces the edge index data structure, aMichael Bolin
TreeMap<S2CellId,TreeSet<Integer>>, with an alternate that is an order of magnitude smaller and faster. Inspiration for this work is owed to Frank Warmerdam, who first recognized the performance consequences of the TreeMap as implemented in Java. Storing the index this way requires 10 fewer references for all edges A that are alone in their cell, and 5 fewer references for all edges B that share a cell. So assuming 64 bits/reference, this saves 80*size(A)+40*size(B) bytes. With the consideration that A>>B for most large real world polygons, the RAM savings here are quite significant. Querying the index this way is also significantly faster. We got the submap of the tree under the cell and tested the size of the submap, but because the cell testing starts at the top and therefore the submaps initially enclose most of the loop's edges, and because size() is a linear operation on a TreeMap's submap, this made index queries linear on the number of elements instead of the expected O(log n). The double binary search to find the edges of the query region is truly O(log N) because size() on a subList() is O(1). The javatests suite passed. A robust set of measurements was taken against the old and new algorithms with millions of real GT polygons. The plot of all these measurements shows quadratic and nearly linear curves for the old and new data structures, respectively. At the low end, constructing S2Polygons with loops just big enough to require an edge index takes essentially the same time as before. Anything above about 5000 vertices is several times faster. And at the high end, constructing huge country polygons, a process that was taking over a minute for the bad cases now takes milliseconds. Incredible find Frank! ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24623432
2011-10-14Performance improvements to S2Loop:Michael Bolin
1. We now cache the edge index in an instance field as the C++ library does, so we don't calculate it more than once. 2. We now use a vertex index to improve findVertex() performance from O(n) to O(1), as the C++ library does. ------------- Created by MOE: http://code.google.com/p/moe-java MOE_MIGRATED_REVID=24293413
2011-09-22Initial import.Michael Bolin
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-12 20:30:31 +0000