lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java

/*
 * 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.lucene.geo;

import java.text.ParseException;
import java.util.List;

import org.apache.lucene.util.LuceneTestCase;

import static org.apache.lucene.geo.GeoTestUtil.nextBoxNotCrossingDateline;

/** Test case for the Polygon {@link Tessellator} class */
public class TestTessellator extends LuceneTestCase {

  /** test line intersection */
  public void testLinesIntersect() {
    Rectangle rect = nextBoxNotCrossingDateline();
    // simple case; test intersecting diagonals
    // note: we don't quantize because the tessellator operates on non quantized vertices
    assertTrue(Tessellator.linesIntersect(rect.minLon, rect.minLat, rect.maxLon, rect.maxLat, rect.maxLon, rect.minLat, rect.minLon, rect.maxLat));
    // test closest encoded value
    assertFalse(Tessellator.linesIntersect(rect.minLon, rect.maxLat, rect.maxLon, rect.maxLat, rect.minLon - 1d, rect.minLat, rect.minLon - 1, rect.maxLat));
  }

  public void testSimpleTessellation() throws Exception {
    Polygon poly = GeoTestUtil.createRegularPolygon(0.0, 0.0, 100000, 100000);
    Polygon inner = new Polygon(new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
        new double[]{1.0, -1.0, -0.5, -1.0, 1.0, 0.5, 1.0});
    Polygon inner2 = new Polygon(new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
        new double[]{-2.0, -4.0, -3.5, -4.0, -2.0, -2.5, -2.0});
    poly = new Polygon(poly.getPolyLats(), poly.getPolyLons(), inner, inner2);
    assertTrue(Tessellator.tessellate(poly).size() > 0);
  }
  
  @Nightly
  public void testSimpleTessellationAtNight() throws Exception {
    Polygon poly = GeoTestUtil.createRegularPolygon(0.0, 0.0, 1000000, 1000000);
    Polygon inner = new Polygon(new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
        new double[]{1.0, -1.0, -0.5, -1.0, 1.0, 0.5, 1.0});
    Polygon inner2 = new Polygon(new double[] {-1.0, -1.0, 0.5, 1.0, 1.0, 0.5, -1.0},
        new double[]{-2.0, -4.0, -3.5, -4.0, -2.0, -2.5, -2.0});
    poly = new Polygon(poly.getPolyLats(), poly.getPolyLons(), inner, inner2);
    assertTrue(Tessellator.tessellate(poly).size() > 0);
  }

