You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sedona.apache.org by ji...@apache.org on 2021/05/26 04:01:47 UTC
[incubator-sedona] branch master updated: [Sedona-27] Add
ST_Subdivide and ST_SubdivideExplode functions. (#528)
This is an automated email from the ASF dual-hosted git repository.
jiayu pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-sedona.git
The following commit(s) were added to refs/heads/master by this push:
new 55311f8 [Sedona-27] Add ST_Subdivide and ST_SubdivideExplode functions. (#528)
55311f8 is described below
commit 55311f82b9a7c3ba6d215710c576134d1817edb6
Author: Paweł Kociński <pa...@gmail.com>
AuthorDate: Wed May 26 06:01:24 2021 +0200
[Sedona-27] Add ST_Subdivide and ST_SubdivideExplode functions. (#528)
* Add st subdivide.
* Update documentation.
* Add lateral view tests with st subdivide.
* Move isEmpty to upper scope implicits.
* Move isEmpty to upper scope implicits.
* Add python tests for subdivide.
* Update docs for dub divide explode.
* Reformat docs.
* Remove not used slashes.
* Fix issue with licence comment.
---
.../subdivide/subdivide_expected_result.txt | 70 ++++++++++
.../subdivide/subdivide_input_geometries.txt | 9 ++
docs/api/sql/Function.md | 115 ++++++++++++++++
python/tests/sql/test_function.py | 57 +++++++-
.../scala/org/apache/sedona/sql/UDF/Catalog.scala | 4 +-
.../sql/sedona_sql/expressions/Functions.scala | 47 ++++++-
.../sql/sedona_sql/expressions/implicits.scala | 3 +-
.../expressions/simplify/CircleSimplifier.scala | 27 ++++
.../simplify/CoordinatesSimplifier.scala | 69 ++++++++++
.../expressions/simplify/CoordinatesSplitter.scala | 82 ++++++++++++
.../simplify/GeometryCollectionSimplifier.scala | 52 ++++++++
.../expressions/simplify/GeometrySimplifier.scala | 50 +++++++
.../simplify/LinestringSimplifier.scala | 42 ++++++
.../expressions/simplify/PolygonSimplifier.scala | 50 +++++++
.../simplify/SimplifyingParameters.scala | 24 ++++
.../expressions/subdivide/GeometrySubDivider.scala | 148 +++++++++++++++++++++
.../GeometrySubDividerConfiguration.scala | 28 ++++
.../expressions/subdivide/PivotFinder.scala | 50 +++++++
.../sedona_sql/expressions/subdivide/Stack.scala | 40 ++++++
.../expressions/subdivide/SubdivideExtent.scala | 35 +++++
.../ZeroToleranceGeometrySimplifier.scala | 65 +++++++++
.../org/apache/sedona/sql/functionTestScala.scala | 105 +++++++++++++++
.../sedona/sql/functions/FunctionsHelper.scala | 32 +++++
.../sql/functions/TestGeometrySimplify.scala | 142 ++++++++++++++++++++
.../sedona/sql/functions/TestStSubDivide.scala | 101 ++++++++++++++
25 files changed, 1443 insertions(+), 4 deletions(-)
diff --git a/core/src/test/resources/subdivide/subdivide_expected_result.txt b/core/src/test/resources/subdivide/subdivide_expected_result.txt
new file mode 100644
index 0000000..7d9831f
--- /dev/null
+++ b/core/src/test/resources/subdivide/subdivide_expected_result.txt
@@ -0,0 +1,70 @@
+1;POINT (21 52)
+2;LINESTRING (0 0, 85 85, 100 100)
+3;LINESTRING (0 0, 85 85)
+4;LINESTRING (0 0, 5 5)
+4;LINESTRING (5 5, 10 10)
+4;LINESTRING (10 10, 21 21)
+4;LINESTRING (21 21, 60 60)
+4;LINESTRING (60 60, 85 85)
+4;LINESTRING (85 85, 100 100)
+4;LINESTRING (100 100, 120 120)
+5;LINESTRING (0 0, 3 0)
+5;LINESTRING (3 0, 6 0)
+6;POLYGON ((119 23, 85 35, 68 29, 66 28, 32 56, 22 64, 29.82608695652174 100, 119 100, 119 23))
+6;POLYGON ((132 10, 119 23, 119 56, 186 56, 186 52, 178 34, 168 18, 147 13, 132 10))
+6;POLYGON ((119 56, 119 100, 190 100, 185 79, 186 56, 119 56))
+6;POLYGON ((29.82608695652174 100, 32 110, 40 119, 36 150, 57 158, 75 171, 92 182, 114 184, 114 100, 29.82608695652174 100))
+6;POLYGON ((114 184, 132 186, 146 178, 176 184, 179 162, 184 141, 190 122, 190 100, 114 100, 114 184))
+7;POLYGON ((37.857142857142854 20, 35 10, 10 20, 37.857142857142854 20))
+7;POLYGON ((15 20, 10 20, 15 40, 15 20))
+7;POLYGON ((20 20, 15 20, 15 30, 20 30, 20 20))
+7;POLYGON ((26.428571428571427 20, 20 20, 20 30, 26.428571428571427 23.571428571428573, 26.428571428571427 20))
+7;POLYGON ((15 30, 15 40, 20 40, 20 30, 15 30))
+7;POLYGON ((20 40, 26.428571428571427 40, 26.428571428571427 32.142857142857146, 20 30, 20 40))
+7;POLYGON ((37.857142857142854 20, 30 20, 34.04761904761905 32.142857142857146, 37.857142857142854 32.142857142857146, 37.857142857142854 20))
+7;POLYGON ((34.04761904761905 34.682539682539684, 26.428571428571427 32.142857142857146, 26.428571428571427 40, 34.04761904761905 40, 34.04761904761905 34.682539682539684))
+7;POLYGON ((34.04761904761905 32.142857142857146, 35 35, 37.857142857142854 35, 37.857142857142854 32.142857142857146, 34.04761904761905 32.142857142857146))
+7;POLYGON ((35 35, 34.04761904761905 34.682539682539684, 34.04761904761905 35, 35 35))
+7;POLYGON ((34.04761904761905 35, 34.04761904761905 40, 37.857142857142854 40, 37.857142857142854 35, 34.04761904761905 35))
+7;POLYGON ((30 20, 26.428571428571427 20, 26.428571428571427 23.571428571428573, 30 20))
+7;POLYGON ((15 40, 37.857142857142854 43.80952380952381, 37.857142857142854 40, 15 40))
+7;POLYGON ((45 45, 37.857142857142854 20, 37.857142857142854 43.80952380952381, 45 45))
+8;POLYGON ((21.101965615 52.2808580120001, 21.10187144 52.2810704710001, 21.101732215 52.2813843490001, 21.101663257 52.2815396240001, 21.101595903 52.2816913940001, 21.101476065 52.2819618440001, 21.1014071060001 52.2821170300001, 21.101387862 52.282160547, 21.1013190480001 52.282315732, 21.1011774830001 52.2826348240001, 21.1008815160001 52.283302049, 21.1008019080001 52.2834811500001, 21.1007981170001 52.2834895120001, 21.1007508870001 52.28360001, 21.101965615 52.28360001, 21.1019656 [...]
+8;POLYGON ((21.1007508870001 52.28360001, 21.1006999800001 52.2837046700001, 21.100648649 52.283816609, 21.100616712 52.283885662, 21.100586961 52.283949679, 21.1005235430001 52.284095602, 21.1004299590001 52.284316507, 21.1002695070001 52.284714256, 21.1002645400001 52.2847211810001, 21.10025431 52.284733772, 21.1002283 52.2847677670001, 21.10022523 52.284771006, 21.10019469 52.284810307, 21.100181101 52.2848282040001, 21.100167658 52.2848459210001, 21.100166636 52.2848472700001, 21.099 [...]
+8;POLYGON ((21.098800501 52.28643177, 21.098554936 52.286327359, 21.0985294110001 52.286316506, 21.098504033 52.2863057420001, 21.0984724940001 52.286292286, 21.098301156 52.2862193600001, 21.0980915580001 52.2861417010001, 21.098069652 52.2861765920001, 21.097797816 52.2861867930001, 21.0975989570001 52.2861943280001, 21.097528031 52.286196993, 21.097272021 52.286206641, 21.09709573 52.286213257, 21.097022752 52.2862160130001, 21.0969959330001 52.2862164840001, 21.09686272 52.2862186610 [...]
+8;POLYGON ((21.098965099635503 52.28643177, 21.098925045 52.2864846030001, 21.098800501 52.28643177, 21.09575402020671 52.28643177, 21.0957129060001 52.2865163700001, 21.0954257550001 52.2871077180001, 21.0953914350001 52.287164008, 21.095378582 52.28718451, 21.0952256200001 52.287478708, 21.095224891 52.2874805060001, 21.095045526 52.2878336840001, 21.0950309360001 52.2878647030001, 21.0949380010001 52.288062955, 21.094917116 52.288097125, 21.0952012880001 52.2881612470001, 21.093976704 [...]
+8;POLYGON ((21.105009379 52.2739940060001, 21.104849067 52.2743557210001, 21.104604657 52.27490679, 21.104494038 52.2751564750001, 21.1044055690001 52.2753557190001, 21.1041884050001 52.2758455570001, 21.1041803910001 52.2758648880001, 21.1040123390001 52.2762434150001, 21.1037826310001 52.2767617540001, 21.103633959 52.277096944, 21.1030614040001 52.27838753, 21.1028372110001 52.278892291, 21.10274975 52.279090185, 21.102595814 52.2794370610001, 21.1025759890001 52.279481837, 21.1024778 [...]
+8;POLYGON ((21.1078766420001 52.2808580120001, 21.112551475 52.2808580120001, 21.112551475 52.27489222785824, 21.111602314 52.2747830060001, 21.1110978560001 52.2747244330001, 21.111011094 52.2747148070001, 21.1104146000001 52.274645982, 21.1102585150001 52.2746279730001, 21.1101506480001 52.274615581, 21.1101188440001 52.274611566, 21.109627727 52.2745548620001, 21.108325113 52.2744003980001, 21.108008985 52.274361771, 21.1078766420001 52.2743455340001, 21.1078766420001 52.2808580120001))
+8;POLYGON ((21.101965615 52.2808580120001, 21.101965615 52.2920242180001, 21.112551475 52.2920242180001, 21.112551475 52.2808580120001, 21.101965615 52.2808580120001))
+8;POLYGON ((21.0907750110001 52.292576997306114, 21.089866253 52.2934904970001, 21.08957164 52.293786593, 21.0879453260001 52.2954087300001, 21.0879358180001 52.295418623, 21.0878929520001 52.2954608970001, 21.0878686670001 52.295485091, 21.0878578410001 52.295495885, 21.0878350190001 52.2955189100001, 21.087804443 52.2955495800001, 21.0877968350001 52.2955566860001, 21.0875740880001 52.2955147000001, 21.0873820150001 52.2958637410001, 21.0862661800001 52.297891625, 21.086246021 52.29792 [...]
+8;POLYGON ((21.08579288 52.2987516330001, 21.0856494240001 52.299011659, 21.085642998 52.2990240660001, 21.0856156790001 52.299073428, 21.0855649860001 52.299164869, 21.085522933 52.29925136, 21.08542612 52.2994494270001, 21.0854230530001 52.2994553610001, 21.085393848 52.2995152390001, 21.084289545 52.301535905, 21.0841132030001 52.301858146, 21.083958191 52.3021420840001, 21.083569116 52.302853908, 21.0840151260001 52.3029440970001, 21.0855139180001 52.303247431, 21.0855935590001 52.30 [...]
+8;POLYGON ((21.091324921 52.2920242180001, 21.0907750110001 52.292576997306114, 21.0907750110001 52.304374054, 21.098032592 52.304374054, 21.098032592 52.2920242180001, 21.091324921 52.2920242180001))
+8;POLYGON ((21.0907750110001 52.304374054, 21.090918018 52.304401985, 21.0911667820001 52.3044532920001, 21.09143096 52.3045139340001, 21.091519987 52.304528964, 21.091845001 52.3045842550001, 21.0918479330001 52.304584253, 21.091989466 52.30460814, 21.0921670970001 52.304646468, 21.092487009 52.304715243, 21.092792101 52.3047780970001, 21.093005227 52.3048219680001, 21.093413135 52.3049023550001, 21.0937192320001 52.3049537910001, 21.0937913930001 52.3049658670001, 21.0938796880001 52.3 [...]
+8;POLYGON ((21.0943136340001 52.3050313300001, 21.0945732060001 52.305059344, 21.0946224350001 52.305043486, 21.0949183770001 52.3050756040001, 21.094952547 52.3050792610001, 21.0950277630001 52.3050801900001, 21.0951183870001 52.3050870370001, 21.095403768 52.3051167360001, 21.095640153 52.3051345200001, 21.0957911150001 52.3051775380001, 21.0959356380001 52.305225953, 21.0960236550001 52.305247722, 21.0961706300001 52.305277351, 21.096365147 52.3053242880001, 21.096777069 52.3054247920 [...]
+8;POLYGON ((21.112551475 52.3057045290001, 21.112551475 52.2920242180001, 21.098032592 52.2920242180001, 21.098032592 52.3057045290001, 21.112551475 52.3057045290001))
+8;POLYGON ((21.098032592 52.3057045290001, 21.0981996730001 52.3057414190001, 21.098572269 52.3058238840001, 21.0986089420001 52.3058320320001, 21.09870399 52.3058494790001, 21.0987541550001 52.3058586940001, 21.0990921050001 52.3059207850001, 21.099179382 52.3059378780001, 21.099234242 52.3059486170001, 21.099532153 52.306004988, 21.0997042130001 52.306038277, 21.0997601 52.3060491040001, 21.099902677 52.3060764860001, 21.0999701530001 52.3060901800001, 21.100248267 52.30614396, 21.1007 [...]
+8;POLYGON ((21.101745782 52.3064345060001, 21.1018288110001 52.3064526790001, 21.101857415 52.306458137, 21.102218851 52.3065277480001, 21.1023455920001 52.306553523, 21.102639702 52.306610968, 21.1028488790001 52.3066515, 21.103517341 52.3067822250001, 21.1038444600001 52.3068465580001, 21.1038806930001 52.306853716, 21.104120531 52.3069006900001, 21.1042664880001 52.3069292320001, 21.104392789 52.3069539260001, 21.1046848500001 52.3070109180001, 21.104706121 52.307015124, 21.1047520290 [...]
+8;POLYGON ((21.105435723 52.307140481, 21.1056413850001 52.3071802920001, 21.1062398870001 52.307295605, 21.1066418230001 52.3073728960001, 21.1070816120001 52.3074591380001, 21.1071042030001 52.3074636110001, 21.107360634 52.307517574, 21.1076670900001 52.3075819160001, 21.10786675 52.3076242450001, 21.1081906650001 52.307692434, 21.1083363390001 52.3077230380001, 21.10858382 52.3077732310001, 21.108936773 52.3078430990001, 21.109239411 52.307903126, 21.1095556920001 52.3079658360001, 2 [...]
+8;POLYGON ((21.1198043420001 52.275761812, 21.119428256 52.2757188730001, 21.1192573600001 52.275699183, 21.118033106 52.2755590370001, 21.1169394460001 52.275433579, 21.116892546 52.275428413, 21.1167327920001 52.275409966, 21.1166681560001 52.275401941, 21.116662294 52.2754014080001, 21.116600589 52.275393739, 21.1165948720001 52.275392846, 21.1164573930001 52.275375995, 21.116084088 52.2753295370001, 21.112758086 52.274916003, 21.112551475 52.27489222785824, 21.112551475 52.27666228, [...]
+8;POLYGON ((21.123403395 52.2762106330001, 21.123337877 52.2762023430001, 21.1230025200001 52.2761607210001, 21.1227828080001 52.276133357, 21.122747631 52.2761289900001, 21.12257321 52.276107241, 21.1221711640001 52.276057058, 21.1220518550001 52.2760420820001, 21.1219754910001 52.276032544, 21.1218079600001 52.2760117760001, 21.1215897160001 52.275984588, 21.1213886210001 52.27595954, 21.121171842 52.2759324400001, 21.1209581420001 52.2759057860001, 21.1207469340001 52.275879489, 21.12 [...]
+8;POLYGON ((21.1270316870001 52.27666228, 21.1266841570001 52.2766190630001, 21.1263212370001 52.2765737940001, 21.1260736720001 52.2765430520001, 21.125498368 52.2764714940001, 21.125018631 52.2764117850001, 21.1248779200001 52.2763942290001, 21.124800383 52.276384604, 21.1247501080001 52.2763783660001, 21.1244859830001 52.27634548, 21.124224789 52.2763128600001, 21.123802513 52.2762603670001, 21.123403395 52.2762106330001, 21.123403395 52.27666228, 21.1270316870001 52.27666228))
+8;POLYGON ((21.112551475 52.27666228, 21.112551475 52.2932063050001, 21.1270316870001 52.2932063050001, 21.1270316870001 52.27666228, 21.112551475 52.27666228))
+8;POLYGON ((21.1341554090001 52.2775530750001, 21.1327203910001 52.2773771010001, 21.132206045 52.277314136, 21.131946015 52.277282251, 21.131704599 52.277252591, 21.131042945 52.27717145, 21.1306221150001 52.2771179010001, 21.129813142 52.277014626, 21.129755684 52.2770073190001, 21.1289566830001 52.2769053760001, 21.128592143 52.2768587680001, 21.128217636 52.2768110910001, 21.127837561 52.276762611, 21.1278366810001 52.2767624320001, 21.1278079520001 52.2767588680001, 21.1274121970001 [...]
+8;POLYGON ((21.139891338 52.285607874, 21.1403893730001 52.28335094, 21.140518677 52.282764973, 21.14093145 52.2809047600001, 21.1409344850001 52.280891275, 21.140937664 52.2808770710001, 21.1409425750001 52.2808547760001, 21.1412656470001 52.2793665770001, 21.141445376 52.278563407, 21.141469068 52.2784571450001, 21.1403709890001 52.2783214840001, 21.1402377430001 52.2783053740001, 21.1371184270001 52.277921491, 21.1368081110001 52.277883294, 21.1364891470001 52.2778440270001, 21.136145 [...]
+8;POLYGON ((21.1381863880001 52.2932063050001, 21.138395453 52.2922801570001, 21.138616304 52.291329008, 21.138823815 52.290380032, 21.139246692 52.288471912, 21.139300312 52.2882316100001, 21.139306237 52.28820482, 21.139668693 52.2865764640001, 21.139865749 52.2857190810001, 21.1398709540001 52.2856967860001, 21.1398735560001 52.2856852790001, 21.139891338 52.285607874, 21.1270316870001 52.285607874, 21.1270316870001 52.2932063050001, 21.1381863880001 52.2932063050001))
+8;POLYGON ((21.124974626 52.3085656380001, 21.124974626 52.2932063050001, 21.112551475 52.2932063050001, 21.112551475 52.3085656380001, 21.124974626 52.3085656380001))
+8;POLYGON ((21.112551475 52.3085656380001, 21.1126176390001 52.3085791460001, 21.1127194490001 52.3085990010001, 21.113106741 52.3086743960001, 21.1131740770001 52.3086874540001, 21.113176138 52.3086905970001, 21.113279155 52.3087234830001, 21.1134554820001 52.3087541410001, 21.113870628 52.308826272, 21.1139609800001 52.308837329, 21.114185977 52.308863446, 21.1142272450001 52.30888902, 21.1142906910001 52.3089283240001, 21.1144711430001 52.308966077, 21.114564156 52.3089854900001, 21.1 [...]
+8;POLYGON ((21.115725094 52.30923655, 21.115745428 52.3092183750001, 21.1160040770001 52.3092716880001, 21.116030042 52.309275707, 21.1164287820001 52.30935099, 21.1169017760001 52.3094479480001, 21.1172305440001 52.309510985, 21.117528065 52.3095682100001, 21.1176254810001 52.309588155, 21.118133104 52.309691904, 21.1182334550001 52.309712475, 21.118527602 52.3097682630001, 21.11865377 52.309792133, 21.118728004 52.3098061690001, 21.118728004 52.3085656380001, 21.115725094 52.3085656380 [...]
+8;POLYGON ((21.118728004 52.3098061690001, 21.118970511 52.3098521210001, 21.1189913440001 52.3098563250001, 21.119315725 52.309921876, 21.1194446820001 52.3099463720001, 21.1198115990001 52.3100158340001, 21.1198743900001 52.3100277240001, 21.1200907780001 52.3100662410001, 21.120185345 52.3100618300001, 21.1201895830001 52.3100565230001, 21.120250314 52.310065809, 21.12031775 52.310059988, 21.1206769510001 52.3101488680001, 21.120962907 52.310210141, 21.121252505 52.310262241, 21.12157 [...]
+8;POLYGON ((21.1219137260001 52.310386398, 21.1220060210001 52.3104087720001, 21.1220683650001 52.3104176050001, 21.122170914 52.3104361040001, 21.122566598 52.310512358, 21.1226484640001 52.3105281810001, 21.1229279520001 52.3105814560001, 21.123015246 52.310598172, 21.123365011 52.3106653940001, 21.123443798 52.3106810400001, 21.123470648 52.3106865840001, 21.12356895 52.3107068830001, 21.123645391 52.3107226220001, 21.124051062 52.310802365, 21.124266877 52.310843032, 21.124974626 52. [...]
+8;POLYGON ((21.1367615180001 52.3022529090001, 21.1368378820001 52.3013429160001, 21.1369216860001 52.3000896780001, 21.1371167190001 52.299205521, 21.137368785 52.2980890580001, 21.1372546170001 52.297576807, 21.1372141840001 52.2973956640001, 21.137137925 52.2970534150001, 21.13755739 52.295987446, 21.1377560190001 52.295138245, 21.1378855770001 52.294564505, 21.1379039440001 52.2944844040001, 21.1380909390001 52.2936688290001, 21.1381863880001 52.2932063050001, 21.124974626 52.2932063 [...]
+8;POLYGON ((21.124974626 52.3109763800001, 21.125818451 52.310538508, 21.126062093 52.3104121530001, 21.1261171460001 52.310383603, 21.1261953330001 52.3103429860001, 21.1265552450001 52.310264858, 21.126652403 52.3102438130001, 21.1267415020001 52.3102244840001, 21.126752346 52.310222136, 21.1268240050001 52.3102065100001, 21.127255281 52.3101129350001, 21.1273546370001 52.310091437, 21.127548394 52.310059143, 21.1278397620001 52.3100106540001, 21.128271243 52.309938915, 21.128538279000 [...]
+8;POLYGON ((21.136303533 52.3056963160001, 21.1363697940001 52.304738162, 21.13622423 52.303839032, 21.136531963 52.3029308390001, 21.1367615180001 52.3022529090001, 21.13080137 52.3022529090001, 21.13080137 52.3056963160001, 21.136303533 52.3056963160001))
+8;POLYGON ((21.13080137 52.3098299070001, 21.131174623 52.3098048670001, 21.131236782 52.3098006640001, 21.131452838 52.3097237600001, 21.1316000480001 52.3096713780001, 21.1318691270001 52.30957554, 21.132106273 52.3094910610001, 21.1324431670001 52.3093711490001, 21.1325104000001 52.3093471670001, 21.132855653 52.309228053, 21.133087822 52.3091478920001, 21.1333829760001 52.309045999, 21.1336076740001 52.308968452, 21.133845846 52.3088862160001, 21.134027917 52.3088233660001, 21.134077 [...]
+9;POLYGON ((21.101965615 52.2808580120001, 21.10187144 52.2810704710001, 21.101732215 52.2813843490001, 21.101663257 52.2815396240001, 21.101595903 52.2816913940001, 21.101476065 52.2819618440001, 21.1014071060001 52.2821170300001, 21.101387862 52.282160547, 21.1013190480001 52.282315732, 21.1011774830001 52.2826348240001, 21.1008815160001 52.283302049, 21.1008019080001 52.2834811500001, 21.1007981170001 52.2834895120001, 21.1007508870001 52.28360001, 21.1006999800001 52.2837046700001, 2 [...]
+9;POLYGON ((21.105009379 52.2739940060001, 21.104849067 52.2743557210001, 21.104604657 52.27490679, 21.104494038 52.2751564750001, 21.1044055690001 52.2753557190001, 21.1041884050001 52.2758455570001, 21.1041803910001 52.2758648880001, 21.1040123390001 52.2762434150001, 21.1037826310001 52.2767617540001, 21.103633959 52.277096944, 21.1030614040001 52.27838753, 21.1028372110001 52.278892291, 21.10274975 52.279090185, 21.102595814 52.2794370610001, 21.1025759890001 52.279481837, 21.1024778 [...]
+9;POLYGON ((21.091324921 52.2920242180001, 21.089866253 52.2934904970001, 21.08957164 52.293786593, 21.0879453260001 52.2954087300001, 21.0879358180001 52.295418623, 21.0878929520001 52.2954608970001, 21.0878686670001 52.295485091, 21.0878578410001 52.295495885, 21.0878350190001 52.2955189100001, 21.087804443 52.2955495800001, 21.0877968350001 52.2955566860001, 21.0875740880001 52.2955147000001, 21.0873820150001 52.2958637410001, 21.0862661800001 52.297891625, 21.086246021 52.29792812900 [...]
+9;POLYGON ((21.098032592 52.3057045290001, 21.0981996730001 52.3057414190001, 21.098572269 52.3058238840001, 21.0986089420001 52.3058320320001, 21.09870399 52.3058494790001, 21.0987541550001 52.3058586940001, 21.0990921050001 52.3059207850001, 21.099179382 52.3059378780001, 21.099234242 52.3059486170001, 21.099532153 52.306004988, 21.0997042130001 52.306038277, 21.0997601 52.3060491040001, 21.099902677 52.3060764860001, 21.0999701530001 52.3060901800001, 21.100248267 52.30614396, 21.1007 [...]
+9;POLYGON ((21.1381863880001 52.2932063050001, 21.138395453 52.2922801570001, 21.138616304 52.291329008, 21.138823815 52.290380032, 21.139246692 52.288471912, 21.139300312 52.2882316100001, 21.139306237 52.28820482, 21.139668693 52.2865764640001, 21.139865749 52.2857190810001, 21.1398709540001 52.2856967860001, 21.1398735560001 52.2856852790001, 21.139891338 52.285607874, 21.1403893730001 52.28335094, 21.140518677 52.282764973, 21.14093145 52.2809047600001, 21.1409344850001 52.280891275, [...]
+9;POLYGON ((21.112551475 52.3085656380001, 21.1126176390001 52.3085791460001, 21.1127194490001 52.3085990010001, 21.113106741 52.3086743960001, 21.1131740770001 52.3086874540001, 21.113176138 52.3086905970001, 21.113279155 52.3087234830001, 21.1134554820001 52.3087541410001, 21.113870628 52.308826272, 21.1139609800001 52.308837329, 21.114185977 52.308863446, 21.1142272450001 52.30888902, 21.1142906910001 52.3089283240001, 21.1144711430001 52.308966077, 21.114564156 52.3089854900001, 21.1 [...]
+9;POLYGON ((21.124974626 52.3109763800001, 21.125818451 52.310538508, 21.126062093 52.3104121530001, 21.1261171460001 52.310383603, 21.1261953330001 52.3103429860001, 21.1265552450001 52.310264858, 21.126652403 52.3102438130001, 21.1267415020001 52.3102244840001, 21.126752346 52.310222136, 21.1268240050001 52.3102065100001, 21.127255281 52.3101129350001, 21.1273546370001 52.310091437, 21.127548394 52.310059143, 21.1278397620001 52.3100106540001, 21.128271243 52.309938915, 21.128538279000 [...]
\ No newline at end of file
diff --git a/core/src/test/resources/subdivide/subdivide_input_geometries.txt b/core/src/test/resources/subdivide/subdivide_input_geometries.txt
new file mode 100644
index 0000000..07b56b7
--- /dev/null
+++ b/core/src/test/resources/subdivide/subdivide_input_geometries.txt
@@ -0,0 +1,9 @@
+1;point;POINT (21 52);5
+2;linestring with three points;LINESTRING (0 0, 85 85, 100 100);5
+3;linestring with two points;LINESTRING (0 0, 85 85);5
+4;linestring with seven points;LINESTRING (0 0, 85 85, 100 100, 120 120, 21 21, 10 10, 5 5);5
+5;linestring with 5 points with the same y coordinate;LINESTRING (0 0, 1 0, 2 0, 3 0, 4 0, 5 0, 6 0);5
+6;polygon;POLYGON ((132 10,119 23,85 35,68 29,66 28,49 42,32 56,22 64,32 110,40 119,36 150, 57 158,75 171,92 182,114 184,132 186,146 178,176 184,179 162,184 141,190 122, 190 100,185 79,186 56,186 52,178 34,168 18,147 13,132 10));10
+7;polygon with holes;POLYGON ((35 10, 45 45, 15 40, 10 20, 35 10), (20 30, 35 35, 30 20, 20 30));5
+8;huge multipolygon with 30 vertices;MULTIPOLYGON(((21.105009379 52.2739940060001,21.104849067 52.2743557210001,21.104604657 52.27490679,21.104494038 52.2751564750001,21.1044055690001 52.2753557190001,21.1041884050001 52.2758455570001,21.1041803910001 52.2758648880001,21.1040123390001 52.2762434150001,21.1037826310001 52.2767617540001,21.103633959 52.277096944,21.1030614040001 52.27838753,21.1028372110001 52.278892291,21.10274975 52.279090185,21.102595814 52.2794370610001,21.102575989000 [...]
+9;huge multipolygon with 100 vertices as minimum;MULTIPOLYGON(((21.105009379 52.2739940060001,21.104849067 52.2743557210001,21.104604657 52.27490679,21.104494038 52.2751564750001,21.1044055690001 52.2753557190001,21.1041884050001 52.2758455570001,21.1041803910001 52.2758648880001,21.1040123390001 52.2762434150001,21.1037826310001 52.2767617540001,21.103633959 52.277096944,21.1030614040001 52.27838753,21.1028372110001 52.278892291,21.10274975 52.279090185,21.102595814 52.2794370610001,21. [...]
\ No newline at end of file
diff --git a/docs/api/sql/Function.md b/docs/api/sql/Function.md
index 8d6f3f2..ccaa3d0 100644
--- a/docs/api/sql/Function.md
+++ b/docs/api/sql/Function.md
@@ -612,3 +612,118 @@ Spark SQL example:
```SQL
SELECT ST_MinimumBoundingCircle(ST_GeomFromText('POLYGON((1 1,0 0, -1 1, 1 1))'))
```
+
+## ST_SubDivide
+
+Introduction: Returns list of geometries divided based of given maximum number of vertices.
+
+Format: `ST_SubDivide(geom: geometry, maxVertices: int)`
+
+Since: `v1.0.2`
+
+Spark SQL example:
+```SQL
+SELECT ST_SubDivide(ST_GeomFromText("POLYGON((35 10, 45 45, 15 40, 10 20, 35 10), (20 30, 35 35, 30 20, 20 30))"), 5)
+
+```
+
+Output:
+```
+[
+ POLYGON((37.857142857142854 20, 35 10, 10 20, 37.857142857142854 20)),
+ POLYGON((15 20, 10 20, 15 40, 15 20)),
+ POLYGON((20 20, 15 20, 15 30, 20 30, 20 20)),
+ POLYGON((26.428571428571427 20, 20 20, 20 30, 26.4285714 23.5714285, 26.4285714 20)),
+ POLYGON((15 30, 15 40, 20 40, 20 30, 15 30)),
+ POLYGON((20 40, 26.4285714 40, 26.4285714 32.1428571, 20 30, 20 40)),
+ POLYGON((37.8571428 20, 30 20, 34.0476190 32.1428571, 37.8571428 32.1428571, 37.8571428 20)),
+ POLYGON((34.0476190 34.6825396, 26.4285714 32.1428571, 26.4285714 40, 34.0476190 40, 34.0476190 34.6825396)),
+ POLYGON((34.0476190 32.1428571, 35 35, 37.8571428 35, 37.8571428 32.1428571, 34.0476190 32.1428571)),
+ POLYGON((35 35, 34.0476190 34.6825396, 34.0476190 35, 35 35)),
+ POLYGON((34.0476190 35, 34.0476190 40, 37.8571428 40, 37.8571428 35, 34.0476190 35)),
+ POLYGON((30 20, 26.4285714 20, 26.4285714 23.5714285, 30 20)),
+ POLYGON((15 40, 37.8571428 43.8095238, 37.8571428 40, 15 40)),
+ POLYGON((45 45, 37.8571428 20, 37.8571428 43.8095238, 45 45))
+]
+```
+
+Spark SQL example:
+
+```SQL
+SELECT ST_SubDivide(ST_GeomFromText("LINESTRING(0 0, 85 85, 100 100, 120 120, 21 21, 10 10, 5 5)"), 5)
+```
+
+Output:
+```
+[
+ LINESTRING(0 0, 5 5)
+ LINESTRING(5 5, 10 10)
+ LINESTRING(10 10, 21 21)
+ LINESTRING(21 21, 60 60)
+ LINESTRING(60 60, 85 85)
+ LINESTRING(85 85, 100 100)
+ LINESTRING(100 100, 120 120)
+]
+```
+
+## ST_SubDivideExplode
+
+Introduction: It works the same as ST_SubDivide but returns new rows with geometries instead of list.
+
+Format: `ST_SubDivideExplode(geom: geometry, maxVertices: int)`
+
+Since: `v1.0.2`
+
+Example:
+
+Query:
+```SQL
+SELECT ST_SubDivideExplode(ST_GeomFromText("LINESTRING(0 0, 85 85, 100 100, 120 120, 21 21, 10 10, 5 5)"), 5)
+```
+
+Result:
+
+```
++-----------------------------+
+|geom |
++-----------------------------+
+|LINESTRING(0 0, 5 5) |
+|LINESTRING(5 5, 10 10) |
+|LINESTRING(10 10, 21 21) |
+|LINESTRING(21 21, 60 60) |
+|LINESTRING(60 60, 85 85) |
+|LINESTRING(85 85, 100 100) |
+|LINESTRING(100 100, 120 120) |
++-----------------------------+
+```
+
+Using Lateral View
+
+Table:
+```
++-------------------------------------------------------------+
+|geometry |
++-------------------------------------------------------------+
+|LINESTRING(0 0, 85 85, 100 100, 120 120, 21 21, 10 10, 5 5) |
++-------------------------------------------------------------+
+```
+
+Query
+```SQL
+select geom from geometries LATERAL VIEW ST_SubdivideExplode(geometry, 5) AS geom
+```
+
+Result:
+```
++-----------------------------+
+|geom |
++-----------------------------+
+|LINESTRING(0 0, 5 5) |
+|LINESTRING(5 5, 10 10) |
+|LINESTRING(10 10, 21 21) |
+|LINESTRING(21 21, 60 60) |
+|LINESTRING(60 60, 85 85) |
+|LINESTRING(85 85, 100 100) |
+|LINESTRING(100 100, 120 120) |
++-----------------------------+
+```
\ No newline at end of file
diff --git a/python/tests/sql/test_function.py b/python/tests/sql/test_function.py
index 77a7c0b..94d8038 100644
--- a/python/tests/sql/test_function.py
+++ b/python/tests/sql/test_function.py
@@ -19,7 +19,7 @@ import math
from typing import List
from pyspark.sql import DataFrame
-from pyspark.sql.functions import explode
+from pyspark.sql.functions import explode, expr
from pyspark.sql.functions import col
from pyspark.sql.types import StructType, StructField, IntegerType
from shapely import wkt
@@ -587,6 +587,61 @@ class TestPredicateJoin(TestBase):
for actual, expected in result_and_expected:
assert(actual == expected)
+ def test_st_subdivide(self):
+ # Given
+ geometry_df = self.__wkt_list_to_data_frame(
+ [
+ "POINT(21 52)",
+ "POLYGON ((35 10, 45 45, 15 40, 10 20, 35 10), (20 30, 35 35, 30 20, 20 30))",
+ "LINESTRING (0 0, 1 1, 2 2)"
+ ]
+ )
+ geometry_df.createOrReplaceTempView("geometry")
+
+ # When
+ subdivided = geometry_df.select(expr("st_SubDivide(geom, 5)"))
+
+ # Then
+ assert subdivided.count() == 3
+
+ assert sum([geometries[0].__len__() for geometries in subdivided.collect()]) == 16
+
+ def test_st_subdivide_explode(self):
+ # Given
+ geometry_df = self.__wkt_list_to_data_frame(
+ [
+ "POINT(21 52)",
+ "POLYGON ((35 10, 45 45, 15 40, 10 20, 35 10), (20 30, 35 35, 30 20, 20 30))",
+ "LINESTRING (0 0, 1 1, 2 2)"
+ ]
+ )
+ geometry_df.createOrReplaceTempView("geometry")
+
+ # When
+ subdivided = geometry_df.select(expr("st_SubDivideExplode(geom, 5)"))
+
+ # Then
+ assert subdivided.count() == 16
+
+ def test_st_subdivide_explode_lateral(self):
+ # Given
+ geometry_df = self.__wkt_list_to_data_frame(
+ [
+ "POINT(21 52)",
+ "POLYGON ((35 10, 45 45, 15 40, 10 20, 35 10), (20 30, 35 35, 30 20, 20 30))",
+ "LINESTRING (0 0, 1 1, 2 2)"
+ ]
+ )
+
+ geometry_df.selectExpr("geom as geometry").createOrReplaceTempView("geometries")
+
+ # When
+ lateral_view_result = self.spark. \
+ sql("""select geom from geometries LATERAL VIEW ST_SubdivideExplode(geometry, 5) AS geom""")
+
+ # Then
+ assert lateral_view_result.count() == 16
+
def calculate_st_is_ring(self, wkt):
geometry_collected = self.__wkt_list_to_data_frame([wkt]). \
selectExpr("ST_IsRing(geom) as is_ring") \
diff --git a/sql/src/main/scala/org/apache/sedona/sql/UDF/Catalog.scala b/sql/src/main/scala/org/apache/sedona/sql/UDF/Catalog.scala
index 31e7112..c8b6fdb 100644
--- a/sql/src/main/scala/org/apache/sedona/sql/UDF/Catalog.scala
+++ b/sql/src/main/scala/org/apache/sedona/sql/UDF/Catalog.scala
@@ -81,7 +81,9 @@ object Catalog {
ST_IsRing,
ST_FlipCoordinates,
ST_LineSubstring,
- ST_LineInterpolatePoint
+ ST_LineInterpolatePoint,
+ ST_SubDivideExplode,
+ ST_SubDivide
)
val aggregateExpressions: Seq[Aggregator[Geometry, Geometry, Geometry]] = Seq(
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
index 7ba88a2..bbe8205 100644
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
@@ -23,11 +23,12 @@ import org.apache.sedona.core.utils.GeomUtils
import org.apache.sedona.sql.utils.GeometrySerializer
import org.apache.spark.internal.Logging
import org.apache.spark.sql.catalyst.InternalRow
-import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
+import org.apache.spark.sql.catalyst.expressions.codegen.{CodegenContext, CodegenFallback, ExprCode}
import org.apache.spark.sql.catalyst.expressions.{Expression, Generator}
import org.apache.spark.sql.catalyst.util.{ArrayData, GenericArrayData}
import org.apache.spark.sql.sedona_sql.UDT.GeometryUDT
import org.apache.spark.sql.sedona_sql.expressions.implicits._
+import org.apache.spark.sql.sedona_sql.expressions.subdivide.GeometrySubDivider
import org.apache.spark.sql.types.{ArrayType, _}
import org.apache.spark.unsafe.types.UTF8String
import org.geotools.geometry.jts.JTS
@@ -1122,4 +1123,48 @@ case class ST_FlipCoordinates(inputExpressions: Seq[Expression])
override def dataType: DataType = GeometryUDT
override def children: Seq[Expression] = inputExpressions
+}
+
+
+case class ST_SubDivide(inputExpressions: Seq[Expression])
+ extends Expression with CodegenFallback {
+ override def nullable: Boolean = true
+
+ override def eval(input: InternalRow): Any = {
+ inputExpressions.validateLength(2)
+ val geometryRaw = inputExpressions.head
+ val maxVerticesRaw = inputExpressions(1)
+ geometryRaw.toGeometry(input) match {
+ case geom: Geometry => ArrayData.toArrayData(
+ GeometrySubDivider.subDivide(geom, maxVerticesRaw.toInt(input)).map(_.toGenericArrayData)
+ )
+ case null => null
+ }
+
+ }
+
+ override def dataType: DataType = ArrayType(GeometryUDT)
+
+ override def children: Seq[Expression] = inputExpressions
+}
+
+case class ST_SubDivideExplode(children: Seq[Expression]) extends Generator {
+ override def eval(input: InternalRow): TraversableOnce[InternalRow] = {
+ children.validateLength(2)
+ val geometryRaw = children.head
+ val maxVerticesRaw = children(1)
+ geometryRaw.toGeometry(input) match {
+ case geom: Geometry => ArrayData.toArrayData(
+ GeometrySubDivider.subDivide(geom, maxVerticesRaw.toInt(input)).map(_.toGenericArrayData)
+ )
+ GeometrySubDivider.subDivide(geom, maxVerticesRaw.toInt(input)).map(_.toGenericArrayData).map(InternalRow(_))
+ case _ => new Array[InternalRow](0)
+ }
+ }
+ override def elementSchema: StructType = {
+ new StructType()
+ .add("geom", GeometryUDT, true)
+ }
+
+ override protected def doGenCode(ctx: CodegenContext, ev: ExprCode): ExprCode = ev
}
\ No newline at end of file
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/implicits.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/implicits.scala
index f13b956..e31efe3 100644
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/implicits.scala
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/implicits.scala
@@ -72,6 +72,7 @@ object implicits {
def getPoints: Array[Point] =
geom.getCoordinates.map(coordinate => geometryFactory.createPoint(coordinate))
- }
+ def isNonEmpty: Boolean = geom != null && !geom.isEmpty
+ }
}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CircleSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CircleSimplifier.scala
new file mode 100644
index 0000000..27f4f2e
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CircleSimplifier.scala
@@ -0,0 +1,27 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.simplify
+
+import org.apache.sedona.core.geometryObjects.Circle
+import org.locationtech.jts.geom.Geometry
+
+object CircleSimplifier {
+ def simplify(geom: Circle, preserveCollapsed: Boolean, epsilon: Double): Geometry = geom
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSimplifier.scala
new file mode 100644
index 0000000..0b04223
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSimplifier.scala
@@ -0,0 +1,69 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.simplify
+
+import org.apache.spark.sql.sedona_sql.expressions.subdivide.{Stack, ZeroToleranceGeometrySimplifier}
+import org.locationtech.jts.geom.Coordinate
+
+import scala.collection.mutable.ArrayBuffer
+
+object CoordinatesSimplifier {
+ def simplifyInPlace(geom: Array[Coordinate], tolerance: Double, minPointsExternal: Int): Array[Coordinate] = {
+ if (geom.length < 3 || geom.length <= minPointsExternal) {
+ geom
+ }
+ else if (tolerance == 0 && minPointsExternal <= 2) {
+ ZeroToleranceGeometrySimplifier.simplifyInPlaceTolerance0(geom)
+ }
+ else {
+ val kept_points = ArrayBuffer.fill(geom.length)(false)
+ kept_points(0) = true
+ var itLast = geom.length - 1
+ kept_points(itLast) = true
+ var keptn = 2
+ val iteratorStack = new Stack[Int]()
+ iteratorStack.push(0)
+ var itFirst = 0
+
+ val toleranceSquared = tolerance * tolerance
+ var itTool = if (keptn >= minPointsExternal) toleranceSquared else -1.0
+
+ while (!iteratorStack.isEmpty){
+ val splitInPlaceRes = CoordinatesSplitter.splitInPlace(geom, itFirst = itFirst, itLast, itTool)
+ if (splitInPlaceRes.split == itFirst){
+ itFirst = itLast
+ itLast = iteratorStack.pull()
+ }
+ else {
+ kept_points(splitInPlaceRes.split) = true
+ keptn = keptn + 1
+
+ iteratorStack.push(itLast)
+ itLast = splitInPlaceRes.split
+ itTool = if (keptn >= minPointsExternal) toleranceSquared else -1.0
+ }
+ }
+
+ geom.zipWithIndex.filter{
+ case (element, index) => kept_points(index)
+ }.map(_._1)
+ }
+ }
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSplitter.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSplitter.scala
new file mode 100644
index 0000000..f993ff3
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSplitter.scala
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.simplify
+
+import org.locationtech.jts.geom.Coordinate
+
+object CoordinatesSplitter extends SimplifyingParameters{
+ def splitInPlace(geom: Array[Coordinate],
+ itFirst: Int,
+ itLast: Int,
+ maxDistanceSquared: Double): SplitInPlace = {
+ var split = itFirst
+ var maxDistance = maxDistanceSquared
+ if ((itFirst - itLast) < 2) SplitInPlace(geom, itFirst)
+ val pointA = geom(itFirst)
+ val pointB = geom(itLast)
+ if (calcualteSquaredDistance(pointA, pointB) < DBL_EPSILON){
+ for (itk <- Range(itFirst + 1, itLast)){
+ val pk = geom(itk)
+ val squaredDistance = calcualteSquaredDistance(pk, pointA)
+ if (squaredDistance > maxDistance){
+ split = itk
+ maxDistance = squaredDistance
+ }
+ }
+ }
+
+ val ba_x = pointB.x - pointA.x
+ val ba_y = pointB.y - pointA.y
+ val ab_length_sqr = (ba_x * ba_x + ba_y * ba_y)
+ maxDistance *= ab_length_sqr
+ for (itk <- Range(itFirst + 1, itLast)){
+ val c = geom(itk)
+ var distance_sqr = 0.0
+ val ca_x = c.x - pointA.x
+ val ca_y = c.y - pointA.y
+ val dot_ac_ab = (ca_x * ba_x + ca_y * ba_y)
+ if (dot_ac_ab <= 0.0) {
+ distance_sqr = calcualteSquaredDistance(c, pointA) * ab_length_sqr;
+ }
+ else if (dot_ac_ab >= ab_length_sqr) {
+ distance_sqr = calcualteSquaredDistance(c, pointB) * ab_length_sqr;
+ }
+ else {
+ val s_numerator = ca_x * ba_y - ca_y * ba_x
+ distance_sqr = s_numerator * s_numerator
+ }
+
+ if (distance_sqr > maxDistance)
+ {
+ split = itk
+ maxDistance = distance_sqr
+ }
+ }
+
+ SplitInPlace(geom, split)
+ }
+
+ private def calcualteSquaredDistance(geomA: Coordinate, geomB: Coordinate): Double = {
+ val distance = geomA.distance(geomB)
+ distance * distance
+ }
+
+ case class SplitInPlace(geom: Array[Coordinate], split: Int)
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometryCollectionSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometryCollectionSimplifier.scala
new file mode 100644
index 0000000..8c7b645
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometryCollectionSimplifier.scala
@@ -0,0 +1,52 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.simplify
+
+import org.apache.sedona.core.geometryObjects.Circle
+import org.locationtech.jts.geom.{Geometry, GeometryCollection, GeometryFactory, LineString, Point, Polygon}
+
+object GeometryCollectionSimplifier {
+ private val geometryFactory = new GeometryFactory()
+
+ def simplify(geom: GeometryCollection, preserveCollapsed: Boolean, epsilon: Double): Geometry = {
+
+ val numberOfGeometries = geom.getNumGeometries
+ val geometries = (0 until numberOfGeometries).map(
+ geom.getGeometryN
+ ).map {
+ case circle: Circle => CircleSimplifier.simplify(circle, preserveCollapsed, epsilon)
+ case string: LineString => LinestringSimplifier.simplify(string, epsilon, preserveCollapsed)
+ case point: Point => point
+ case polygon: Polygon => PolygonSimplifier.simplify(polygon, preserveCollapsed, epsilon)
+ case _ => null
+ case collection: GeometryCollection => simplify(collection, preserveCollapsed, epsilon)
+ }.filter(_!=null).toArray
+
+ val distinctGeometries = geometries.map(_.getGeometryType).distinct
+ if (distinctGeometries.length ==1){
+ distinctGeometries.head match {
+ case "LineString" => geometryFactory.createMultiLineString(geometries.map(x => x.asInstanceOf[LineString]))
+ case "Polygon" => geometryFactory.createMultiPolygon(geometries.map(x => x.asInstanceOf[Polygon]))
+ case "Point" => geometryFactory.createMultiPoint(geometries.map(x => x.asInstanceOf[Point]))
+ }
+ }
+ else geometryFactory.createGeometryCollection(geometries)
+ }
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometrySimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometrySimplifier.scala
new file mode 100644
index 0000000..36ffe15
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometrySimplifier.scala
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.simplify
+
+import org.apache.sedona.core.geometryObjects.Circle
+import org.locationtech.jts.geom._
+
+object GeometrySimplifier {
+
+ def simplify(geom: Geometry, preserveCollapsed: Boolean, epsilon: Double): Geometry = geom match {
+ case circle: Circle => simplifyCircle(circle, preserveCollapsed, epsilon)
+ case collection: GeometryCollection => simplifyGeometryCollection(collection, preserveCollapsed, epsilon)
+ case string: LineString => simplifyLineString(string, epsilon, preserveCollapsed)
+ case point: Point => point
+ case polygon: Polygon => simplifyPolygon(polygon, preserveCollapsed, epsilon)
+ case geom: Geometry => geom
+ }
+
+ private def simplifyLineString(geom: LineString, epsilon: Double, preserveCollapsed: Boolean): Geometry =
+ LinestringSimplifier.simplify(geom, epsilon, preserveCollapsed)
+
+ private def simplifyPolygon(geom: Polygon, preserveCollapsed: Boolean, epsilon: Double): Geometry =
+ PolygonSimplifier.simplify(geom, preserveCollapsed, epsilon)
+
+ private def simplifyCircle(geom: Circle, preserveCollapsed: Boolean, epsilon: Double): Geometry =
+ CircleSimplifier.simplify(geom, preserveCollapsed, epsilon)
+
+ private def simplifyGeometryCollection(geom: GeometryCollection,
+ preserveCollapsed: Boolean,
+ epsilon: Double): Geometry =
+ GeometryCollectionSimplifier.simplify(geom, preserveCollapsed, epsilon)
+
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/LinestringSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/LinestringSimplifier.scala
new file mode 100644
index 0000000..e24b2a1
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/LinestringSimplifier.scala
@@ -0,0 +1,42 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.simplify
+
+import org.locationtech.jts.geom.{Geometry, GeometryFactory, LineString}
+
+object LinestringSimplifier {
+ private val geometryFactory = new GeometryFactory()
+
+ def simplify(geom: LineString, epsilon: Double, preserveCollapsed: Boolean): Geometry = {
+ val simplified = CoordinatesSimplifier.simplifyInPlace(geom.getCoordinates, epsilon, 2)
+
+ if (simplified.length == 1){
+ if (preserveCollapsed) geometryFactory.createLineString(simplified ++ simplified)
+ else geometryFactory.createLineString(simplified)
+ }
+ else if (simplified.length == 2 && !preserveCollapsed){
+ if (simplified(0) == simplified(1)) geometryFactory.createLineString(simplified)
+ else geometryFactory.createLineString(simplified)
+ }
+ else {
+ geometryFactory.createLineString(simplified)
+ }
+ }
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/PolygonSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/PolygonSimplifier.scala
new file mode 100644
index 0000000..e85604b
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/PolygonSimplifier.scala
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.simplify
+
+import org.apache.spark.sql.sedona_sql.expressions.simplify.CoordinatesSimplifier.simplifyInPlace
+import org.locationtech.jts.geom.{Geometry, GeometryFactory, Polygon}
+
+object PolygonSimplifier {
+ private val geometryFactory = new GeometryFactory()
+
+ def simplify(geom: Polygon, preserveCollapsed: Boolean, epsilon: Double): Geometry = {
+ val exteriorRing = geom.getExteriorRing
+ val minPointsExternal = if (preserveCollapsed) 4 else 0
+
+ val simplifiedExterior =
+ geometryFactory.createLinearRing(simplifyInPlace(exteriorRing.getCoordinates, epsilon, minPointsExternal))
+
+ if (simplifiedExterior.getNumPoints < 4) {
+ simplifiedExterior
+ }
+ else {
+ val exteriorRings = (0 until geom.getNumInteriorRing).map(index => geom.getInteriorRingN(index))
+ .map(geom => simplifyInPlace(geom.getCoordinates, epsilon, minPointsExternal))
+ .filter(_.length >= 4)
+ .map(geometryFactory.createLinearRing)
+ .filter(_.getNumPoints >= 4)
+
+
+ geometryFactory.createPolygon(simplifiedExterior, exteriorRings.toArray)
+
+ }
+ }
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/SimplifyingParameters.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/SimplifyingParameters.scala
new file mode 100644
index 0000000..642a337
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/SimplifyingParameters.scala
@@ -0,0 +1,24 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.simplify
+
+trait SimplifyingParameters {
+ val DBL_EPSILON = 2.2204460492503131e-16
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDivider.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDivider.scala
new file mode 100644
index 0000000..5a995b5
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDivider.scala
@@ -0,0 +1,148 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.subdivide
+
+import org.apache.spark.sql.sedona_sql.expressions.simplify.GeometrySimplifier
+import org.geotools.geometry.jts.JTS
+import org.locationtech.jts.geom.{Envelope, Geometry, GeometryCollection, GeometryFactory, Point}
+import org.apache.spark.sql.sedona_sql.expressions.implicits.GeometryEnhancer
+
+object GeometrySubDivider {
+
+ val geometryFactory = new GeometryFactory()
+
+ import GeometrySubDividerConfiguration._
+
+ def equalValue(value: Double, pivot: Double): Boolean = {
+ math.abs(value - pivot) > FP_TOLERANCE
+ }
+
+ def subDivideRecursive(
+ geom: Geometry,
+ dimension: Int,
+ maxVertices: Int,
+ depth: Int,
+ geometries: Seq[Geometry]
+ ): Seq[Geometry] = {
+
+ val numberOfVertices = geom.getNumPoints
+ val geometryBbox = geom.getEnvelope.getEnvelopeInternal
+ val width = geometryBbox.getWidth
+ val height = geometryBbox.getHeight
+ val geometryBboxAligned = if (width == 0) new Envelope(
+ geometryBbox.getMinX - FP_TOLERANCE,
+ geometryBbox.getMaxX + FP_TOLERANCE,
+ geometryBbox.getMinY,
+ geometryBbox.getMaxY
+ ) else if (height == 0) new Envelope(
+ geometryBbox.getMinX,
+ geometryBbox.getMaxX,
+ geometryBbox.getMinY - FP_TOLERANCE,
+ geometryBbox.getMaxY + FP_TOLERANCE
+ ) else geometryBbox
+ if (
+ geom == null || geom.getDimension < dimension || numberOfVertices == 0 || geometryBboxAligned == null
+ ) geometries
+ else if (width == 0.0 && height == 0.0) geom match {
+ case point: Point => if (dimension == 0) geom +: geometries else geometries
+ case polygon: Geometry => geometries
+ }
+ else if (geom.isInstanceOf[GeometryCollection] && !geom.getGeometryType.contains("Point")) {
+ val collection = geom.asInstanceOf[GeometryCollection]
+ val numberOfGeometries = collection.getNumGeometries
+ (0 until numberOfGeometries).map(
+ i => subDivideRecursive(collection.getGeometryN(i), dimension, maxVertices, depth, geometries)
+ ).reduce(_ ++ _)
+ }
+ else {
+ if (numberOfVertices <= maxVertices || depth > maxDepth) {
+ geom +: geometries
+ }
+ else {
+ val split_ordinate = if (width > height) 0 else 1
+
+ val center = if (split_ordinate == 0) (geometryBboxAligned.getMinX + geometryBboxAligned.getMaxX) / 2
+ else (geometryBboxAligned.getMinY + geometryBboxAligned.getMaxY) / 2
+
+ val pivot = PivotFinder.findPivot(geom, split_ordinate, center, numberOfVertices)
+
+ val subBoxes = getSubBoxes(split_ordinate, SubdivideExtent.fromClip(geometryBboxAligned), pivot, center)
+
+ val intersectedSimplified = getIntersectionGeometries(subBoxes.subBox, geom)
+ val intersectedIter2Simplfied = getIntersectionGeometries(subBoxes.subBox2, geom)
+
+ if (intersectedSimplified.isNonEmpty && intersectedIter2Simplfied.isNonEmpty) {
+ subDivideRecursive(intersectedSimplified, dimension, maxVertices, depth + 1, geometries) ++
+ subDivideRecursive(intersectedIter2Simplfied, dimension, maxVertices, depth + 1, geometries)
+ } else if (intersectedSimplified.isNonEmpty) {
+ subDivideRecursive(intersectedSimplified, dimension, maxVertices, depth + 1, geometries)
+ } else if (intersectedIter2Simplfied.isNonEmpty) {
+ subDivideRecursive(intersectedIter2Simplfied, dimension, maxVertices, depth + 1, geometries)
+ }
+ else {
+ geometries
+ }
+
+ }
+ }
+ }
+
+ private def getSubBoxes(split_ordinate: Int, subbox: SubdivideExtent, pivot: Double, center: Double): SubBoxes = {
+ if (split_ordinate == 0) {
+ if (equalValue(subbox.xmax, pivot) && equalValue(subbox.xmin, pivot))
+ SubBoxes(subbox.copy(xmax = pivot), subbox.copy(xmin = pivot))
+ else
+ SubBoxes(subbox.copy(xmax = center), subbox.copy(xmin = center))
+ }
+ else {
+ if (equalValue(subbox.ymax, pivot) && equalValue(subbox.ymin, pivot))
+ SubBoxes(subbox.copy(ymax = pivot), subbox.copy(ymin = pivot))
+ else
+ SubBoxes(subbox.copy(ymax = center), subbox.copy(ymin = center))
+ }
+ }
+
+ private def getIntersectionGeometries(extent: SubdivideExtent, geom: Geometry): Geometry = {
+ val subBox = new Envelope(extent.xmin, extent.xmax, extent.ymin, extent.ymax)
+ val intersected = geom.intersection(JTS.toGeometry(subBox))
+ GeometrySimplifier.simplify(intersected, true, 0.0)
+ }
+
+ def subDividePrecise(geom: Geometry, maxVertices: Int): Seq[Geometry] = {
+ if (geom == null) {
+ Seq()
+ }
+ else {
+ if (maxVertices < minMaxVertices) {
+ Seq()
+ }
+ else {
+ subDivideRecursive(geom, geom.getDimension, maxVertices, startDepth, Seq())
+ }
+ }
+
+ }
+
+ def subDivide(geom: Geometry, maxVertices: Int): Seq[Geometry] = {
+ subDividePrecise(geom, maxVertices)
+ }
+
+}
+
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDividerConfiguration.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDividerConfiguration.scala
new file mode 100644
index 0000000..90e9666
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDividerConfiguration.scala
@@ -0,0 +1,28 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.subdivide
+
+object GeometrySubDividerConfiguration {
+ val maxDepth: Int = 50
+ val minMaxVertices = 5
+ val startDepth = 0
+ val DBL_MAX: Double = Double.MaxValue
+ val FP_TOLERANCE: Double = 1e-12
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/PivotFinder.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/PivotFinder.scala
new file mode 100644
index 0000000..2489d94
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/PivotFinder.scala
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.subdivide
+
+import org.apache.spark.sql.sedona_sql.expressions.subdivide.GeometrySubDivider.geometryFactory
+import org.apache.spark.sql.sedona_sql.expressions.subdivide.GeometrySubDividerConfiguration.DBL_MAX
+import org.locationtech.jts.geom.{Geometry, Polygon}
+
+object PivotFinder {
+ def findPivot(geom: Geometry, split_ordinate: Int, center: Double, numberOfVertices: Int): Double = {
+ var pivot = DBL_MAX;
+ if (geom.isInstanceOf[Polygon]) {
+ var pivot_eps = DBL_MAX
+ var ptEps = DBL_MAX
+ val lwPoly = geom.copy().asInstanceOf[Polygon]
+ val ringToTrim = if (numberOfVertices >= 2 * lwPoly.getExteriorRing.getNumPoints)
+ (geometryFactory.createPolygon(lwPoly.getExteriorRing).getArea +: (0 until lwPoly.getNumInteriorRing)
+ .map(lwPoly.getInteriorRingN)
+ .map(x => geometryFactory.createPolygon(x).getArea)).zipWithIndex.maxBy(_._1)._2 else 0
+
+ val pointArray = if (ringToTrim == 0) lwPoly.getExteriorRing else lwPoly.getInteriorRingN(ringToTrim - 1)
+ for (i <- 0 until pointArray.getNumPoints) {
+ val pt = if (split_ordinate == 0) pointArray.getPointN(i).getX else pointArray.getPointN(i).getY
+ ptEps = math.abs(pt - center)
+ if (pivot_eps > ptEps) {
+ pivot = pt
+ pivot_eps = ptEps
+ }
+ }
+ }
+ if (pivot == DBL_MAX) center else pivot
+ }
+}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/Stack.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/Stack.scala
new file mode 100644
index 0000000..711fba2
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/Stack.scala
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.subdivide
+
+import scala.collection.mutable.ArrayBuffer
+
+class Stack[T]{
+
+ private val elements: ArrayBuffer[T] = ArrayBuffer.empty[T]
+
+ def push(element: T): T = {
+ elements += element
+ element
+ }
+
+ def pull(): T = {
+ val last = elements.last
+ elements.remove(elements.length-1)
+ last
+ }
+
+ def isEmpty: Boolean = elements.isEmpty
+}
\ No newline at end of file
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/SubdivideExtent.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/SubdivideExtent.scala
new file mode 100644
index 0000000..e50cf00
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/SubdivideExtent.scala
@@ -0,0 +1,35 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.subdivide
+
+import org.locationtech.jts.geom.Envelope
+
+case class SubdivideExtent(xmin: Double, xmax: Double, ymin: Double, ymax: Double)
+
+object SubdivideExtent {
+ def fromClip(clip: Envelope): SubdivideExtent = SubdivideExtent(
+ xmin = clip.getMinX,
+ xmax = clip.getMaxX,
+ ymin = clip.getMinY,
+ ymax = clip.getMaxY
+ )
+}
+
+case class SubBoxes(subBox: SubdivideExtent, subBox2: SubdivideExtent)
\ No newline at end of file
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/ZeroToleranceGeometrySimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/ZeroToleranceGeometrySimplifier.scala
new file mode 100644
index 0000000..85305df
--- /dev/null
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/ZeroToleranceGeometrySimplifier.scala
@@ -0,0 +1,65 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.spark.sql.sedona_sql.expressions.subdivide
+
+import org.locationtech.jts.geom.Coordinate
+
+import scala.annotation.tailrec
+
+object ZeroToleranceGeometrySimplifier {
+
+ def simplifyInPlaceTolerance0(geom: Array[Coordinate]): Array[Coordinate] =
+ simplifyInPlaceHelper(geom, Seq(), 1, geom.length - 1, geom(0), 0).toArray
+
+ @tailrec
+ private def simplifyInPlaceHelper(geom: Array[Coordinate],
+ resultArray: Seq[Coordinate],
+ currentIndex: Int,
+ lastIndex: Int,
+ keptPoint: Coordinate,
+ keptIt: Int
+ ): Seq[Coordinate] = {
+ if (currentIndex == lastIndex) if (keptIt != lastIndex) resultArray :+ keptPoint :+ geom(lastIndex)
+ else resultArray :+ geom(lastIndex)
+ else {
+ val currPt = geom(currentIndex)
+ val nextPt = geom(currentIndex + 1)
+ val ba_x = nextPt.x - keptPoint.x
+ val ba_y = nextPt.y - keptPoint.y
+ val ab_length_sqr = ba_x * ba_x + ba_y * ba_y
+
+ val ca_x = currPt.x - keptPoint.x
+ val ca_y = currPt.y - keptPoint.y
+ val dot_ac_ab = ca_x * ba_x + ca_y * ba_y;
+ val s_numerator = ca_x * ba_y - ca_y * ba_x
+
+ val isEligible = dot_ac_ab < 0.0 || dot_ac_ab > ab_length_sqr || s_numerator != 0
+
+ simplifyInPlaceHelper(
+ geom = geom,
+ resultArray = if (keptIt != currentIndex && isEligible) resultArray :+ keptPoint else resultArray,
+ currentIndex + 1,
+ lastIndex = lastIndex,
+ keptPoint = if (isEligible) currPt else keptPoint,
+ keptIt = if (isEligible) keptIt + 1 else keptIt
+ )
+ }
+ }
+}
diff --git a/sql/src/test/scala/org/apache/sedona/sql/functionTestScala.scala b/sql/src/test/scala/org/apache/sedona/sql/functionTestScala.scala
index 6758831..3be2324 100644
--- a/sql/src/test/scala/org/apache/sedona/sql/functionTestScala.scala
+++ b/sql/src/test/scala/org/apache/sedona/sql/functionTestScala.scala
@@ -765,6 +765,111 @@ class functionTestScala extends TestBaseScala with Matchers with GeometrySample
calculateStIsRing("POLYGON ((0 0, 0 5, 5 5, 5 0, 0 0), (1 1, 2 1, 2 2, 1 2, 1 1))") shouldBe None
}
+
+ it("should handle subdivision on huge amount of data"){
+ Given("dataframe with 100 huge polygons")
+ val expectedCount = 55880
+ val polygonWktDf = sparkSession
+ .read
+ .format("csv")
+ .option("delimiter", "\t")
+ .option("header", "false").load(mixedWktGeometryInputLocation)
+ .selectExpr("ST_GeomFromText(_c0) AS geom", "_c3 as id")
+
+ When("running st subdivide")
+ val subDivisionExplode = polygonWktDf.selectExpr("id", "ST_SubDivideExplode(geom, 10) as divided")
+ val subDivision = polygonWktDf.selectExpr("id", "ST_SubDivide(geom, 10) as divided")
+
+ Then("result should be appropriate")
+ subDivision.count shouldBe polygonWktDf.count
+ subDivision.select(explode(col("divided"))).count shouldBe expectedCount
+ subDivisionExplode.count shouldBe expectedCount
+ }
+
+ it("should return empty data when the input geometry is null"){
+ Given("dataframe with null geometries")
+ val geodataframe = Seq((1, null)).toDF("id", "geom")
+
+ When("calculating sub divide")
+ val subDivisionExplode = geodataframe.selectExpr("id", "ST_SubDivideExplode(geom, 10)")
+ val subDivision = geodataframe.selectExpr("id", "ST_SubDivide(geom, 10)")
+
+ Then("dataframe exploded should be empty")
+ subDivisionExplode.count shouldBe 0
+
+ And(s"dataframe based on subdivide should be as ${geodataframe.count}")
+ subDivision.count shouldBe 1
+ }
+
+ it("it should return appropriate default column names for st_subdivide"){
+ Given("Sample geometry dataframe with different geometry types")
+ val polygonWktDf = sparkSession
+ .read
+ .format("csv")
+ .option("delimiter", "\t")
+ .option("header", "false").load(mixedWktGeometryInputLocation)
+ .selectExpr("ST_GeomFromText(_c0) AS geom", "_c3 as id")
+
+ When("using ST_SubDivide function")
+ val subDivisionExplode = polygonWktDf.selectExpr("id", "ST_SubDivideExplode(geom, 10)")
+ val subDivision = polygonWktDf.selectExpr("id", "ST_SubDivide(geom, 10)")
+
+ Then("column names should be as expected")
+ subDivisionExplode.columns shouldBe Seq("id", "geom")
+ subDivision.columns shouldBe Seq("id", "st_subdivide(geom, 10)")
+
+ }
+
+ it("should return null values from st subdivide when input row has null value"){
+ Given("Sample dataframe with null values and geometries")
+ val nonNullGeometries = Seq(
+ (1, "LINESTRING (0 0, 1 1, 2 2)"),
+ (2, "POINT (0 0)"),
+ (3, "POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))")
+ ).map{
+ case (id, geomWkt) => (id, wktReader.read(geomWkt))
+ }
+ val nullGeometries: Tuple2[Int, Geometry] = (4, null)
+
+ val geometryTable = (nullGeometries +: nonNullGeometries).toDF("id", "geom")
+
+ When("running ST_SubDivide on dataframe")
+ val subDivision = geometryTable.selectExpr("id", "ST_SubDivide(geom, 10) as divided")
+
+ Then("for null values return value should be null also")
+ subDivision.filter("divided is null")
+ .select("id").as[Long].collect().headOption shouldBe Some(nullGeometries._1)
+
+ And("for geometry type value should be appropriate")
+ subDivision.filter("divided is not null")
+ .select("id").as[Long].collect() should contain theSameElementsAs nonNullGeometries.map(_._1)
+ }
+
+ it("should allow to use lateral view with st sub divide explode"){
+ Given("geometry dataframe")
+ val geometryDf = Seq(
+ (1, "LINESTRING (0 0, 1 1, 2 2)"),
+ (2, "POINT (0 0)"),
+ (3, "POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))"),
+ (4, "POLYGON ((35 10, 45 45, 15 40, 10 20, 35 10), (20 30, 35 35, 30 20, 20 30))")
+ ).map{
+ case (id, geomWkt) => (id, wktReader.read(geomWkt))
+ }.toDF("id", "geometry")
+ geometryDf.createOrReplaceTempView("geometries")
+
+ When("using lateral view on data")
+ val lateralViewResult = sparkSession.sql(
+ """
+ |select id, geom from geometries
+ |LATERAL VIEW ST_SubdivideExplode(geometry, 5) AS geom
+ |""".stripMargin)
+
+
+ Then("result should include exploded geometries")
+ lateralViewResult.count() shouldBe 17
+
+ }
+
private val expectedStartingPoints = List(
"POINT (-112.506968 45.98186)",
"POINT (-112.519856 45.983586)",
diff --git a/sql/src/test/scala/org/apache/sedona/sql/functions/FunctionsHelper.scala b/sql/src/test/scala/org/apache/sedona/sql/functions/FunctionsHelper.scala
new file mode 100644
index 0000000..0c5cf86
--- /dev/null
+++ b/sql/src/test/scala/org/apache/sedona/sql/functions/FunctionsHelper.scala
@@ -0,0 +1,32 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sedona.sql.functions
+
+import org.locationtech.jts.geom.{Geometry, GeometryFactory}
+import org.locationtech.jts.io.{WKTReader, WKTWriter}
+
+trait FunctionsHelper {
+ val geometryFactory = new GeometryFactory()
+ val wktReader = new WKTReader(geometryFactory)
+ val wktWriter = new WKTWriter()
+ def geometryToWkt(geom: Geometry): String = wktWriter.write(geom)
+
+ def readGeometry(wkt: String): Geometry = wktReader.read(wkt)
+}
diff --git a/sql/src/test/scala/org/apache/sedona/sql/functions/TestGeometrySimplify.scala b/sql/src/test/scala/org/apache/sedona/sql/functions/TestGeometrySimplify.scala
new file mode 100644
index 0000000..9b00552
--- /dev/null
+++ b/sql/src/test/scala/org/apache/sedona/sql/functions/TestGeometrySimplify.scala
@@ -0,0 +1,142 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.sedona.sql.functions
+
+import org.apache.spark.sql.sedona_sql.expressions.simplify.GeometrySimplifier
+import org.locationtech.jts.geom.Geometry
+import org.scalatest.funsuite.AnyFunSuite
+import org.scalatest.matchers.should.Matchers
+import org.scalatest.prop.{TableDrivenPropertyChecks, TableFor5}
+
+
+class TestGeometrySimplify extends AnyFunSuite with Matchers with TableDrivenPropertyChecks with FunctionsHelper {
+
+ import Fixtures._
+
+ for ((statement: String, inputGeometry: String, outPutGeometry: String, collapse: Boolean, epsilon: Double) <- Fixtures.geometriesToSimplify) {
+ test("it should simplify geometry " + statement) {
+ Fixtures.simplifyGeometries(inputGeometry, collapse, epsilon).toWkt shouldBe outPutGeometry
+ }
+ }
+
+
+ object Fixtures {
+
+ implicit class GeometryEnhancements(geom: Geometry) {
+ def toWkt: String = wktWriter.write(geom)
+ }
+
+
+ val geometriesToSimplify: TableFor5[String, String, String, Boolean, Double] = Table(
+ ("geometryType", "inputWkt", "expectedResult", "preserve collapsed", "epsilon"),
+ ("point", "POINT (4 43)", "POINT (4 43)", true, 0.0),
+ ("polygon", "POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))", "POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))", true, 0.0),
+ ("linestring", "LINESTRING (1 1, 2 2, 3 2)", "LINESTRING (1 1, 2 2, 3 2)", true, 0.0),
+ ("polygon with few points on the same line",
+ "POLYGON ((45 45, 37.857142857142854 20, 30 20, 10 20, 15 40, 45 45), (30 20, 35 35, 20 30, 30 20))",
+ "POLYGON ((45 45, 37.857142857142854 20, 10 20, 15 40, 45 45), (30 20, 35 35, 20 30, 30 20))",
+ true,
+ 0.0),
+ ("linestring with 10 epsilon", "LINESTRING (0 0, 1 0, 1 1, 0 1, 0 0)", "LINESTRING (0 0, 0 0)", true, 10.0),
+ ("polygon with 10 epsilon", "POLYGON((0 0, 1 0, 1 1, 0 1, 0 0))", "POLYGON ((0 0, 1 0, 1 1, 0 0))", true, 10.0),
+ ("linestring with epsilon 1.0",
+ "LINESTRING (0 0, 50 1.00001, 100 0)",
+ "LINESTRING (0 0, 50 1.00001, 100 0)",
+ false,
+ 1.0
+ ),
+ ("another linestring with epsilon 1, 0", "LINESTRING (0 0, 50 0.99999, 100 0)", "LINESTRING (0 0, 100 0)", false, 1.0),
+ (
+ "polygon with multiple holes",
+ "POLYGON((0 0, 100 0, 100 100, 0 100, 0 0), (1 1, 1 5, 5 5, 5 1, 1 1), (20 20, 20 40, 40 40, 40 20, 20 20))",
+ "POLYGON ((0 0, 100 0, 100 100, 0 100, 0 0), (20 20, 20 40, 40 40, 40 20, 20 20))",
+ false,
+ 10.0
+ ),
+ (
+ "polygon with multiple holes but reordered",
+ "POLYGON ((0 0, 100 0, 100 100, 0 100, 0 0), (20 20, 20 40, 40 40, 40 20, 20 20), (1 1, 1 5, 5 5, 5 1, 1 1))",
+ "POLYGON ((0 0, 100 0, 100 100, 0 100, 0 0), (20 20, 20 40, 40 40, 40 20, 20 20))",
+ false,
+ 10.0
+ ),
+ (
+ "geometry collection with no changes needed",
+ "GEOMETRYCOLLECTION (POINT (2 0), POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0)))",
+ "GEOMETRYCOLLECTION (POINT (2 0), POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0)))",
+ false,
+ 0.0
+ ),
+ (
+ "multilinestring with no changes required",
+ "MULTIPOLYGON (((30 20, 45 40, 10 40, 30 20)), ((15 5, 40 10, 10 20, 5 10, 15 5)))",
+ "MULTIPOLYGON (((30 20, 45 40, 10 40, 30 20)), ((15 5, 40 10, 10 20, 5 10, 15 5)))",
+ false,
+ 0.0
+ ),
+ (
+ "multipolygon with holes",
+ "MULTIPOLYGON (((40 40, 20 45, 45 30, 40 40)), ((20 35, 10 30, 10 10, 30 5, 45 20, 20 35), (30 20, 20 15, 20 25, 30 20)))",
+ "MULTIPOLYGON (((40 40, 20 45, 45 30, 40 40)), ((20 35, 10 30, 10 10, 30 5, 45 20, 20 35), (30 20, 20 15, 20 25, 30 20)))",
+ false,
+ 0.0
+ ),
+ (
+ "multipolygon with duplicated polygons",
+ "MULTIPOLYGON (((30 20, 45 40, 10 40, 30 20)), ((15 5, 40 10, 10 20, 5 10, 15 5)), ((15 5, 40 10, 10 20, 5 10, 15 5)))",
+ "MULTIPOLYGON (((30 20, 45 40, 10 40, 30 20)), ((15 5, 40 10, 10 20, 5 10, 15 5)), ((15 5, 40 10, 10 20, 5 10, 15 5)))",
+ false,
+ 0.0
+ ),
+ (
+ "multipoint",
+ "MULTIPOINT ((10 40), (40 30), (20 20), (30 10))",
+ "MULTIPOINT ((10 40), (40 30), (20 20), (30 10))",
+ false,
+ 0.0
+ ),
+ (
+ "multpoint with duplicated points",
+ "MULTIPOINT ((10 40), (40 30), (20 20), (30 10), (30 10))",
+ "MULTIPOINT ((10 40), (40 30), (20 20), (30 10), (30 10))",
+ false,
+ 0.0
+ ),
+ (
+ "multilinestring",
+ "MULTILINESTRING ((10 10, 20 20, 10 40), (40 40, 30 30, 40 20, 30 10))",
+ "MULTILINESTRING ((10 10, 20 20, 10 40), (40 40, 30 30, 40 20, 30 10))",
+ false,
+ 0.0
+ ),
+ (
+ "multilinestring with duplicated lines",
+ "MULTILINESTRING ((10 10, 20 20, 10 40), (40 40, 30 30, 40 20, 30 10), (40 40, 30 30, 40 20, 30 10))",
+ "MULTILINESTRING ((10 10, 20 20, 10 40), (40 40, 30 30, 40 20, 30 10), (40 40, 30 30, 40 20, 30 10))",
+ false,
+ 0.0
+ )
+ )
+
+ def simplifyGeometries(geom: String, preserveCollapsed: Boolean, epsilon: Double): Geometry =
+ GeometrySimplifier.simplify(wktReader.read(geom), preserveCollapsed, epsilon)
+
+ }
+
+}
diff --git a/sql/src/test/scala/org/apache/sedona/sql/functions/TestStSubDivide.scala b/sql/src/test/scala/org/apache/sedona/sql/functions/TestStSubDivide.scala
new file mode 100644
index 0000000..5e40d74
--- /dev/null
+++ b/sql/src/test/scala/org/apache/sedona/sql/functions/TestStSubDivide.scala
@@ -0,0 +1,101 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sedona.sql.functions
+
+import org.apache.spark.sql.sedona_sql.expressions.subdivide.{GeometrySubDivider, GeometrySubDividerConfiguration}
+import org.locationtech.jts.geom.Geometry
+import org.scalatest.funsuite.AnyFunSuite
+import org.scalatest.matchers.should.Matchers
+import org.scalatest.prop.{TableDrivenPropertyChecks, TableFor3, TableFor4}
+
+import java.io.FileInputStream
+import scala.io.Source
+import scala.tools.nsc.interpreter.InputStream
+
+
+class TestStSubDivide extends AnyFunSuite with Matchers with TableDrivenPropertyChecks with FunctionsHelper {
+
+
+ for ((statement: String, inputGeometry: String, maxVertices: Int, outPutGeometry: Seq[String]) <- Fixtures.testPolygons) {
+ test("it should return subdivide geometry when input geometry is " + statement) {
+ Fixtures.subDivideGeometry(inputGeometry, maxVertices).map(geom => geometryToWkt(geom)) should contain theSameElementsAs outPutGeometry
+ }
+ }
+
+ for ((statement: String, inputGeometry: String, maxVertices: Int) <- Fixtures.geometriesWithNumberOfVerticesLowerThanThreshold) {
+ test("it should return empty sequence when number of vertices is lower than threshold" + statement) {
+ Fixtures.subDivideGeometry(inputGeometry, maxVertices).map(geom => geometryToWkt(geom)) should contain theSameElementsAs Seq()
+ }
+ }
+
+
+ object Fixtures {
+
+ val resourceFolder: String = System.getProperty("user.dir") + "/../core/src/test/resources/"
+
+ private val geometries: Seq[(String, String, Int, Seq[String])] = {
+
+ val input = loadResourceFile(resourceFolder + "subdivide/subdivide_input_geometries.txt").map(
+ line => line.split(";")
+ ).map(elements => (elements.head, elements(1), elements(2), elements(3).toInt))
+ .sortBy(_._1)
+
+ val expected = loadResourceFile(resourceFolder + "subdivide/subdivide_expected_result.txt").map(
+ line => line.split(";")
+ ).map(elements => (elements.head, elements(1)))
+
+ val expectedGrouped = expected.groupBy(_._1)
+
+ expectedGrouped.map{
+ case (key, group) => (key, group.map(_._2))
+ }.toSeq.sortBy(_._1).zip(input)
+ .map{
+ case ((_, resultGeom), (_, testName, inputGeom, subdivisionVertices)) =>
+ (testName, inputGeom, subdivisionVertices, resultGeom)
+ }
+
+ }
+
+ private def loadResourceFile(fileName: String): List[String] = {
+ val stream: InputStream = new FileInputStream(fileName)
+ Source.fromInputStream(stream).getLines.toList
+ }
+
+ val geometriesWithNumberOfVerticesLowerThanThreshold: TableFor3[String, String, Int] = Table(
+ ("geometryType", "inputWkt", "numberOfVertices"),
+ ("point", "POINT(4 43)", GeometrySubDividerConfiguration.minMaxVertices - 1),
+ ("polygon", "POLYGON((0 0, 0 1, 1 1, 1 0, 0 0))", GeometrySubDividerConfiguration.minMaxVertices - 1),
+ ("linestring", "LINESTRING(1 1, 2 2, 3 2)", GeometrySubDividerConfiguration.minMaxVertices - 1)
+ )
+
+ val testPolygons: TableFor4[String, String, Int, Seq[String]] = Table(
+ ("statement", "input", "maxVertices", "output"),
+ geometries:_*
+ )
+
+ def subDivideGeometry(wkt: String, maxVertices: Int): Seq[Geometry] =
+ subDivideGeometry(readGeometry(wkt), maxVertices)
+
+ def subDivideGeometry(geom: Geometry, maxVertices: Int): Seq[Geometry] =
+ GeometrySubDivider.subDivide(geom, maxVertices)
+ }
+
+
+}