  public void testLUCENE8454() throws ParseException {
    String geoJson = "{\"type\": \"Polygon\", \"coordinates\": [[[167.8752929333776, -30.078235509309092], [167.729078, -30.078368], [167.7288750679411, -29.918443128222044], [167.728949, -30.078598], [167.582239, -30.078557], [167.58234527408044, -29.9717026229659],  " +
        "[167.43547018634274, -30.030896196337487], [167.43528, -30.078575], [167.288467, -30.078185], [167.28846777961195, -30.078041819512045], [167.142089, -30.077483], [167.143635, -29.813199], [167.1450859974141, -29.567345798606294], [167.144888, -29.567345], " +
        "[167.14633281276596, -29.302953194679134], [167.146281, -29.302953], [167.147725, -29.036352], [167.292924, -29.036892], [167.2918703799358, -29.301396273146477], [167.29192460356776, -29.301396365495897], [167.292964, -29.036798], [167.4380298884901, -29.037250444489867], " +
        "[167.43803, -29.03719], [167.583317, -29.037381], [167.58331697583935, -29.03744011447325], [167.7285250024388, -29.037514998454153], [167.728525, -29.03749], [167.873835, -29.037419], [167.87383543708486, -29.037703808329873], [168.018612, -29.037121], " +
        "[168.0186121103674, -29.03714161109612], [168.163842, -29.03656], [168.1650939339767, -29.247683610268638], [168.164004, -29.036724], [168.309341, -29.036127], [168.3110870459225, -29.30068025473746], [168.311176, -29.30068], [168.312472, -29.567161], " +
        "[168.31243194795024, -29.56716111631554], [168.31443, -29.812612], [168.31388505737894, -29.812615143334597], [168.315886, -30.077081], [168.169234, -30.077883], [168.16913368505345, -30.06147402418803], [168.169224, -30.077737], [168.022447, -30.078317], " +
        "[168.02181920125142, -29.924959173336568], [168.0221, -30.078254], [167.875293, -30.078413], [167.8752929333776, -30.078235509309092]]," + //holes
        "[[167.43638852926597, -29.811913377451322], [167.43642819713568, -29.81191343893342], [167.43660948310222, -29.684470839430233], [167.43638852926597, -29.811913377451322]], " +
        "[[167.2900169281376, -29.811700260790584], [167.29007609051774, -29.811700416752192], [167.29022481985885, -29.765019899914726], [167.2900169281376, -29.811700260790584]], " +
        "[[167.72865676499967, -29.812149953736277], [167.7287401903084, -29.81214997654223], [167.72874, -29.812], [167.72893197342373, -29.81199982820994], [167.72851531939722, -29.568503012044204], [167.72851327553326, -29.568503011862287], [167.72865676499967, -29.812149953736277]], " +
        "[[167.87424106545097, -29.302014822030415], [167.87432742269175, -29.30201461402921], [167.87418553426855, -29.265830214765142], [167.87424106545097, -29.302014822030415]], " +
        "[[168.1652103335658, -29.3030088541673], [168.16605788758287, -29.446580625201833], [168.16556735186845, -29.303245228857072], [168.165381, -29.303246], [168.16537977124085, -29.303008170411644], [168.1652103335658, -29.3030088541673]], " +
        "[[168.02088551865063, -29.647294313012004], [168.02133932508806, -29.811843292379823], [168.02135614030843, -29.811843274349446], [168.021356, -29.811809], [168.02162340579383, -29.811807949652078], [168.02088551865063, -29.647294313012004]]]}";
    Polygon[] polygons =Polygon.fromGeoJSON(geoJson);
    List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0]);
    assertEquals(result.size(), 84);
  }

  public void testLUCENE8534() throws ParseException {
    String geoJson = "{\"type\":\"Polygon\",\"coordinates\":[[[168.412605,-32.061828],[168.41260500337557,-32.06164814731918],[168.263154,-32.061754],[168.263074,-31.795333],[168.2631866330167,-31.79533292075007],[168.26293615809584,-31.55183198959802],[168.26271862830876,-31.55183199836296]," +
        "[168.26260885857246,-31.79551898342183],[168.262799,-31.795519],[168.262922,-32.061969],[168.113391,-32.061955],[168.1136947020627,-31.797506925167987],[168.1134623401242,-31.7975067304478],[168.112867,-32.061933],[167.96342,-32.061572],[167.964447,-31.795078],[167.96462554945853,-31.79507843013861]," +
        "[167.96521264500555,-31.551376165945904],[167.965145,-31.551376],[167.9663078329189,-31.287013079577566],[167.966251,-31.287013],[167.9664724470441,-31.186852765132446],[167.966135,-31.286996],[167.96583002270634,-31.28699509215832],[167.96514242732414,-31.530648904745615],[167.96518,-31.530649]," +
        "[167.964244373485,-31.795342905910022],[167.964267,-31.795343],[167.963051,-32.06191],[167.813527,-32.061286],[167.81515841152935,-31.796764131690956],[167.815107,-31.796764],[167.8163675951437,-31.55101526478777],[167.81635023954297,-31.551015225373174],[167.814827,-31.796834]," +
        "[167.81479823247224,-31.796833898826222],[167.813495,-32.061159],[167.664068,-32.060513],[167.66581,-31.794011],[167.6658519100183,-31.794011179736117],[167.6677495759609,-31.550438401064135],[167.667432,-31.550437],[167.66930180157829,-31.286073839134556],[167.669105,-31.286073],[167.670807,-31.019532]," +
        "[167.818843,-31.020159],[167.8175723936035,-31.284543327213736],[167.81766095836642,-31.284543526532044],[167.818971,-31.020062],[167.967033,-31.020499],[167.96703262843647,-31.020609267886275],[168.114968,-31.020815],[168.1149445990616,-31.05814524188174],[168.114978,-31.020912],[168.26306,-31.021035]," +
        "[168.2631849793437,-31.203987591682104],[168.263163,-31.021002],[168.411259,-31.020914],[168.41125954741193,-31.02123593258559],[168.5589863328454,-31.020786105561243],[168.558986,-31.020705],[168.707027,-31.020199],[168.70828992266655,-31.242361611483734],[168.707298,-31.020426],[168.855538,-31.019789]," +
        "[168.85713808565947,-31.284233200286536],[168.857209,-31.284233],[168.8583969293829,-31.54547348363567],[168.86057,-31.796021],[168.86004803213373,-31.796023826818654],[168.862202,-32.060514],[168.712722,-32.061376],[168.71099229524427,-31.796760977737968],[168.7108263042178,-31.79676167516991],[168.712468,-32.061301]," +
        "[168.56291,-32.061787],[168.561684,-31.795261],[168.56198761104602,-31.795260018704994],[168.560821,-31.530975],[168.56092374559077,-31.530974570518158],[168.56001677082173,-31.287057906497665],[168.5597021283975,-31.287058866102726],[168.5607530382453,-31.530880020491022],[168.560769,-31.53088]," +
        "[168.56079128925168,-31.539754620482725],[168.560842,-31.55152],[168.56082083893278,-31.551520031401303],[168.56143311036655,-31.7953001584517],[168.561622,-31.7953],[168.562045,-32.0617],[168.412605,-32.061828]]," +
        "[[168.41212499436773,-31.68171617103951],[168.41200593405762,-31.551740860609502],[168.411912,-31.551741],[168.41154546767467,-31.416898111348704],[168.41158059852074,-31.53102923335134],[168.411729,-31.531029],[168.41212499436773,-31.68171617103951]]," +
        "[[168.7083938476212,-31.28652950649234],[168.70945084576658,-31.485690997091577],[168.70886199577689,-31.28667838236468],[168.708488,-31.28668],[168.7084873259438,-31.28652918474386],[168.7083938476212,-31.28652950649234]]," +
        "[[168.71121460687698,-31.795031659971823],[168.71136127361123,-31.79503081865431],[168.71038567290682,-31.657182838382653],[168.71121460687698,-31.795031659971823]]," +
        "[[167.81624041598312,-31.53023516975434],[167.81634270442586,-31.530235525706665],[167.81676369867318,-31.434841665952604],[167.81624041598312,-31.53023516975434]]]}";
    Polygon[] polygons =Polygon.fromGeoJSON(geoJson);
    List<Tessellator.Triangle> result = Tessellator.tessellate(polygons[0]);
    assertEquals(113, result.size());
  }

  public void testInvalidPolygon()  throws Exception {
    String wkt = "POLYGON((0 0, 1 1, 0 1, 1 0, 0 0))";
    Polygon polygon = (Polygon)SimpleWKTShapeParser.parse(wkt);
    expectThrows( IllegalArgumentException.class, () -> {Tessellator.tessellate(polygon); });
  }

  public void testLUCENE8550()  throws Exception {
    String wkt = "POLYGON((24.04725 59.942,24.04825 59.94125,24.04875 59.94125,24.04875 59.94175,24.048 59.9425,24.0475 59.94275,24.0465 59.94225,24.046 59.94225,24.04575 59.9425,24.04525 59.94225,24.04725 59.942))";
    Polygon polygon = (Polygon)SimpleWKTShapeParser.parse(wkt);
    assertTrue(Tessellator.tessellate(polygon).size() == 8);
  }

  public void testLUCENE8559()  throws Exception {
    String wkt = "POLYGON((-0.1348674 51.7458255,-0.1345884 51.7455067,-0.1329898 51.745314,-0.1326358 51.745314,-0.1324105 51.744404,-0.131981 51.7444423,-0.1312196 51.7445102,-0.1310908 51.7456794,-0.1319706 51.7460713,-0.1343095 51.7465828,-0.1348674 51.7458255)," +
        "(-0.1322388 51.7447959,-0.1322388 51.7454336,-0.1318633 51.7457126,-0.1313912 51.7456262,-0.1318985 51.7448032,-0.1322388 51.7447959))";
    checkPolygon(wkt);
  }

  public void testLUCENE8556()  throws Exception {
    String wkt ="POLYGON((-111.4765 68.321,-111.47625 68.32225,-111.4765 68.3225,-111.478 68.3225,-111.47825 68.32275,-111.479 68.32275,-111.47975 68.32325,-111.48125 68.324,-111.4815 68.32375,-111.48175 68.32375," +
        "-111.48225 68.32425,-111.48275 68.32425,-111.483 68.324,-111.4845 68.324,-111.48475 68.32425,-111.4845 68.32475,-111.48425 68.3245,-111.483 68.325,-111.4835 68.325,-111.48425 68.3255,-111.48525 68.3255,-111.4855 68.32575," +
        "-111.4855 68.32525,-111.486 68.32475,-111.48725 68.3245,-111.4875 68.32475,-111.48725 68.325,-111.487 68.325,-111.4865 68.32525,-111.487 68.32575,-111.486465 68.326385,-111.486 68.326,-111.48575 68.32625," +
        "-111.48525 68.32625,-111.485 68.326,-111.48375 68.326,-111.48225 68.3265,-111.483 68.3265,-111.48325 68.32675,-111.4835 68.3265,-111.48675 68.3265,-111.487 68.32675,-111.48675 68.32725,-111.4865 68.327," +
        "-111.48375 68.32775,-111.485 68.32775,-111.48525 68.3275,-111.4855 68.3275,-111.486 68.32775,-111.48625 68.3275,-111.48675 68.3275,-111.48725 68.327,-111.48775 68.327,-111.4875 68.32625,-111.488 68.32625," +
        "-111.48825 68.32675,-111.49025 68.327,-111.49025 68.32675,-111.4905 68.3265,-111.49075 68.3265,-111.49125 68.326,-111.492 68.32575,-111.4945 68.32575,-111.49475 68.3255,-111.49525 68.3255,-111.4955 68.32525,-111.49625 68.32525," +
        "-111.4965 68.325,-111.49775 68.32425,-111.498 68.3245,-111.4985 68.3245,-111.49875 68.32425,-111.49925 68.32425,-111.5005 68.324,-111.50075 68.32375,-111.501 68.32375,-111.501 68.323,-111.5015 68.323,-111.50175 68.32325,-111.5015 68.3235," +
        "-111.5025 68.32375,-111.50275 68.3235,-111.504 68.32375,-111.50425 68.3235,-111.50525 68.32325,-111.5055 68.3235,-111.506 68.3235,-111.50625 68.32325,-111.5065 68.3225,-111.5075 68.3225,-111.50775 68.32275,-111.50825 68.32275," +
        "-111.5085 68.3225,-111.50875 68.3225,-111.509 68.32275,-111.5125 68.32275,-111.51325 68.32225,-111.4765 68.321))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon01() throws Exception {
    String wkt = "POLYGON((58.8792517 54.9160937, 58.8762477 54.9154524, 58.8735011 54.9140217, 58.8726428 54.9127389, 58.8731146 54.9122507, 58.8741877 54.9120482, 58.8771918 54.9117028, 58.88011 54.913331, 58.8801175 54.9137036, 58.8805885 54.9143186, 58.8807109 54.9148604, 58.88011 54.915551, 58.8792517 54.9160937), " +
        "(58.8746003 54.9125589, 58.8766188 54.9137965, 58.8791419 54.9152275, 58.8798554 54.9151074, 58.8805548 54.9146087, 58.8801175 54.9137036, 58.8788867 54.9130833, 58.8790905 54.9128921, 58.8767533 54.9120561, 58.8748358 54.9122495, 58.8744557 54.9124049, 58.8746003 54.9125589))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon02() throws Exception {
    String wkt = "POLYGON((-0.5033651 48.7307175, -0.5036334 48.7300183, -0.5038592 48.7297349, -0.5044826 48.7295356, -0.5049852 48.72953, -0.504857 48.7301383, -0.5041382 48.7310084, -0.5033651 48.7307175), " +
        "(-0.504035 48.730838, -0.504282 48.730519, -0.504718 48.729958, -0.504778 48.72988, -0.504545 48.729797, -0.50448 48.729774, -0.503721 48.73073, -0.504035 48.730838), " +
        "(-0.50448 48.729774, -0.504545 48.729797, -0.504708 48.729597, -0.50458 48.729554, -0.504419 48.729753, -0.50448 48.729774))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon03() throws Exception {
    String wkt ="POLYGON((57.7258102 -20.1927474, 57.7257611 -20.192854, 57.7260971 -20.1929559, 57.726191 -20.1929232, 57.7262648 -20.1926211, 57.7262165 -20.1925544, 57.7260649 -20.1924877, 57.7259684 -20.1924678, 57.7259333 -20.1925297, 57.7258102 -20.1927474)," +
        " (57.7259333 -20.1925297, 57.7258471 -20.1927671, 57.7259774 -20.1928078, 57.7260433 -20.1925557, 57.7259333 -20.1925297))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon04() throws Exception {
    String wkt ="POLYGON((139.2749646 36.2742799, 139.2747468 36.2743137, 139.2747057 36.2743705, 139.2745531 36.2743918, 139.2744944 36.2743563, 139.2719227 36.2747799, 139.2719021 36.2748249, 139.2723724 36.2762706, 139.2724692 36.2765445, 139.2725362 36.2765573, 139.2754328 36.2760613, 139.2749646 36.2742799), " +
        "(139.2726473 36.2762561, 139.2726277 36.2760151, 139.2723528 36.2760297, 139.2723724 36.2762706, 139.2726473 36.2762561))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon05() throws Exception {
    String wkt ="POLYGON((8.6778468 49.8622443, 8.6782001 49.8622443, 8.6786272 49.8622443, 8.6790127 49.8622444, 8.6790127 49.8620355, 8.678775 49.8620355, 8.6780348 49.8620354, 8.6778468 49.8620354, 8.6778468 49.8622443)," +
        " (8.6785777 49.8621738, 8.6785775 49.8620923, 8.678253 49.8620926, 8.6782532 49.8621741, 8.6785777 49.8621738)," +
        " (8.6781491 49.8621742, 8.6781491 49.8620925, 8.6779802 49.8620925, 8.6779802 49.8621742, 8.6781491 49.8621742))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon06() throws Exception {
    String wkt ="POLYGON((-77.578272 38.7906104, -77.5784061 38.7901379, -77.5785349 38.7897198, -77.5786743 38.7894522, -77.5787441 38.7892306, -77.578846 38.7891679," +
        " -77.5789104 38.7891762, -77.5789747 38.789239, -77.5789747 38.7893979, -77.5789694 38.789586, -77.5789104 38.7897449, -77.5789104 38.7898494," +
        " -77.5789104 38.7900083, -77.5789157 38.7901714, -77.5789157 38.7903052, -77.5790659 38.7903972, -77.5791786 38.7905101, -77.5792215 38.7905979," +
        " -77.5789962 38.7906439, -77.5787977 38.7905268, -77.5786529 38.7904724, -77.5785027 38.7905352, -77.578272 38.7906104))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon07() throws Exception {
    String wkt ="POLYGON((27.481388 53.871276, 27.481388 53.870876, 27.4809477 53.870876, 27.4808096 53.870876, 27.480293 53.870876, 27.480287 53.871276, 27.481388 53.871276)," +
        " (27.481145 53.870998, 27.481145 53.871173, 27.480674 53.871173, 27.480674 53.870998, 27.481145 53.870998))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon08() throws Exception {
    String wkt ="POLYGON((27.473089 53.862247, 27.473089 53.86185, 27.4726752 53.86185, 27.4726755 53.8617698, 27.4725118 53.8617698, 27.4725116 53.86185, 27.471994 53.86185, 27.471994 53.862247," +
        " 27.473089 53.862247), (27.472547 53.861969, 27.472847 53.861969, 27.472852 53.862163, 27.472375 53.862163, 27.472375 53.861969, 27.472547 53.861969))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon09() throws Exception {
    String wkt ="POLYGON((27.4822056 53.9262047, 27.482123 53.9262047, 27.4820878 53.9262047, 27.4816412 53.9262047, 27.4816412 53.9265967, 27.4821202 53.9265967, 27.4826562 53.9265967, 27.4826562 53.9262047," +
        " 27.4823321 53.9262047, 27.4822831 53.9262047, 27.4822056 53.9262047)," +
        " (27.482419 53.9263193, 27.482419 53.9265023, 27.4821217 53.9265023, 27.481969 53.9265023, 27.481969 53.9263193, 27.482419 53.9263193))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon10() throws Exception {
    String wkt ="POLYGON((12.3480275 49.1830779, 12.3481411 49.1830974, 12.3481318 49.1831254, 12.3482695 49.1831485, 12.348275 49.1831181, 12.3486026 49.1831619, 12.3486007 49.1831728, 12.3486919 49.1831838, 12.3487068 49.1831254, 12.3487505 49.1831275, 12.3487501 49.1831345, 12.3487603 49.1831348, 12.3487608 49.1831278, 12.3488143 49.1831172, 12.3488222 49.1831239, 12.348831 49.183119, 12.3488231 49.1831123, 12.3488259 49.1830731," +
        " 12.3488361 49.1830697, 12.348831 49.1830637, 12.3488198 49.183067, 12.3487724 49.1830393, 12.3487724 49.1830311, 12.3487631 49.1830317, 12.3487621 49.1830399, 12.348731 49.1830323, 12.3489338 49.1823572, 12.3489617 49.1823499, 12.3489841 49.1823372, 12.3489831 49.1823171, 12.3489738 49.1823025, 12.3489543 49.1822934, 12.3489217 49.1822915," +
        " 12.3489329 49.1822447, 12.3487124 49.1822222, 12.3486965 49.18228, 12.348115 49.1822167, 12.348128 49.1821559, 12.3479326 49.182131, 12.3479233 49.1821894, 12.3479168 49.1821711, 12.3478917 49.1821638, 12.3478573 49.1821699, 12.3478387 49.1821857, 12.3478405 49.1822046, 12.3478498 49.1822167, 12.3478722 49.1822253, 12.3478833 49.1822253, 12.347713 49.1828626, 12.3480806 49.1829168, 12.3480275 49.1830779)," +
        " (12.348571 49.1828869, 12.3487052 49.182425, 12.3480373 49.1823465, 12.34791 49.1828088, 12.3482676 49.1828517, 12.348571 49.1828869)," +
        " (12.3482676 49.1828517, 12.3482341 49.1829685, 12.348537 49.1830042, 12.348571 49.1828869, 12.3482676 49.1828517))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon11() throws Exception {
    String wkt ="POLYGON((-95.252045 42.897609, -95.251709 42.897569, -95.251523 42.897554, -95.25137 42.897559, -95.251315 42.897561, -95.250753 42.89763, -95.25024 42.897716, -95.249356 42.897835, -95.24884 42.897905, -95.248685 42.897924, -95.248686 42.89805, -95.248691 42.89843, -95.248693 42.898557, -95.234751 42.898871, -95.234631 42.890847, -95.237959 42.890779, -95.237885 42.886205, -95.249964 42.886255, -95.249943 42.894309, -95.248836 42.894259, -95.248759 42.895872, -95.252112 42.896047, -95.252045 42.897609)," +
        " (-95.248685 42.897924, -95.248686 42.897876, -95.248693 42.897732, -95.248696 42.897685, -95.248546 42.897171, -95.248097 42.89563, -95.247977 42.895217, -95.247948 42.895117, -95.247912 42.895, -95.247876 42.894882, -95.247835 42.89475, -95.247497 42.89365, -95.247449 42.893492, -95.247238 42.893441, -95.246999 42.893542, -95.246988 42.89369, -95.246984 42.893751, -95.24728 42.894877, -95.247289 42.89491, -95.247317 42.895016, -95.247345 42.895121, -95.247366 42.895203, -95.247384 42.895273, -95.247397 42.895323," +
        " -95.24752 42.895818, -95.247927 42.897456, -95.248063 42.898003, -95.248128 42.897991, -95.248154 42.897987, -95.24843 42.897953, -95.248523 42.897943, -95.248555 42.897938, -95.248652 42.897927, -95.248685 42.897924))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon12() throws Exception {
    String wkt ="POLYGON((-85.418489 41.768716, -85.418482 41.767212, -85.418481 41.766867, -85.408741 41.766911, -85.408745 41.763218, -85.41744 41.763171, -85.41744 41.763335, -85.418456 41.763335, -85.418455 41.763171, -85.420528 41.763171, -85.420843 41.766839, -85.420937 41.768716, -85.418489 41.768716)," +
        " (-85.418481 41.766867, -85.419141 41.766859, -85.419173 41.766858, -85.41923 41.766313, -85.418477 41.766272, -85.418481 41.766867))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon13() throws Exception {
    String wkt ="POLYGON((30.6852741 59.9232998, 30.6856122 59.9236242, 30.6859407 59.9236291, 30.6863851 59.9235177, 30.6867039 59.9233144, 30.6866169 59.9231159, 30.6864044 59.9229464, 30.6860566 59.9227285, 30.6855736 59.9228496, 30.6850036 59.9228012, 30.6851775 59.9229755, 30.6851496 59.9229971, 30.6850712 59.9230578, 30.6847911 59.923019, 30.6849843 59.923174, 30.6851872 59.9232078, 30.685361 59.9232127, 30.6852741 59.9232998)," +
        " (30.6851678 59.9231308, 30.6852544 59.9231618, 30.6853904 59.923171, 30.6855264 59.9231927, 30.6856625 59.9231865, 30.6857366 59.9232113, 30.6858912 59.923171, 30.6858418 59.9231122, 30.6857366 59.9230936, 30.6857181 59.9230223, 30.6856254 59.9229541, 30.6854399 59.9229634, 30.6853409 59.9229603, 30.6853162 59.9230037, 30.6851496 59.9229971, 30.6851431 59.9230657, 30.6851678 59.9231308))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon14() throws Exception {
    String wkt ="POLYGON((-2.7996138 53.4243001, -2.7995616 53.4243095, -2.7995084 53.4243189, -2.7994612 53.4243274, -2.7995377 53.4243807, -2.7995906 53.4243689, -2.7996138 53.4243001)," +
        " (-2.7995616 53.4243095, -2.7995429 53.4243345, -2.7995084 53.4243189, -2.7995616 53.4243095))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon15() throws Exception {
    String wkt ="POLYGON((5.3247527 61.4108691, 5.3247243 61.4105839, 5.3250792 61.4107616, 5.325961 61.4108553, 5.3266624 61.4110128, 5.3270003 61.4110466, 5.3274267 61.4111918, 5.3274094 61.4112734," +
        " 5.3275956 61.411337, 5.328454 61.4117214, 5.3288879 61.4117593, 5.3293803 61.4119717, 5.3292581 61.412102, 5.3294948 61.4124709, 5.3288962 61.4128764, 5.3282449 61.4129021," +
        " 5.3274134 61.4130613, 5.3271761 61.413222, 5.3263619 61.413395, 5.3263619 61.413395, 5.3258351 61.4131221, 5.3255073 61.4131218, 5.325332 61.4129946, 5.3253043 61.4127856," +
        " 5.3250305 61.4128579, 5.3245279 61.4126489, 5.3244206 61.4124399, 5.3244415 61.4122399, 5.324192 61.4118966, 5.3242034 61.4117109, 5.3244695 61.4115646, 5.3250112 61.4113443, 5.3251052 61.4111494, 5.3247527 61.4108691))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon16() throws Exception {
    String wkt ="POLYGON((34.6110434 62.1752511, 34.6109864 62.1751687, 34.6115575 62.1749522, 34.6112716 62.1749876, 34.6109715 62.1750879," +
        " 34.6100197 62.1751666, 34.6101212 62.1750403, 34.6120273 62.1747823, 34.6122303 62.1746507, 34.6122529 62.1745243, 34.6126928 62.1743506," +
        " 34.6127717 62.1742295, 34.6133808 62.1740189, 34.6134823 62.1737767, 34.6077526 62.174577, 34.6077301 62.1745138, 34.6133695 62.1737135, " +
        "34.6133357 62.1736451, 34.6115085 62.1734924, 34.6100986 62.1737399, 34.6094445 62.1737715, 34.6093204 62.1737293, 34.6102227 62.1735082, " +
        "34.6100535 62.1731765, 34.6099069 62.1731081, 34.6093204 62.1730133, 34.6092414 62.1733081, 34.6079556 62.1742664, 34.6077075 62.1743453, " +
        "34.6070646 62.1749034, 34.6070082 62.1751614, 34.6065683 62.1757352, 34.6063428 62.1760353, 34.6063879 62.1762669, 34.606027 62.1767986, " +
        "34.6054292 62.1772987, 34.6050795 62.1773987, 34.604572 62.1775251, 34.6046848 62.177662, 34.6052374 62.1776409, 34.605948 62.1773987, " +
        "34.6066022 62.1770671, 34.6076962 62.1765564, 34.6078654 62.1761511, 34.6080684 62.1759247, 34.6082038 62.1755667, 34.6085524 62.1755425, " +
        "34.6090384 62.1755088, 34.6110434 62.1752511)," +
        " (34.6098618 62.1749455, 34.6119935 62.1745664, 34.6120386 62.1744559, 34.6098505 62.1748665, 34.6098618 62.1749455), " +
        " (34.6098731 62.1745717, 34.6119596 62.174219, 34.6119935 62.17414, 34.6098731 62.1745085, 34.6098731 62.1745717)," +
        " (34.6086549 62.1754193, 34.6086211 62.1745717, 34.6084632 62.1746296, 34.6085309 62.1754351, 34.6086549 62.1754193)," +
        " (34.6091963 62.1753298, 34.6091286 62.174577, 34.608982 62.1745822, 34.6090723 62.1753877, 34.6091963 62.1753298)," +
        " (34.6097264 62.1751508, 34.60967 62.1745717, 34.6095347 62.1745717, 34.6095798 62.1751508, 34.6097264 62.1751508))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon17() throws Exception {
    String wkt ="POLYGON((14.1989238 40.8274753, 14.1990593 40.8275004, 14.1991793 40.8275226, 14.1993451 40.8275478, 14.1993761 40.8275525, 14.1994599 40.8275746, 14.1996909 40.8276174, 14.1996769 40.8276728, 14.1993975 40.8277665, " +
        "14.1993717 40.8277752, 14.1992074 40.8278304, 14.1990929 40.8278688, 14.1989635 40.8279122, 14.1988594 40.8276864, 14.1989238 40.8274753), (14.1993717 40.8277752, 14.1993975 40.8277665, 14.1995864 40.8276576, 14.1994599 40.8275746," +
        " 14.1993761 40.8275525, 14.1993451 40.8275478, 14.1993073 40.8276704, 14.1993717 40.8277752), (14.1990593 40.8275004, 14.1989907 40.8276889, 14.1990929 40.8278688, 14.1992074 40.8278304, 14.1991335 40.8276763, 14.1991793 40.8275226, 14.1990593 40.8275004))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon18() throws Exception {
    String wkt = "POLYGON((-6.0057153 37.378144, -6.0056993 37.3781273, -6.005663 37.3781481, -6.0056241 37.3781101, -6.0056938 37.3780656, " +
        "-6.0057319 37.3781066, -6.0057619 37.3780888, -6.0057645 37.3780916, -6.0057775 37.3781049, -6.0057153 37.378144), " +
        "(-6.0056993 37.3781273, -6.0057275 37.3781093, -6.0057052 37.3780871, -6.005677 37.378105, -6.0056993 37.3781273))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon19() throws Exception {
    String wkt ="POLYGON((60.3629011 55.1038828,60.3686333 55.0945319, 60.3696616 55.0944318, 60.3701429 55.094269, 60.3707555 55.094269, 60.3719807 55.0942941, 60.373184 55.0941939, 60.3738841 55.0938559, 60.3741685 55.0938809, 60.3752406 55.0940311, 60.3760938 55.0940687, 60.3765751 55.0941188, 60.3789161 55.1022181, 60.3629011 55.1038828)," +
        " (60.3685348 55.098134, 60.3685348 55.0980714, 60.3681634 55.0980759, 60.3681629 55.0980119, 60.3681738 55.0979431, 60.3682285 55.0978304, 60.3681848 55.0976426, 60.3681902 55.0974298, 60.3682887 55.0972671, 60.368409 55.0972264, 60.3685786 55.0972858, 60.3687044 55.0973234, 60.3688083 55.0972639, 60.368956 55.0972639, 60.3692185 55.0972545, 60.3692294 55.0973328, 60.3692732 55.0975612, 60.369306 55.0977177, 60.369306 55.0979681, 60.3690654 55.0980682, 60.3688411 55.0981308, 60.3685348 55.098134), " +
        "(60.3680535 55.098256, 60.3685348 55.0982529, 60.3685348 55.098134, 60.3685348 55.0980714, 60.3681634 55.0980759, 60.3680261 55.0980776, 60.3680535 55.098256))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon20() throws Exception {
    String wkt ="POLYGON((11.4224981 52.1936005, 11.4228777 52.1934599, 11.4231781 52.1933004, 11.424204 52.192568, 11.4236675 52.1919366, 11.4234208 52.1912986, 11.4233564 52.1909237, 11.4223763 52.1907738, 11.4217128 52.1907656, 11.4216977 52.1908798, 11.421629 52.1923707, 11.422541 52.1924299, 11.422777 52.1927784, 11.4226268 52.1934559, 11.4224981 52.1936005), " +
        "(11.4230184 52.1931194, 11.4229045 52.1928061, 11.4228337 52.1924324, 11.4230153 52.192289, 11.4233217 52.1919891, 11.4233614 52.1919891, 11.4234102 52.1919891, 11.4238071 52.1925876, 11.4232185 52.1930477, 11.4230184 52.1931194), " +
        "(11.4233029 52.1918642, 11.4233614 52.1919891, 11.4233217 52.1919891, 11.423267 52.191863, 11.4230829 52.191851, 11.4228576 52.1916768, 11.4219593 52.191568, 11.4217993 52.1914605, 11.4218547 52.1910641, 11.4225773 52.1909533, 11.4229569 52.1910092, 11.423142 52.1911144, 11.4233029 52.1918642))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon21() throws Exception {
    String wkt ="POLYGON((-8.8695167 38.5283886, -8.8695085 38.5280497, -8.8692041 38.5280497, -8.869208 38.528419, -8.8692324 38.5284411, -8.8693155 38.5284589, -8.8694778 38.5284138, -8.8695167 38.5283886)," +
        " (-8.8693914 38.5283407, -8.8692384 38.5283407, -8.8692383 38.5281424, -8.8693914 38.5281424, -8.8693914 38.5283297, -8.8693914 38.5283407)," +
        " (-8.8694452 38.5283297, -8.8693914 38.5283297, -8.8693914 38.5281424, -8.8693914 38.5281131, -8.8694451 38.5281131, -8.8694452 38.5283297))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon22() throws Exception {
    String wkt ="POLYGON((64.0209362 61.4681776, 64.0210248 61.4682157, 64.0211071 61.4682512, 64.0212391 61.468193, 64.021904 61.4681913, 64.0220258 61.468256, 64.0221224 61.4682435, 64.022299 61.4682161, 64.0222172 61.4681665, 64.0221553 61.4681319, 64.0218224 61.4679859, 64.0216788 61.4679836, 64.0216784 61.4679438, 64.0216361 61.4679187, 64.0215193 61.4679187, 64.0214889 61.4679414, 64.0214838 61.4679883, 64.021362 61.4679891, 64.0209362 61.4681776)," +
        " (64.0215237 61.4680208, 64.021635 61.4680208, 64.021635 61.4680058, 64.021635 61.4679288, 64.0215237 61.4679288, 64.0215237 61.4680058, 64.0215237 61.4680208)," +
        " (64.0215227 61.46806, 64.0215227 61.4681552, 64.0216321 61.4681552, 64.0216321 61.46806, 64.021725 61.46806, 64.021725 61.4680058, 64.021635 61.4680058, 64.021635 61.4680208, 64.0215237 61.4680208, 64.0215237 61.4680058, 64.0214238 61.4680058, 64.0214238 61.46806, 64.0215227 61.46806))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon23() throws Exception {
    String wkt ="POLYGON((-123.7404617 58.3125, -123.75 58.3125, -123.75 58.375, -123.6321531 58.3749956, -123.6317004 58.3749059, -123.6314612 58.3741376, -123.6306331 58.373089, -123.6296881 58.3723157, -123.627312 58.3710664, -123.625641 58.3692493, -123.625 58.3687661, -123.625 58.3633125, -123.6283038 58.3624226, -123.6296466 58.362358, -123.6306625 58.3621921, -123.6314938 58.3618889, -123.6330286 58.3616731, -123.634273 58.3611626, -123.6349202 58.3609982, -123.6361556 58.360838, -123.6379868 58.3597587, -123.6389829 58.3594443, -123.640572 58.3586312, -123.6421679 58.3572329, -123.6423102 58.3568794, -123.6429936 58.3565215, -123.6447649 58.3562455, -123.6460215 58.3558545, -123.6483288 58.3554625, -123.6488064 58.3551774, -123.6493181 58.3550985, -123.6509318 58.3551592, -123.6521902 58.355003, -123.6527222 58.3550521, -123.6538012 58.355484, -123.6565104 58.3556346, -123.6576767 58.3553995, -123.658255 58.3554777, -123.6590797 58.3554215, -123.661566 58.3547586, -123.6622838 58.3542689, -123.6639835 58.3543382, -123.6664585 58.3541285, -123.667106 58.3539433, -123.6678853 58.3534994, -123.6687755 58.3533241, -123.6690952 58.353079, -123.6702918 58.3525596, -123.6717506 58.3522191, -123.6758233 58.3523909, -123.6775504 58.3526168, -123.6778731 58.3525654, -123.6794879 58.3529018, -123.6800906 58.352943, -123.6808703 58.3527957, -123.6823335 58.3532423, -123.6843889 58.3531901, -123.6856506 58.3528894, -123.6862467 58.352881, -123.6872887 58.3522574, -123.687291 58.351837, -123.6869332 58.3510681, -123.6854944 58.3496119, -123.6855283 58.3485283, -123.6857475 58.3482165, -123.6874383 58.3476631, -123.6881526 58.347297, -123.6891555 58.3469904, -123.6918469 58.3458955, -123.6922003 58.3455393, -123.6924054 58.345487, -123.6924623 58.3454009, -123.6921451 58.3452257, -123.6923479 58.3449385, -123.6929675 58.3445964, -123.6931148 58.3443336, -123.6929389 58.3402113, -123.6931606 58.3394585, -123.6935341 58.3389129, -123.6939308 58.3387094, -123.6945457 58.3378975, -123.6972661 58.3371942, -123.6978071 58.3368515, -123.698247 58.3361456, -123.6993662 58.335543, -123.6997906 58.3351583, -123.7002932 58.3351122, -123.7021613 58.3346463, -123.7030156 58.3343057, -123.7047178 58.3342302, -123.7065843 58.3338261, -123.7089787 58.3336356, -123.7102074 58.3333633, -123.7107549 58.333408, -123.7110472 58.3333027, -123.7133154 58.3331443, -123.7153485 58.3323084, -123.7161434 58.331143, -123.715938 58.3302021, -123.7153031 58.3295345, -123.7145757 58.3291466, -123.7131432 58.3287541, -123.71271 58.3281785, -123.7127057 58.328026, -123.7130922 58.3279172, -123.7137255 58.3279707, -123.7137126 58.3278512, -123.7130951 58.3274557, -123.7133263 58.3266082, -123.7129943 58.3263959, -123.7132633 58.3259484, -123.7135818 58.3257238, -123.7151388 58.3251321, -123.716882 58.3249537, -123.717405 58.3250354, -123.7176916 58.3251773, -123.7198942 58.3251172, -123.7224908 58.3246186, -123.7251722 58.323832, -123.7262131 58.3231875, -123.7263272 58.3229945, -123.7262397 58.3227096, -123.7265877 58.3222214, -123.7268646 58.3220995, -123.7274534 58.3220414, -123.7280048 58.3215627, -123.7287641 58.3205496, -123.7296068 58.3189724, -123.7301585 58.3184731, -123.7322935 58.3175799, -123.7340084 58.3172445, -123.7346599 58.3168323, -123.7357182 58.3164392, -123.7366318 58.315868, -123.7370013 58.3158043, -123.7378098 58.3153726, -123.7380588 58.3150939, -123.738132 58.3146245, -123.737104 58.3136785, -123.7371457 58.3132172, -123.7377165 58.3129076, -123.7381332 58.3128319, -123.7396672 58.3128703, -123.7404617 58.3125)," +
        " (-123.7169112 58.3253866, -123.7163295 58.3254736, -123.7157654 58.325812, -123.7158944 58.327008, -123.7161972 58.3267874, -123.7164083 58.3261293, -123.7169112 58.3253866)," +
        " (-123.7153958 58.3262135, -123.7152468 58.3262208, -123.7149697 58.3266806, -123.7148026 58.3274708, -123.7152792 58.3278612, -123.7155639 58.3274097, -123.7153958 58.3262135), (-123.7497313 58.350133, -123.7498506 58.3502042, -123.75 58.3502944, -123.7494451 58.3503224, -123.7490112 58.3500917, -123.7497313 58.350133))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon24() throws Exception {
    String wkt ="POLYGON((130.67658 33.4549747, 130.6766161 33.454976, 130.6766609 33.4549775, 130.6766642 33.454912, 130.6766212 33.4549105, 130.6766102 33.4549066, 130.6766061 33.454879, 130.6765768 33.4548779, 130.6765765 33.4548831," +
        " 130.6765691 33.4548828, 130.6765693 33.4548793, 130.6765507 33.4548786, 130.6765509 33.4548761, 130.6765281 33.4548753, 130.6765273 33.4548919, 130.6765322 33.454892, 130.6765315 33.4549065, 130.6765323 33.4549065," +
        " 130.6765321 33.4549107, 130.6765257 33.4549105, 130.6765238 33.454949, 130.6765515 33.45495, 130.6765512 33.4549572, 130.6765808 33.4549583, 130.67658 33.4549747)," +
        " (130.6765844 33.4549234, 130.6765847 33.4549188, 130.6765847 33.4549188, 130.6765844 33.4549234))";
    Polygon polygon = (Polygon)SimpleWKTShapeParser.parse(wkt);
    expectThrows( IllegalArgumentException.class, () -> {Tessellator.tessellate(polygon); });
  }

  public void testComplexPolygon25() throws Exception {
    String wkt ="POLYGON((33.3275991 -8.9353026, 33.3276122 -8.9353021, 33.3276139 -8.9353425, 33.3276095 -8.9353427, 33.3276107 -8.9353706, 33.3276074 -8.9353707, 33.3276087 -8.9354024, 33.3275766 -8.9354038, 33.3275753 -8.9353739," +
        " 33.3275354 -8.9353756, 33.3275342 -8.9353464, 33.3275184 -8.935347, 33.3275167 -8.9353066, 33.3275381 -8.9353057, 33.3275375 -8.9352901, 33.3275598 -8.9352892, 33.3275594 -8.9352808, 33.3275981 -8.9352792, 33.3275991 -8.9353026)," +
        " (33.3275601 -8.9353046, 33.3275599 -8.9352988, 33.3275601 -8.9353046, 33.3275601 -8.9353046))";
    Polygon polygon = (Polygon)SimpleWKTShapeParser.parse(wkt);
    expectThrows( IllegalArgumentException.class, () -> {Tessellator.tessellate(polygon); });
  }

  public void testComplexPolygon26()  throws Exception {
    String wkt = "MULTIPOLYGON(((6.9731246 51.6251295,6.9730244 51.6251554,6.9729251 51.6251578,6.9728319 51.6251448,6.9727549 51.6251233,6.9727002 51.625087,6.9726832 51.6250387,6.9727017 51.6250038,6.9734774 51.6243338,6.973492 51.6243185," +
        "6.9735143 51.6243071,6.9735575 51.6242956,6.9736068 51.6243037,6.9738517 51.6244209,6.9739079 51.624452,6.9739256 51.6244816,6.9739272 51.624506,6.973911 51.6245399,6.973646 51.6247551,6.973586 51.6248025,6.973519 51.6248398,6.9734435 51.6248852," +
        "6.973388 51.6249344,6.9733141 51.6250411,6.9732586 51.6250913,6.9731893 51.6251238,6.9731246 51.6251295)," +
        "(6.9731928 51.6247753,6.9731161 51.624802,6.9729805 51.6248665,6.9729205 51.6249144,6.9728943 51.6249694,6.9729074 51.6250196,6.9729436 51.625064," +
        "6.9730029 51.6251047,6.9730799 51.6251272,6.9731246 51.6251295,6.9732016 51.6250865,6.973244 51.6250286,6.9732763 51.6249588,6.9732886 51.6248842,6.9732963 51.6248216,6.9732917 51.6248096,6.9732817 51.6248345,6.9732748 51.6248995,6.9732455 51.6249368," +
        "6.9731762 51.6249789,6.9731576 51.6249947,6.9731693 51.6248976,6.97319 51.6247819,6.9731928 51.6247753)," +
        "(6.9731928 51.6247753,6.9732363 51.6247413,6.9733118 51.6246748,6.9733795 51.6246404,6.9734519 51.6245992,6.9735097 51.6245538,6.9734874 51.6245404,6.9734573 51.6245127,6.9734581 51.6244907,6.9734774 51.6244543,6.9735344 51.6243931,6.9735236 51.6243946," +
        "6.9734943 51.6244161,6.9734504 51.6244543,6.9733811 51.6245275,6.9732987 51.6246064,6.9732586 51.6246518,6.9732162 51.6247183,6.9731928 51.6247753)," +
        "(6.9735097 51.6245538,6.9736199 51.624605,6.9736853 51.6246203,6.9737516 51.6246231,6.9738024 51.6246107,6.9738324 51.6245878,6.9738425 51.6245509,6.9738332 51.6245122,6.9738039 51.6244869,6.9737616 51.6244687,6.9737061 51.6244625,6.9736445 51.6244749,6.9735736 51.6245046,6.9735097 51.6245538))," +
        "((6.9731576 51.6249947,6.9731361 51.6250664,6.9731161 51.6251037,6.9731022 51.6250803,6.9731277 51.62502,6.9731576 51.6249947)))";
    Polygon[] polygons = (Polygon[])SimpleWKTShapeParser.parse(wkt);
    for (Polygon polygon : polygons) {
      List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
      assertTrue(tessellation.size() > 0);
    }
  }

  public void testComplexPolygon27() throws Exception {
    String wkt ="POLYGON((-81.9197777 32.1606889, -81.9208459 32.1614027, -81.9218128 32.1625683, -81.9217233 32.1641908, -81.9206653 32.1644687, -81.9199227 32.1644768, -81.919507 32.1652893, -81.9194166 32.1668237, -81.9196435 32.1682649, " +
        "-81.9197542 32.1687152, -81.9193309 32.1688085, -81.9189093 32.1690825, -81.9180624 32.1692691, -81.9166876 32.16973, -81.9166906 32.1700009, -81.9200053 32.1725022, -81.9205426 32.1731301, -81.920549 32.1737617, " +
        "-81.9178035 32.1750446, -81.9170662 32.1755912, -81.9155919 32.1766844, -81.9143178 32.1766031, -81.914088 32.1748909, -81.9137658 32.1745325, -81.9111045 32.1736493, -81.9100176 32.1711314, -81.9094835 32.1707767, " +
        "-81.9079966 32.1706066, -81.9046131 32.1718045, -81.9037545 32.1708181, -81.9050084 32.1689149, -81.9052123 32.1681017, -81.9051941 32.1652, -81.9029677 32.1652419, -81.8968028 32.1653673, -81.8951044 32.1652887, " +
        "-81.8948798 32.1640275, -81.8956041 32.1622183, -81.8959115 32.1611335, -81.8975012 32.1609418, -81.8979156 32.1599466, -81.898968 32.1591269, -81.8989561 32.1579545, -81.8957748 32.1580697, -81.8962963 32.1571635, " +
        "-81.8964984 32.1561697, -81.89649 32.155358, -81.8968019 32.1547247, -81.8975401 32.154268, -81.900716 32.1536142, -81.9014396 32.1517146, -81.9047425 32.1531344, -81.9072972 32.1540158, -81.9072132 32.1561818, " +
        "-81.9082779 32.156535, -81.9097676 32.156975, -81.9103042 32.1576029, -81.9105275 32.1586835, -81.911802 32.1588551, -81.9126231 32.1561425, -81.9122938 32.1550627, -81.9119664 32.1541629, -81.9126021 32.1540681, " +
        "-81.9137678 32.1539695, -81.9154642 32.1538671, -81.9159939 32.1537731, -81.9183302 32.1540263, -81.9189767 32.1550118, -81.9191927 32.155371, -81.9196179 32.1554583, -81.9198383 32.1562684, -81.9211357 32.1586041, " +
        "-81.9249461 32.1577645, -81.9255824 32.1577599, -81.9256923 32.1581198, -81.9264468 32.1592869, -81.9246484 32.1597514, -81.9243348 32.1602047, -81.9207271 32.1601408, -81.9197777 32.1606889), " +
        "(-81.9197777 32.1606889, -81.9176617 32.1612454, -81.9161794 32.1615269, -81.9158703 32.1624312, -81.9156776 32.164327, -81.9154878 32.1664932, -81.9170807 32.1666603, -81.9172827 32.1656687, -81.9174819 32.1644039, -81.9192724 32.1631284, -81.9197777 32.1606889), " +
        "(-81.9023354 32.1563966, -81.902532 32.1548643, -81.9034866 32.1548548, -81.9042322 32.1551206, -81.9044708 32.1577348, -81.9057444 32.1578156, -81.9062758 32.1579022, -81.9067039 32.1582599, -81.9070442 32.1604224, -81.9101224 32.1605786, -81.9104441 32.160937, " +
        "-81.910352 32.1622913, -81.9090818 32.1625707, -81.9057958 32.1628676, -81.9032505 32.1629757, -81.9031317 32.1617138, -81.901008 32.1615485, -81.9013139 32.160283, -81.9025866 32.1602741, -81.902572 32.1588308, -81.9023354 32.1563966))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon28() throws Exception {
    String wkt ="POLYGON((-68.206957 49.5, -68.2084578 49.5, -68.209709 49.5, -68.2095384 49.4994267, -68.209625 49.4992348, -68.210007 49.4989218, -68.210023 49.4987883, -68.2096826 49.4986001, -68.2094519 49.4983847, " +
        "-68.2093766 49.4982739, -68.2093156 49.4980982, -68.2093356 49.498025, -68.2093107 49.4979289, -68.2092162 49.4977138, -68.2092657 49.4973334, -68.2092317 49.4970964, -68.2089469 49.4967172, -68.2088447 49.4966676, " +
        "-68.2083464 49.4969072, -68.2082338 49.4969829, -68.2081498 49.4972151, -68.2081795 49.4974804, -68.2081717 49.4976459, -68.2080004 49.4979611, -68.2077763 49.4981327, -68.2073525 49.4983742, -68.2071536 49.4985531, " +
        "-68.2070131 49.4985812, -68.2067493 49.498524, -68.2064765 49.4986121, -68.2064173 49.4986541, -68.206208 49.4989583, -68.2061419 49.4989883, -68.2057963 49.4990059, -68.2056593 49.4991831, -68.2055727 49.499375, " +
        "-68.2055949 49.4994309, -68.2056537 49.4994776, -68.2059649 49.4995981, -68.2060542 49.4997327, -68.206666 49.5, -68.206775 49.5, -68.206957 49.5), (-68.206957 49.5, -68.2068746 49.4999721, -68.2069691 49.499901, " +
        "-68.2072345 49.4998896, -68.2073016 49.4999684, -68.2072524 49.4999738, -68.2072032 49.4999792, -68.206957 49.5), " +
        "(-68.2071295 49.4995135, -68.2071026 49.4995747, -68.206831 49.499683, -68.2065151 49.4996796, -68.2064171 49.4996017, -68.2064693 49.4995478, -68.2067 49.4994769, -68.2068784 49.4994599, -68.207103 49.499486, -68.2071295 49.4995135))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon29() throws Exception {
    String wkt ="POLYGON((-81.36913 28.589541, -81.369566 28.589542, -81.372775 28.589552, -81.373184 28.589553, -81.373245 28.589608, -81.3732717 28.591233, -81.373274 28.591373, -81.3732974 28.5930032, " +
        "-81.3732474 28.5930567, -81.370891 28.593039, -81.370844 28.593039, -81.370841 28.593038, -81.370801 28.593038, -81.370798 28.593037, -81.370628 28.593033, -81.370321 28.593017, -81.3698235 28.5929986, " +
        "-81.3691812 28.592994, -81.3691723 28.5924913, -81.3691603 28.5918073, -81.3696538 28.5918014, -81.3696565 28.5916848, -81.3696484 28.5915517, -81.3696001 28.5912644, -81.3695827 28.5911137, " +
        "-81.3691482 28.5911149, -81.3691442 28.5904248, -81.36913 28.589541), (-81.3717082 28.5913906, -81.3717104 28.5915295, -81.3712894 28.5915295, -81.3712866 28.5913906, -81.3717082 28.5913906), " +
        "(-81.37226 28.591612, -81.371836 28.59161, -81.371841 28.591884, -81.3722601 28.5918808, -81.37226 28.591612), " +
        "(-81.372258 28.591474, -81.3726774 28.5914737, -81.3726754 28.5916118, -81.37226 28.591612, -81.372258 28.591474), " +
        "(-81.3722683 28.592167, -81.3718455 28.5921684, -81.371852 28.592584, -81.372276 28.592585, -81.3722683 28.592167))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon30() throws Exception {
    String wkt ="POLYGON((-118.1288162 34.1527018, -118.1288162 34.1526725, -118.1288002 34.1526725, -118.1288001 34.1526511, -118.1287859 34.1526382, -118.1287859 34.1526293, -118.1288001 34.1526218, -118.1288 34.1525913, -118.1288093 34.1525912, -118.1288093 34.1525831, " +
        "-118.1288 34.1525831, -118.1288 34.1525544, -118.1287852 34.1525469, -118.1287852 34.1525375, -118.1287999 34.1525259, -118.1287999 34.1524997, -118.1288091 34.1524997, -118.1288091 34.1524966, -118.1288479 34.1524965, -118.1288479 34.1524996, " +
        "-118.1288701 34.1524996, -118.1288701 34.1524965, -118.1289107 34.1524965, -118.1289107 34.1524996, -118.1289174 34.1524996, -118.1289175 34.1525129, -118.1289384 34.1525128, -118.1289384 34.1524995, -118.1289654 34.1524995, -118.1289654 34.1524964, " +
        "-118.1290406 34.1524963, -118.1290406 34.1524994, -118.1290858 34.1524994, -118.1290875 34.1524901, -118.129108 34.1524901, -118.1291127 34.1524993, -118.1292449 34.1524992, -118.1292498 34.1525125, -118.1292498 34.1525084, -118.1292726 34.1525084, -118.1292727 34.1525621, " +
        "-118.1292992 34.1525621, -118.1292992 34.1526061, -118.1292727 34.1526061, -118.1292727 34.1525693, -118.1292499 34.1525693, -118.1292499 34.1525805, -118.1292678 34.1525805, -118.1292678 34.1526087, -118.129306 34.1526086, -118.129306 34.1526111, -118.1293085 34.1526111, " +
        "-118.1293087 34.1527887, -118.1292798 34.1527888, -118.1292798 34.1527862, -118.1292703 34.1527862, -118.1292689 34.1527898, -118.1292578 34.1527972, -118.1292472 34.1527963, -118.1292378 34.1527863, -118.129209 34.1527863, -118.129209 34.1527898, -118.1291961 34.1527898, " +
        "-118.1291961 34.1527863, -118.1291611 34.1527863, -118.1291566 34.1527966, -118.1291403 34.1527965, -118.1291313 34.1527864, -118.1290711 34.1527864, -118.1290743 34.1527922, -118.1290617 34.1527983, -118.1290498 34.152793, -118.1290521 34.1527864, -118.1290078 34.1527865, " +
        "-118.1290077 34.1527804, -118.1289997 34.1527804, -118.1289997 34.1527891, -118.1289639 34.1527891, -118.1289573 34.1527994, -118.1289431 34.1527993, -118.1289356 34.1527891, -118.1288754 34.1527892, -118.1288754 34.1527941, -118.1288666 34.1527999, -118.1288552 34.1527999, " +
        "-118.1288478 34.1527939, -118.1288478 34.1527892, -118.1288004 34.1527893, -118.1288002 34.1527018, -118.1288162 34.1527018), (-118.1289329 34.1525558, -118.1289331 34.1526612, -118.1289386 34.1526786, -118.1289386 34.1526208, -118.1289484 34.1526208, -118.1289484 34.1525972, " +
        "-118.1289385 34.1525972, -118.1289385 34.1525558, -118.1289329 34.1525558), " +
        "(-118.1289577 34.1526842, -118.1289867 34.1526842, -118.1289867 34.1526898, -118.129055 34.1526897, -118.129055 34.1526596, -118.1290352 34.1526596, -118.1290353 34.1526785, -118.1289386 34.1526786, -118.1289577 34.1526842), (-118.1292235 34.1525908, -118.1292235 34.1525969, -118.129218 34.1525969, -118.129218 34.1526087, -118.1292278 34.1526087, -118.1292278 34.1525908, -118.1292235 34.1525908), " +
        "(-118.1290728 34.1526595, -118.1290728 34.1526508, -118.1290679 34.1526508, -118.1290679 34.1526595, -118.1290728 34.1526595), (-118.1291115 34.1526447, -118.1291546 34.1526446, -118.1291547 34.1526753, -118.1291664 34.1526753, -118.1291663 34.1526113, -118.1291626 34.1526062, -118.1290881 34.1526063, -118.1290795 34.1526114, -118.1290795 34.1526508, -118.1291116 34.1526508, -118.1291115 34.1526447), " +
        "(-118.1290678 34.1525971, -118.1290881 34.1525971, -118.1290794 34.1525879, -118.1290124 34.152588, -118.1290124 34.1526064, -118.1290678 34.1526063, -118.1290678 34.1525971), (-118.1288586 34.1526756, -118.1288586 34.1526787, -118.1288937 34.1526786, -118.128906 34.1526756, -118.1288586 34.1526756), (-118.1291835 34.1526087, -118.1291835 34.1526277, -118.1292088 34.1526277, -118.1292087 34.1526087, -118.1291835 34.1526087), " +
        "(-118.1291861 34.152686, -118.1292181 34.152686, -118.1292181 34.1526824, -118.1291861 34.1526824, -118.1291861 34.152686))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon31() throws Exception {
    String wkt ="POLYGON((33.2851247 64.3962413, 33.2853164 64.3964752, 33.2855082 64.396563, 33.2858465 64.3965825, 33.2861736 64.3964899, " +
        "33.2865571 64.396329, 33.286997 64.3961633, 33.2872677 64.396251, 33.2873466 64.3962072, 33.2870534 64.395905, 33.2866361 64.3956807, 33.2861511 64.3955638, " +
        "33.2856435 64.3956174, 33.2852826 64.3957149, 33.2851247 64.3958562, 33.2851247 64.396134, 33.2851247 64.3962413), " +
        "(33.2851247 64.396134, 33.2854405 64.3962023, 33.2860157 64.3958172, 33.2858578 64.3956807, 33.2853164 64.3958221, 33.2851247 64.396134), " +
        "(33.2857563 64.3963875, 33.2859932 64.396446, 33.2861736 64.3963534, 33.2859706 64.3962851, 33.2857225 64.3963095, 33.2857563 64.3963875))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon32() throws Exception {
    String wkt ="POLYGON((-94.1396281 47.8427276, -94.1394597 47.8318694, -94.1401176 47.8173121, -94.1395648 47.8062658, -94.1343888 47.8063357, -94.1346412 47.8136767, -94.1293684 47.8137221, -94.1292883 47.8100637, -94.1241003 47.8101206, -94.1240711 47.8028274, -94.1018162 47.8025521, " +
        "-94.1016856 47.7989284, -94.0962427 47.7990633, -94.0958641 47.7919119, -94.090393 47.7919809, -94.0901788 47.7883992, -94.0956694 47.7883497, -94.0953154 47.7736816, -94.1009001 47.773599, -94.1007919 47.7773656, -94.1011601 47.7882999, -94.1224262 47.7882635, " +
        "-94.1278201 47.7882045, -94.128157 47.791947, -94.1334767 47.7919893, -94.1340009 47.7990339, -94.1391714 47.7989574, -94.1392586 47.8025871, -94.1445192 47.802501, -94.1441646 47.7952601, -94.1495363 47.7952326, -94.1498918 47.8024807, -94.1553562 47.8024703, " +
        "-94.1555675 47.806059, -94.150131 47.8061278, -94.1506011 47.8129253, -94.1501789 47.8129684, -94.149611 47.8132643, -94.1491352 47.813398, -94.1489002 47.8135939, -94.1488101 47.8138527, -94.1488665 47.8142391, -94.1483486 47.8146313, -94.1482663 47.8152448, " +
        "-94.1483213 47.8155667, -94.1490605 47.817251, -94.1497062 47.8182566, -94.1498362 47.8193197, -94.1499652 47.8195646, -94.150403 47.8213749, -94.1507045 47.821924, -94.1508205 47.8222638, -94.151727 47.8234564, -94.15213 47.8236878, -94.1524748 47.8240132, " +
        "-94.1531753 47.8251591, -94.1537606 47.8265457, -94.1541208 47.8270211, -94.1545129 47.8273013, -94.1546514 47.8275679, -94.1551127 47.8277094, -94.1552844 47.8278376, -94.1554978 47.828217, -94.1561502 47.8288194, -94.1562033 47.8290381, -94.1567283 47.8298772, " +
        "-94.1570108 47.8302438, -94.1572449 47.8303308, -94.1579044 47.8312801, -94.1588831 47.8316117, -94.1589829 47.8317057, -94.1589776 47.8319543, -94.1592481 47.8324046, -94.1601486 47.8333603, -94.1612329 47.8342848, -94.1619696 47.8351853, -94.155575 47.8352963, " +
        "-94.1556138 47.8388745, -94.144871 47.8390595, -94.144906 47.8426792, -94.1396281 47.8427276), (-94.1340009 47.7990339, -94.1288303 47.7991103, -94.1291281 47.8027466, -94.1342625 47.802665, -94.1340009 47.7990339), " +
        "(-94.1013659 47.7924644, -94.1014295 47.792468, -94.102571 47.7924213, -94.1027201 47.7923202, -94.1027617 47.7920166, -94.1026243 47.7918031, -94.1024919 47.7911957, -94.102004 47.7901082, -94.1018445 47.7888476, -94.1017758 47.7887408, -94.101548 47.7886445, " +
        "-94.1013617 47.7886284, -94.1006145 47.7891011, -94.1005105 47.7892095, -94.1004868 47.789344, -94.1007015 47.790076, -94.1011754 47.7905011, -94.1012329 47.7907064, -94.1011431 47.7908595, -94.1009054 47.7909244, -94.1007312 47.7908545, -94.1005935 47.7906231, " +
        "-94.100326 47.7905361, -94.0999407 47.7905308, -94.0998106 47.7906151, -94.1000388 47.7906356, -94.0993399 47.790923, -94.0992874 47.7910474, -94.0994397 47.7913413, -94.099697 47.7915716, -94.0997034 47.7918759, -94.0998534 47.7920624, -94.1005516 47.7924138, -94.1013659 47.7924644))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon33() throws Exception {
    String wkt ="POLYGON((110.3240182 -7.8006815, 110.3235448 -7.8007665, 110.3233914 -7.8012355, 110.323407 -7.801519, 110.3233706 -7.8015241, 110.3232692 -7.8018926, 110.3234616 -7.8021632, 110.3235813 -7.8025213, 110.3238986 -7.8026038, 110.3238569 -7.8025316, " +
        "110.3238439 -7.8021941, 110.3237321 -7.8021193, 110.323948 -7.8019802, 110.3240936 -7.8021116, 110.3244603 -7.8020137, 110.3244187 -7.80189, 110.3242991 -7.8016865, 110.3242133 -7.8016143, 110.324078 -7.8015293, 110.3239766 -7.8014803, " +
        "110.3239324 -7.8014133, 110.3239116 -7.8012458, 110.3239532 -7.8011015, 110.323987 -7.8009907, 110.3240182 -7.8006815), " +
        "(110.3235776 -7.8007793, 110.3239413 -7.800712, 110.3239467 -7.8008326, 110.3235594 -7.8008779, 110.3235776 -7.8007793), " +
        "(110.3235182 -7.8009198, 110.3239302 -7.8008615, 110.3239391 -7.8009232, 110.3235271 -7.8009815, 110.3235182 -7.8009198), " +
        "(110.3235214 -7.8010247, 110.3238373 -7.8009589, 110.3239145 -7.8014873, 110.3235664 -7.8015372, 110.3235214 -7.8010247), " +
        "(110.3235634 -7.8015783, 110.323957 -7.8015163, 110.3239758 -7.8016341, 110.324071 -7.8016183, 110.3240998 -7.8017897, 110.3240034 -7.8018056, 110.3240128 -7.8018645, 110.3236192 -7.8019264, 110.3235634 -7.8015783))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon34() throws Exception {
    String wkt ="POLYGON((16.9888793 52.3995602, 16.9888951 52.3995678, 16.9888867 52.3995718, 16.9888928 52.3995788, 16.9888945 52.3995867, 16.9888916 52.3995945, 16.9888843 52.3996012, 16.9888738 52.3996059, 16.9888612 52.3996081, 16.9888481 52.3996074, " +
        "16.9888363 52.399604, 16.9888297 52.3996096, 16.9888094 52.3996009, 16.9887881 52.3996192, 16.9888405 52.3996419, 16.9888306 52.3996504, 16.9887783 52.3996277, 16.9887349 52.3996651, 16.9887103 52.3996746, 16.9886922 52.3996886, 16.9886819 52.3997053, " +
        "16.9886804 52.3997231, 16.9886878 52.3997404, 16.9887036 52.3997556, 16.9887086 52.3997679, 16.9887085 52.3997812, 16.9887018 52.3997938, 16.9886433 52.3998479, 16.9886324 52.3998524, 16.9886238 52.3998539, 16.9886151 52.3998526, 16.9885947 52.3998431, " +
        "16.9885866 52.3998495, 16.9886312 52.3998768, 16.988671 52.3999086, 16.9887038 52.3999418, 16.988731 52.3999784, 16.988776 52.3999362, 16.9888177 52.3998971, 16.9888471 52.3999089, 16.989027 52.3997413, 16.9889856 52.3997247, 16.9890396 52.3996744, " +
        "16.9890158 52.3996649, 16.989152 52.3995378, 16.9891608 52.3995249, 16.9891652 52.3995113, 16.989165 52.3994974, 16.9891602 52.3994838, 16.9891509 52.3994711, 16.9891376 52.3994598, 16.9890972 52.3994436, 16.9890682 52.399432, 16.9890372 52.399461, " +
        "16.9890244 52.3994673, 16.9890106 52.3994709, 16.9890079 52.3994628, 16.9890341 52.3994596, 16.989023 52.3994258, 16.9889663 52.3994327, 16.9889775 52.3994666, 16.9889209 52.3994735, 16.9889323 52.3995083, 16.9888772 52.399515, 16.9888885 52.3995493, " +
        "16.9888793 52.3995602), (16.9886602 52.3998804, 16.9886764 52.3998641, 16.9887009 52.3998732, 16.9886894 52.3998847, 16.9887115 52.3999171, 16.9886996 52.3999206, 16.9886602 52.3998804), " +
        "(16.9888417 52.3998584, 16.9888054 52.3998922, 16.9887213 52.3998586, 16.9888863 52.3997049, 16.9889704 52.3997384, 16.9889688 52.3997399, 16.9889926 52.3997494, 16.98896 52.3997796, 16.9889611 52.3997801, 16.9888664 52.3998683, 16.9888417 52.3998584), " +
        "(16.9887468 52.3998164, 16.9887379 52.3998129, 16.9887336 52.3998287, 16.9887468 52.3998164), " +
        "(16.9887603 52.3998039, 16.9887794 52.3997861, 16.9887591 52.399778, 16.9887451 52.3997981, 16.9887603 52.3998039), " +
        "(16.9887792 52.3997595, 16.9887993 52.3997676, 16.9888261 52.3997426, 16.988806 52.3997346, 16.9887792 52.3997595), " +
        "(16.9888874 52.3996435, 16.9888054 52.3997199, 16.9888168 52.3997245, 16.9888989 52.3996481, 16.9888874 52.3996435), " +
        "(16.9890281 52.3996129, 16.9890181 52.3996223, 16.9889549 52.3995971, 16.9889222 52.3996275, 16.9889098 52.3996226, 16.9889526 52.3995827, 16.9890281 52.3996129), " +
        "(16.9891175 52.3994786, 16.9891045 52.3994903, 16.9890497 52.3994968, 16.9890606 52.3995313, 16.9890056 52.3995378, 16.9890164 52.399572, 16.9890715 52.3995655, 16.9890768 52.3995676, 16.9890382 52.3996035, 16.9889627 52.3995733, 16.9890804 52.3994638, 16.9891175 52.3994786), " +
        "(16.9889151 52.399546, 16.9889436 52.3995425, 16.9889323 52.3995083, 16.9889431 52.3995139, 16.98895 52.3995215, 16.9889523 52.39953, 16.9889496 52.3995385, 16.9889423 52.399546, 16.9889312 52.3995514, 16.9889178 52.3995541, 16.9889151 52.399546), " +
        "(16.9889615 52.3995047, 16.9889645 52.3995137, 16.9889783 52.3995107, 16.9889896 52.3995051, 16.9889969 52.3994973, 16.9889993 52.3994885, 16.9889966 52.3994797, 16.988989 52.3994721, 16.9889775 52.3994666, 16.988989 52.3995013, 16.9889615 52.3995047), " +
        "(16.9890664 52.3995495, 16.9890796 52.399548, 16.9890725 52.3995387, 16.9890606 52.3995313, 16.9890664 52.3995495), " +
        "(16.9890606 52.3995313, 16.9890747 52.3995357, 16.9890905 52.3995359, 16.989105 52.3995321, 16.9891154 52.3995249, 16.9890606 52.3995313), " +
        "(16.9891045 52.3994903, 16.9891101 52.399508, 16.9891232 52.3995065, 16.9891163 52.3994967, 16.9891045 52.3994903))";
    checkPolygon(wkt);
  }


  public void testComplexPolygon35() throws Exception {
    String wkt ="POLYGON((118.8359325 31.3044397, 118.8356554 31.3043398, 118.8348319 31.3044474, 118.8345171 31.3044103, 118.8344937 31.3043842, 118.8344634 31.304404, 118.8343236 31.3043875, 118.8343041 31.3045084, 118.8342481 31.304545, 118.8340683 31.3045526, 118.8340699 31.3045798, " +
        "118.8321485 31.3044289, 118.8322045 31.3037237, 118.8321291 31.3037194, 118.8324438 31.2986696, 118.8322669 31.2986616, 118.8319086 31.30441, 118.8315908 31.3043851, 118.8315781 31.3045036, 118.8235562 31.3039588, 118.8230309 31.3039895, 118.8230309 31.3042747, " +
        "118.8233192 31.3043525, 118.823316 31.3047391, 118.8231649 31.3051035, 118.8228827 31.3054057, 118.8225003 31.3056123, 118.8220598 31.3057007, 118.8219234 31.3067616, 118.8217667 31.3067548, 118.8214409 31.3122485, 118.8194315 31.3121343, 118.8197515 31.3067386, " +
        "118.8194532 31.3067257, 118.8191334 31.3121174, 118.8171023 31.3120019, 118.8174875 31.3055082, 118.8171122 31.305492, 118.8167274 31.3119806, 118.8146675 31.3118636, 118.8150559 31.3052685, 118.814709 31.3052536, 118.8143209 31.3118439, 118.8121504 31.3117205, " +
        "118.8125177 31.3048052, 118.8122628 31.3047953, 118.8118957 31.3117061, 118.8098208 31.3115881, 118.8102656 31.3040593, 118.8099024 31.3040436, 118.8097101 31.3072998, 118.8065381 31.3071481, 118.8065121 31.3073986, 118.80969 31.3076392, 118.8094579 31.3115675, " +
        "118.8051915 31.3113251, 118.8051035 31.3115159, 118.8095649 31.3117597, 118.8091148 31.3168929, 118.8092977 31.3169046, 118.8095032 31.3159679, 118.8116626 31.3160948, 118.811662 31.3161065, 118.8119169 31.3161164, 118.8119172 31.3161097, 118.8140622 31.3162357, " +
        "118.8140223 31.3169131, 118.8143692 31.316928, 118.8144088 31.3162561, 118.8188723 31.3165182, 118.8188717 31.3165282, 118.8191701 31.3165411, 118.8191704 31.3165357, 118.8211796 31.3166537, 118.8210287 31.3191976, 118.8215026 31.3192181, 118.821653 31.3166815, " +
        "118.8238584 31.3168111, 118.8238285 31.3173164, 118.824093 31.3173279, 118.8241228 31.3168266, 118.8261849 31.3169477, 118.8257633 31.3240544, 118.8260128 31.3240652, 118.8264341 31.3169624, 118.8265321 31.3169681, 118.835779 31.3175303, 118.8357304 31.3182445, " +
        "118.8353814 31.3215368, 118.8356569 31.3215581, 118.8360032 31.3182911, 118.8360673 31.3182943, 118.8361179 31.3175509, 118.8372978 31.3176226, 118.8381885 31.317677, 118.837935 31.3211482, 118.8382089 31.3211628, 118.8384623 31.3176937, 118.8406308 31.317826, " +
        "118.8403627 31.3213945, 118.8406664 31.3214112, 118.8409344 31.3178445, 118.8430721 31.3179749, 118.8427296 31.3219519, 118.843006 31.3219692, 118.8433484 31.3179918, 118.8483436 31.3182966, 118.8483631 31.3180636, 118.8433685 31.3177588, 118.8437065 31.3138324, " +
        "118.8442166 31.3138635, 118.844236 31.3136313, 118.8436388 31.3135949, 118.8437791 31.3118077, 118.8484908 31.3120354, 118.8485069 31.3117915, 118.8437983 31.3115639, 118.8439409 31.3097467, 118.8441978 31.3097636, 118.8510368 31.3100952, 118.8512996 31.3101096, " +
        "118.8514524 31.3080769, 118.8536716 31.3082122, 118.8536932 31.3079541, 118.8514718 31.3078188, 118.8515423 31.3068817, 118.8512796 31.3068673, 118.8512092 31.3078028, 118.8441274 31.3073712, 118.8442618 31.3056595, 118.8440724 31.3056487, 118.8439381 31.3073597, " +
        "118.8417545 31.3072267, 118.8418247 31.3063658, 118.8415386 31.3063487, 118.8414684 31.3072092, 118.8393169 31.3070781, 118.8394421 31.3052826, 118.8390997 31.3052652, 118.8389748 31.3070573, 118.8368497 31.3069278, 118.8370281 31.3051513, 118.8398637 31.3052816, " +
        "118.8398793 31.3050328, 118.836886 31.3048953, 118.8369569 31.3039477, 118.8369571 31.3039469, 118.8367845 31.3039157, 118.8365534 31.3048517, 118.8362758 31.3048155, 118.8359325 31.3044397), (118.8318849 31.3047901, 118.8318807 31.3048586, 118.8319069 31.3048598, " +
        "118.8312737 31.3128253, 118.8266978 31.3125182, 118.8268176 31.3104976, 118.8268263 31.310498, 118.8272321 31.3044742, 118.8318849 31.3047901), " +
        "(118.8265321 31.3169681, 118.8265485 31.3167642, 118.8264462 31.3167582, 118.8266792 31.312831, 118.831441 31.3131505, 118.836054 31.3134868, 118.8357929 31.3173262, 118.8265491 31.3167643, 118.8265321 31.3169681), " +
        "(118.8340906 31.3049399, 118.8344671 31.3049241, 118.8347889 31.3047133, 118.8357009 31.3045941, 118.8360442 31.3049699, 118.8367176 31.3050578, 118.8365317 31.3069084,118.832709 31.3066755, 118.8326972 31.3068173, 118.8339339 31.3069288, 118.8346211 31.3070514,118.8354145 31.3072038," +
        "118.8363587 31.3070847, 118.836467 31.3071638, 118.8365058 31.3071662, 118.8363372 31.308844, 118.8323175 31.3088821, 118.83232 31.3090801, 118.8363173 31.3090423, 118.8361165 31.3110409, 118.8316981 31.310786, 118.8316769 31.3110546, 118.8362279 31.3113171, 118.8360822 31.3131156, 118.8314845 31.3127805, 118.8321185 31.304806, 118.8340906 31.3049399), " +
        "(118.8367177 31.305057, 118.8368751 31.305069, 118.836875 31.3050693, 118.8367176 31.3050578, 118.8367177 31.305057), " +
        "(118.8412471 31.3136823, 118.8434302 31.3138155, 118.8430921 31.3177419, 118.8409519 31.3176113, 118.8412471 31.3136823)," +
        "(118.8439564 31.3095503, 118.8441072 31.3076294, 118.8511898 31.3080609, 118.8510368 31.3100952, 118.8510541 31.3098339, 118.8442152 31.3095023, 118.8442109 31.309567, 118.8439564 31.3095503)," +
        "(118.8363927 31.3135115, 118.8387552 31.3136837, 118.8384812 31.3136691, 118.8382056 31.3174437, 118.8373172 31.3173895, 118.8372978 31.3176226, 118.8373147 31.3174187, 118.8361318 31.3173468, 118.8363927 31.3135115), " +
        "(118.8387552 31.3136837, 118.8387704 31.3135311, 118.8409435 31.3136638, 118.8406483 31.3175928, 118.8384793 31.3174605, 118.8387552 31.3136837), " +
        "(118.8364943 31.3113325, 118.8386681 31.3114579, 118.8385401 31.3132947, 118.8363482 31.313135, 118.8364943 31.3113325)," +
        "(118.8386869 31.3111891, 118.836516 31.3110639, 118.8365238 31.3109687, 118.8364442 31.310964, 118.8366148 31.3092652, 118.8388109 31.3094095, 118.8386869 31.3111891), " +
        "(118.8412918 31.3093751, 118.8391666 31.3092355, 118.8392989 31.3073364, 118.8414474 31.3074673, 118.8412918 31.3093751), " +
        "(118.8415778 31.3093939, 118.8417335 31.3074847, 118.8439178 31.3076178, 118.8437671 31.3095378, 118.8415778 31.3093939), " +
        "(118.8414126 31.3114199, 118.8415618 31.3095903, 118.8437517 31.3097342, 118.8436078 31.3115676, 118.8414126 31.3114199)," +
        "(118.8434495 31.3135834, 118.8412472 31.313449, 118.8413941 31.3116476, 118.8435899 31.3117954, 118.8434495 31.3135834), " +
        "(118.8411267 31.3114006, 118.8395641 31.3112954, 118.8395623 31.3113159, 118.8390244 31.3112748, 118.8391529 31.309432, 118.8412758 31.3095715, 118.8411267 31.3114006), " +
        "(118.8388246 31.309213, 118.8366345 31.3090691, 118.8368238 31.3071856, 118.8389568 31.3073156, 118.8388246 31.309213), " +
        "(118.838883 31.3133047, 118.83899 31.3117697, 118.8396426 31.3118194, 118.8396727 31.3115317, 118.8411081 31.3116283, 118.8409611 31.3134315, 118.838883 31.3133047), " +
        "(118.8243753 31.3125689, 118.8262393 31.3126708, 118.8264312 31.3127962, 118.826197 31.3167436, 118.8241349 31.3166225, 118.8243753 31.3125689), " +
        "(118.8118861 31.3118865, 118.8116734 31.3158906, 118.8095561 31.3157662, 118.8095278 31.3142803, 118.809748 31.3117697, 118.8118861 31.3118865), " +
        "(118.8219144 31.3122754, 118.8222406 31.3067753, 118.8223178 31.305947, 118.8227426 31.3058563, 118.8231167 31.3055875, 118.8233926 31.3052427, 118.8235499 31.3048473, 118.8235771 31.3044303, 118.8235316 31.3042228, 118.8246008 31.3042955, 118.8241201 31.3124007, 118.8219144 31.3122754), " +
        "(118.8143105 31.312019, 118.8140742 31.3160316, 118.8119281 31.3159055, 118.8121408 31.3119004, 118.8143105 31.312019), (118.8168536 31.3161948, 118.8170923 31.312171, 118.8191236 31.312282, 118.8188844 31.3163141, 118.8168536 31.3161948), " +
        "(118.8263576 31.3124658, 118.8256293 31.3122973, 118.8252652 31.3124658, 118.8243844 31.3124158, 118.824865 31.3043134, 118.8269744 31.3044567, 118.8265682 31.3104853, 118.8264468 31.3125321, 118.8263576 31.3124658), " +
        "(118.8211917 31.3164496, 118.8191825 31.3163316, 118.8194218 31.3122983, 118.8214314 31.3124081, 118.8211917 31.3164496), " +
        "(118.8144208 31.3160519, 118.8146572 31.3120379, 118.8167173 31.3121505, 118.8164787 31.3161728, 118.8144208 31.3160519), " +
        "(118.821905 31.312434, 118.8241109 31.3125545, 118.8238706 31.3166069, 118.8216651 31.3164774, 118.821905 31.312434))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon36() throws Exception {
    String wkt ="POLYGON((31.5432386 40.5444846, 31.5428333 40.5447783, 31.5430418 40.5451573, 31.5432774 40.5458431, 31.5431345 40.5461992, 31.5427443 40.5468028, 31.5427293 40.5468683, 31.5427698 40.5471044, 31.54283 40.5473436, 31.5430011 40.5475888, " +
        "31.5429981 40.5476338, 31.5427795 40.5477506, 31.5431954 40.5481283, 31.5436282 40.548149, 31.543919 40.5484179, 31.5442586 40.5485314, 31.5442822 40.5484902, 31.5445155 40.5485406, 31.5448742 40.5487706, 31.5412238 40.5521027, 31.5400475 40.5530066, " +
        "31.5349761 40.5510675, 31.530855 40.5490397, 31.5310524 40.5485952, 31.5314166 40.5480415, 31.5300249 40.5454272, 31.5301413 40.5447536, 31.5312361 40.5410823, 31.529328 40.5360959, 31.5300358 40.5360506, 31.5307307 40.5359733, 31.5306022 40.535728, " +
        "31.5306898 40.5357188, 31.5308605 40.5360324, 31.5315976 40.5356632, 31.5321057 40.5360186, 31.5322743 40.5364639, 31.5322077 40.536602, 31.5327667 40.5372757, 31.5333512 40.5372369, 31.5335205 40.5367053, 31.5343248 40.5368691, 31.5350711 40.5371246, " +
        "31.5348027 40.5376999, 31.5355428 40.5377723, 31.5361926 40.5378068, 31.5368964 40.53822, 31.5374149 40.5388121, 31.5379622 40.5392757, 31.5386165 40.5398509, 31.5391947 40.5401287, 31.5395102 40.5403617, 31.5396454 40.5405819, 31.5396771 40.540956, " +
        "31.5400588 40.5412507, 31.540127 40.541369, 31.5399063 40.5413579, 31.5397812 40.5419516, 31.5400226 40.5418548, 31.5400302 40.5418816, 31.5397734 40.5420002, 31.5397234 40.5423203, 31.5399911 40.5421976, 31.5403034 40.542339, 31.5409027 40.5429551, " +
        "31.5417321 40.5433709, 31.542426 40.5437638, 31.5428528 40.5442692, 31.5432386 40.5444846), (31.5412238 40.5521027, 31.5406937 40.5520915, 31.5402685 40.5521744, 31.5403206 40.5524837, 31.5405968 40.5523547, 31.5412238 40.5521027), " +
        "(31.5400475 40.5530066, 31.5400904 40.5526181, 31.5399647 40.552562, 31.5398491 40.5528512, 31.5400475 40.5530066), " +
        "(31.5409996 40.5496883, 31.5406703 40.5496437, 31.540137 40.549897, 31.5393764 40.5497885, 31.5393464 40.5501246, 31.5399187 40.5502324, 31.5405251 40.5501602, 31.5409996 40.5496883), " +
        "(31.5393617 40.5490587, 31.5393516 40.5488143, 31.5391465 40.5489137, 31.5391566 40.5491582, 31.5393617 40.5490587), " +
        "(31.5409254 40.5443719, 31.5407571 40.54419, 31.5407255 40.5438239, 31.5401325 40.5438579, 31.5399032 40.5439566, 31.5398296 40.5441184, 31.5393995 40.5445676, 31.5389124 40.5446421, 31.5387512 40.54494, 31.5383869 40.5453713, 31.5386127 40.5456853, " +
        "31.5392235 40.5453415, 31.5392131 40.5455667, 31.5392264 40.5456182, 31.5391974 40.546022, 31.5397349 40.5459706, 31.5399777 40.545728, 31.5402482 40.5454367, 31.5405182 40.5451789, 31.540689 40.5447674, 31.5409254 40.5443719), " +
        "(31.5379966 40.5463885, 31.5377894 40.5456116, 31.5376279 40.5456641, 31.537648 40.5463993, 31.5378796 40.5467303, 31.5379966 40.5463885), " +
        "(31.5378556 40.5516982, 31.5370605 40.5513965, 31.5369507 40.5516329, 31.5377436 40.551998, 31.5378556 40.5516982), " +
        "(31.5373231 40.5487845, 31.5372871 40.547977, 31.5367298 40.5483529, 31.5366771 40.5486289, 31.5373231 40.5487845), " +
        "(31.536937 40.5495577, 31.5366547 40.5493848, 31.5364985 40.5495603, 31.5366721 40.5497374, 31.536937 40.5495577), " +
        "(31.5376342 40.5471325, 31.5373396 40.5467958, 31.536765 40.547373, 31.5358182 40.5479584, 31.5360419 40.5481495, 31.5364173 40.5478667, 31.5367077 40.5479675, 31.5376342 40.5471325), " +
        "(31.5359169 40.5475959, 31.5357927 40.5474265, 31.5350828 40.5479457, 31.535207 40.5481151, 31.5359169 40.5475959), " +
        "(31.5369515 40.5453629, 31.53672 40.5450847, 31.5365133 40.5450307, 31.53618 40.5452052, 31.5353734 40.5451948, 31.5347556 40.5458435, 31.5356215 40.5459459, 31.5364346 40.5462813, 31.5367607 40.5460925, 31.5358931 40.5455262, 31.5361393 40.5453977, 31.5366303 40.5455835, 31.5367923 40.5454808, 31.5369515 40.5453629), " +
        "(31.5357976 40.5418655, 31.5352819 40.5415257, 31.534827 40.5421415, 31.5357976 40.5418655), " +
        "(31.5352717 40.5501041, 31.5346075 40.5500969, 31.53453 40.5502005, 31.5351532 40.5502695, 31.5352717 40.5501041), " +
        "(31.5343455 40.5448048, 31.5339916 40.544821, 31.533926 40.5452323, 31.5342813 40.5452432, 31.5343455 40.5448048))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon37() throws Exception {
    String wkt ="POLYGON ((0.655085104926744 44.1423449911154,0.662410270135664 44.1383837911746,0.663029824228426 44.1383005360528,0.666194929686351 44.1376998068095,0.665852086395847 44.1363576761449,0.665825350681267 44.1363519832388,0.665797803048059 44.1362972434215,0.664592469165541 44.1357012764041,0.661253118837805 44.1364200434166,0.655085104926744 44.1423449911154)," +
        "(0.665828005870389 44.1363561368379,0.665833229243683 44.1363674767066,0.665825350681267 44.1363519832388,0.665828005870389 44.1363561368379))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon38() throws Exception {
    String wkt ="POLYGON((-80.1124643 40.8042035, -80.1124675 40.8044718, -80.1124274 40.8045944, -80.1123667 40.8047618, -80.1123187 40.8048961, -80.1122144 40.8052404, -80.1121822 40.8054597, " +
        "-80.1126328 40.8055247, -80.11318 40.8057277, -80.1136735 40.8060119, -80.1139935 40.8061, -80.1144689 40.8062548, -80.1147571 40.8065235, -80.115177 40.8068213, -80.1152614 40.8070676, " +
        "-80.1150468 40.8073031, -80.1149288 40.8075955, -80.1150039 40.8079934, -80.1151026 40.8081061, -80.1152399 40.8081396, -80.1156798 40.8082857, -80.1151843 40.8089253, -80.1156524 40.808904, " +
        "-80.1162332 40.8091775, -80.1157808 40.8095377, -80.1156441 40.8096134, -80.1155087 40.8096884, -80.1151646 40.8098791, -80.1147561 40.8100954, -80.1147128 40.8101183, -80.1145352 40.8101879, " +
        "-80.1142434 40.8103022, -80.1137421 40.8105106, -80.1136367 40.8101601, -80.1124244 40.8101033, -80.1121871 40.8099392, -80.1122527 40.8098272, -80.1125317 40.8098231, -80.1126926 40.8093887, " +
        "-80.1129976 40.808775, -80.1128367 40.8084177, -80.1128685 40.8082688, -80.1129547 40.8078655, -80.1128903 40.8073945, -80.1128903 40.8069722, -80.1130083 40.8067529, -80.1128045 40.8065174, " +
        "-80.1121608 40.8063794, -80.1115492 40.8062576, -80.111312 40.806182, -80.1111323 40.8063058, -80.1108733 40.8061601, -80.1099828 40.8057866, -80.1095966 40.8057297, -80.1091352 40.805478, " +
        "-80.1085936 40.8053328, -80.1080731 40.8053967, -80.1077088 40.8055159, -80.1073654 40.8054672, -80.1063779 40.8050719, -80.1057878 40.8048932, -80.1051012 40.8047146, -80.1045237 40.804701, " +
        "-80.1039834 40.803764, -80.1044145 40.803941, -80.1055089 40.8042334, -80.1063243 40.8044527, -80.1069251 40.8045014, -80.1073717 40.8045757, -80.1076775 40.8047463, -80.1081173 40.8047138, " +
        "-80.1085143 40.8046813, -80.1088241 40.8049968, -80.1093399 40.8050004, -80.1096931 40.8050455, -80.1101759 40.8050618, -80.1103047 40.8050374, -80.1104549 40.8046232, -80.1106051 40.8041522, " +
        "-80.1107553 40.8036937, -80.1088178 40.8030618, -80.1088714 40.8029156, -80.1094293 40.8030496, -80.1095751 40.8030051, -80.1091996 40.802599, -80.1089636 40.8023797, -80.1090816 40.8022741, " +
        "-80.109382 40.8023797, -80.1099399 40.8025746, -80.1103905 40.8028751, -80.1108089 40.8030375, -80.1110557 40.8028914, -80.1114956 40.80307, -80.1119998 40.803338, -80.112429 40.8033299, -80.112665 40.8031512, " +
        "-80.1121822 40.8029563, -80.1115063 40.8025665, -80.1108411 40.8023391, -80.1105407 40.8018924, -80.1103905 40.8014945, -80.1098648 40.8012996, -80.1092318 40.8009828, -80.1086417 40.8009585, " +
        "-80.1087597 40.8006417, -80.1096065 40.8007592, -80.1117469 40.8018434, -80.1126175 40.8023287, -80.1138093 40.8032437, -80.1140089 40.8033365, -80.1142363 40.8033396, -80.1146277 40.8032744, " +
        "-80.1159865 40.8029532, -80.1172922 40.802728, -80.1177849 40.8026481, -80.1179499 40.8014287, -80.1177068 40.8033675, -80.1176231 40.8040661, -80.1175682 40.8044886, -80.1173232 40.8045697, " +
        "-80.114679 40.804454, -80.1146739 40.8043283, -80.1147726 40.8038162, -80.1139347 40.8040133, -80.1132184 40.8040944, -80.113193 40.8041732, -80.1130709 40.8042723, -80.1128737 40.80424, -80.1124643 40.8042035), " +
        "(-80.112012 40.8039682, -80.1111747 40.8038305, -80.111237 40.8038512, -80.112012 40.8039682)," +
        " (-80.1124643 40.8042035, -80.112484 40.804144, -80.1125136 40.8040207, -80.1124643 40.8042035))";
    checkPolygon(wkt);
  }

  public void testComplexPolygon39() throws Exception {
    String wkt ="POLYGON((71.8821959 52.3494653, 71.8824975 52.3494644, 71.8825076 52.3485511, 71.88209 52.3485465, 71.8820828 52.3487054, 71.8822007 52.3487626, 71.8822 52.3488601, 71.8821989 52.3490193, 71.8821959 52.3494653), " +
        "(71.8823576 52.3489838, 71.882321 52.348962, 71.882357 52.3489395, 71.8823936 52.3489613, 71.8823576 52.3489838), " +
        "(71.8823569 52.3494143, 71.8823916 52.349435, 71.8823568 52.3494567, 71.8823221 52.349436, 71.8823569 52.3494143), " +
        "(71.8823569 52.3494143, 71.8823263 52.349396, 71.8823588 52.3493757, 71.8823894 52.3493939, 71.8823569 52.3494143), " +
        "(71.8823588 52.3493757, 71.8823258 52.349356, 71.8823595 52.349335, 71.8823925 52.3493547, 71.8823588 52.3493757), " +
        "(71.8823595 52.349335, 71.8823277 52.3493161, 71.8823602 52.3492958, 71.8823919 52.3493147, 71.8823595 52.349335), " +
        "(71.8823602 52.3492958, 71.8823307 52.3492782, 71.8823595 52.3492602, 71.882389 52.3492778, 71.8823602 52.3492958), " +
        "(71.8823595 52.3492602, 71.8823307 52.349243, 71.8823611 52.349224, 71.8823899 52.3492412, 71.8823595 52.3492602), " +
        "(71.8823611 52.349224, 71.8823276 52.3492041, 71.882361 52.3491832, 71.8823944 52.3492031, 71.8823611 52.349224), " +
        "(71.882361 52.3491832, 71.8823281 52.3491636, 71.8823613 52.3491428, 71.8823942 52.3491624, 71.882361 52.3491832), " +
        "(71.8823613 52.3491428, 71.8823305 52.3491244, 71.8823618 52.3491048, 71.8823927 52.3491232, 71.8823613 52.3491428), " +
        "(71.8823618 52.3491048, 71.8823294 52.3490854, 71.8823607 52.3490659, 71.8823931 52.3490852, 71.8823618 52.3491048), " +
        "(71.8823607 52.3490659, 71.8823285 52.3490467, 71.8823581 52.3490282, 71.8823902 52.3490474, 71.8823607 52.3490659), " +
        "(71.8823581 52.3490282, 71.8823215 52.3490064, 71.8823576 52.3489838, 71.8823942 52.3490057, 71.8823581 52.3490282))";
    checkPolygon(wkt);
  }

  @Nightly
  public void testComplexPolygon40() throws Exception {
    String wkt = GeoTestUtil.readShape("lucene-9251.wkt.gz");
    Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
    List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
    // calculate the area of big polygons have numerical error
    assertEquals(area(polygon), area(tessellation), 1e-12);
    for (Tessellator.Triangle t : tessellation) {
      checkTriangleEdgesFromPolygon(polygon, t);
    }
  }

  public void testComplexPolygon41() throws Exception {
    String wkt = "POLYGON((-1.569137181294115 54.4855283059375, -1.5692505240440333 54.48535373128068, -1.5684753656387294 54.48534438253056, -1.568606793880459 54.485674703738624, -1.5694141387939453 54.48611720532629, -1.569137181294115 54.4855283059375)," +
        "(-1.569137181294115 54.4855283059375, -1.5690783030431206 54.48545352137167, -1.5689449291711688 54.48547663706703, -1.569137181294115 54.4855283059375)," +
        "(-1.5689449291711688 54.48547663706703, -1.5689437289004642 54.48535482680399, -1.5687730514221028 54.48538045082698, -1.5689449291711688 54.48547663706703)," +
        "(-1.5689449291711688 54.48547663706703,  -1.5689879483854345 54.485580118416785, -1.5687756358893499 54.485612860811244, -1.568765285875931 54.485496217554285, -1.5689449291711688 54.48547663706703))";
    checkPolygon(wkt);
  }

  @Nightly
  public void testComplexPolygon42() throws Exception {
    String geoJson = GeoTestUtil.readShape("lucene-9417.geojson.gz");
    Polygon[] polygons =Polygon.fromGeoJSON(geoJson);
    for (int i = 0; i < polygons.length; i++) {
      List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygons[i]);
      // calculate the area of big polygons have numerical error
      assertEquals(area(polygons[i]), area(tessellation), 1e-11);
      for (Tessellator.Triangle t : tessellation) {
       checkTriangleEdgesFromPolygon(polygons[i], t);
      }
    }
  }

  private void checkPolygon(String wkt) throws Exception {
    Polygon polygon = (Polygon) SimpleWKTShapeParser.parse(wkt);
    List<Tessellator.Triangle> tessellation = Tessellator.tessellate(polygon);
    assertEquals(area(polygon), area(tessellation), 0.0);
    for (Tessellator.Triangle t : tessellation) {
      checkTriangleEdgesFromPolygon(polygon, t);
    }
  }

  private double area(Polygon p) {
    double val = 0;
    for (int i = 0; i < p.numPoints() - 1; i++) {
      val += p.getPolyLon(i) * p.getPolyLat(i + 1)
          - p.getPolyLat(i) * p.getPolyLon(i + 1);
    }
    double area = Math.abs(val / 2.);
    for (Polygon hole : p.getHoles()) {
      area -= area(hole);
    }
    return area;
  }

  private double area(List<Tessellator.Triangle> triangles) {
    double area = 0;
    for (Tessellator.Triangle t : triangles) {
      double[] lats = new double[] {t.getY(0), t.getY(1), t.getY(2), t.getY(0)};
      double[] lons = new double[] {t.getX(0), t.getX(1), t.getX(2), t.getX(0)};
      area += area(new Polygon(lats, lons));
    }
    return area;
  }

  private void checkTriangleEdgesFromPolygon(Polygon p, Tessellator.Triangle t) {
    // first edge
    assertEquals(t.isEdgefromPolygon(0), isEdgeFromPolygon(p, t.getX(0), t.getY(0), t.getX(1), t.getY(1)));
    // second edge
    assertEquals(t.isEdgefromPolygon(1), isEdgeFromPolygon(p, t.getX(1), t.getY(1), t.getX(2), t.getY(2)));
    // third edge
    assertEquals(t.isEdgefromPolygon(2), isEdgeFromPolygon(p, t.getX(2), t.getY(2), t.getX(0), t.getY(0)));
  }

  private boolean isEdgeFromPolygon(Polygon p, double aLon, double aLat, double bLon, double bLat) {
    for (int i = 0; i < p.getPolyLats().length - 1; i++) {
      if (isPointInLine(p.getPolyLon(i), p.getPolyLat(i), p.getPolyLon(i + 1), p.getPolyLat(i + 1), aLon, aLat) &&
          isPointInLine(p.getPolyLon(i), p.getPolyLat(i), p.getPolyLon(i + 1), p.getPolyLat(i + 1), bLon, bLat)) {
        return true;
      }
      if (p.getPolyLon(i) != p.getPolyLon(i + 1) || p.getPolyLat(i) != p.getPolyLat(i + 1)) {
        //Check for co-planar points
        final int length = p.getPolyLats().length;
        final int offset = i + 2;
        int j = 0;
        int index = getIndex(length, j + offset);
        while (j < length  && area(p.getPolyLon(i), p.getPolyLat(i), p.getPolyLon(i + 1), p.getPolyLat(i + 1), p.getPolyLon(index), p.getPolyLat(index)) == 0) {
          if (isPointInLine(p.getPolyLon(i), p.getPolyLat(i), p.getPolyLon(index), p.getPolyLat(index), aLon, aLat) &&
              isPointInLine(p.getPolyLon(i), p.getPolyLat(i), p.getPolyLon(index), p.getPolyLat(index), bLon, bLat)) {
            return true;
          }
          index = getIndex(length, ++j + offset);
        }
      }
    }
    if (p.getHoles() != null && p.getHoles().length > 0) {
      for (Polygon hole : p.getHoles()) {
        if (isEdgeFromPolygon(hole, aLon, aLat, bLon, bLat)) {
          return true;
        }
      }
    }
    return false;
  }

  private int getIndex(int size, int index) {
    if (index < size) {
      return index;
    }
    return index - size;
  }

  /** Compute signed area of triangle */
  private double area(final double aX, final double aY, final double bX, final double bY,
                      final double cX, final double cY) {
    return (bY - aY) * (cX - bX) - (bX - aX) * (cY - bY);
  }

  private  boolean isPointInLine(final double aX, final double aY, final double bX, final double bY, double lon, double lat) {
    double dxc = lon - aX;
    double dyc = lat - aY;

    double dxl = bX - aX;
    double dyl = bY - aY;

    if (dxc * dyl - dyc * dxl == 0) {
      if (Math.abs(dxl) >= Math.abs(dyl))
        return dxl > 0 ?
            aX <= lon && lon <= bX :
            bX <= lon && lon <= aX;
      else
        return dyl > 0 ?
            aY <= lat && lat <= bY :
            bY <= lat && lat <= aY;
    }
    return false;
  }
}