PolygonBuilder.java

package com.maponics.algorithm;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.operation.polygonize.Polygonizer;
import com.vividsolutions.jts.operation.union.UnaryUnionOp;

import java.util.*;
import java.util.concurrent.Callable;

/**
 *
 * @author dbaston
 */
public class PolygonBuilder implements Callable<Geometry> {
    private final Polygonizer polygen;
    
    public PolygonBuilder(Collection<Geometry> inputs) {
        this.polygen = new Polygonizer();
        
        // Inputs that are incorrectly noded or may have duplicate geometry
        // can cause the polygonizer to fail.  Since polygonization is often
        // at the end of a long process, the price of UnaryUnionOp.Union()
        // is well worth it.
        //this.polygen.add(inputs);
        this.polygen.add(UnaryUnionOp.union(inputs));
    }
    
    @Override
    public Geometry call() {
        return this.getResult();
    }
    
    /** Given a collection of JTS Geometry objects, returns the subset of
     * Geometries that have at least one vertex that is not shared by
     * any other Geometry in the input set.
     * @param polys
     * @return 
     */
    public static Collection<Geometry> getNonRedundantGeom(Collection<Geometry> polys) {
        HashSet<Coordinate> uniqueVertices = new HashSet<>();
        HashSet<Coordinate> duplicateVertices = new HashSet<>();

        for (Geometry p : polys) {
            HashSet<Coordinate> verticesInThisPolygon = new HashSet<>(Arrays.asList(p.getCoordinates()));
            for (Coordinate c : verticesInThisPolygon) {
                if (!uniqueVertices.contains(c) && !duplicateVertices.contains(c)) {
                    uniqueVertices.add(c);
                } else {
                    uniqueVertices.remove(c);
                    duplicateVertices.add(c);
                }
            }
        }
        
        Set<Geometry> exteriorPolys = new HashSet<>();
        
        for (Geometry p : polys) {
            for (Coordinate c : p.getCoordinates()) {
                if (!duplicateVertices.contains(c)) {
                    // If this poly has at least one unique vertex, it must be exterior
                    exteriorPolys.add(p);
                    break;
                }
            }
        }
        
        return exteriorPolys;
    }
    
    /** Uses a JTS Polygonizer to identify all possible polygons from a set
     * of input linework, then uses an iterative algorithm to determine which
     * of the returned polygons represent holes.  The algorithm is:
     * 1.  Identify the outermost polygons in the returned set (those polygons
     *        that have at least one unique vertex).  These polygons cannot
     *        be holes.
     * 2.  Classify as a "hole" any polygon that has a linear intersection with
     *        a non-hole polygon.
     * 3.  Classify as "non-hole" any polygon that has a linear intersection
     *        with a hole polygon.
     * 4.  Repeat steps 2-3 until all polygons have been classified.
     * 
     * @return A single Geometry representing the union of all non-hole polygons.
     */
    public Geometry getResult() {
        Collection<Geometry> polys = polygen.getPolygons();

        
        Set<Geometry> exteriorPolys = new HashSet<>(getNonRedundantGeom(polys));
        Set<Geometry> unknownPolys  = new HashSet<>(polys);
        Set<Geometry> interiorPolys = new HashSet<>();
        unknownPolys.removeAll(exteriorPolys);
        
        Geometry mainPoly = UnaryUnionOp.union(exteriorPolys);
        Geometry holePoly = null;
        
        boolean changed = true;
        while (!unknownPolys.isEmpty() && changed) {
            interiorPolys.clear();
            exteriorPolys.clear();
            changed = false;
            
            for (Geometry p : unknownPolys) {
                if (p.intersects(mainPoly) && p.intersection(mainPoly).getDimension() > 0) {
                    changed = true;
                    interiorPolys.add(p);
                } else if (holePoly != null && p.intersects(holePoly) && p.intersection(holePoly).getDimension() > 0) {
                    changed = true;
                    exteriorPolys.add(p);
                }
            }

            unknownPolys.removeAll(exteriorPolys);
            unknownPolys.removeAll(interiorPolys);
            
            if (!exteriorPolys.isEmpty()) {
                exteriorPolys.add(mainPoly);
                mainPoly = UnaryUnionOp.union(exteriorPolys);
            }
    
            if (!interiorPolys.isEmpty()) {
                if (holePoly != null) {
                    interiorPolys.add(holePoly);
                }
                holePoly = UnaryUnionOp.union(interiorPolys);
            }
        }
        
        return mainPoly;
    }
    
    
}

PolygonBuilderTest.java

import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryCollection;
import com.vividsolutions.jts.geom.PrecisionModel;
import com.vividsolutions.jts.geom.util.LinearComponentExtracter;
import com.vividsolutions.jts.noding.snapround.GeometryNoder;
import java.util.ArrayList;
import static junit.framework.Assert.assertTrue;
import static junit.framework.Assert.assertTrue;
import static junit.framework.Assert.assertTrue;
import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;

/**
 *
 * @author dbaston
 */
public class PolygonBuilderTest {
    
    public PolygonBuilderTest() {
    }
    
    @BeforeClass
    public static void setUpClass() {
    }
    
    @AfterClass
    public static void tearDownClass() {
    }
    
    @Before
    public void setUp() {
    }
    
    @After
    public void tearDown() {
    }
    
    private static Geometry getPolygonsFromGeometryCollection(String wkt) throws Exception {
        ArrayList<Geometry> components = new ArrayList<>();
        GeometryCollection coll = (GeometryCollection) geomFromWKT(wkt);
                for (int i=0; i < coll.getNumGeometries(); i++) {
            components.add(coll.getGeometryN(i));
        }
        
        PolygonBuilder pb = new PolygonBuilder(components);
        return pb.getResult();
    }

    private static void checkInputMatchesOutput(String wkt) throws Exception {
        Geometry input = geomFromWKT(wkt);
        GeometryNoder gn = new GeometryNoder(new PrecisionModel(1e6));
        Geometry poly = new PolygonBuilder(
                gn.node(LinearComponentExtracter.getLines(input, true))).getResult();
        assertTrue(input.equalsTopo(poly));
    }

    /**
     * Test of isHole method, of class PolygonBuilder.
     */
    @Test
    public void testIsHoleDonut() throws Exception {
        checkInputMatchesOutput(
                "POLYGON ((0 0, 0 20, 20 20, 20 0, 0 0), " +
                "   (5 5, 15 5, 15 15, 5 15, 5 5))");
    }

    /**
     * Three polygon components, in which a "top" and "bottom" each touch at
     * two single points.  A third "middle" is situated in between.
     * 
     * ___________
     * |          |
     * |    /\    |
     * |   /  \   |
     * |  /    \  |
     * | /      \ |
     * |/        \|
     * |\        /|
     * | \      / |
     * |  \    /  |
     * |   \  /   |
     * |    \/    |
     * |__________|
     * 
     * @throws Exception 
     */
    @Test
    public void testIsHoleBetweenTwoPieces() throws Exception {
        checkInputMatchesOutput(
                "MULTIPOLYGON (((0 0, 0 10, 5 5, 10 10, 10 0, 0 0)), " +
                    "((0 10, 0 20, 10 20, 10 10, 5 15, 0 10)))");
    }
    
    /** ____________________
     *  |  ______________  |
     *  |  |  ________  |  |
     *  |  |  |      |  |  |
     *  |  |  |______|  |  |
     *  |  |____________|  |
     *  |__________________|
     * 
     * @throws Exception 
     */
    @Test
    public void testBullsEye() throws Exception {
        checkInputMatchesOutput(
            "MULTIPOLYGON (((0 0, 0 20, 20 20, 20 0, 0 0), " +
            "  (5 5, 15 5, 15 15, 5 15, 5 5))," +
            "  ((8 8, 8 12, 12 12, 12 8, 8 8)))"
        );
    }
    
    /**  ____________________
     *   |  _____________   |
     *   |  |     ___    |  |
     *   |  |     |__|___|  |
     *   |  |________|      |
     *   |__________________|
     */
    @Test
    public void testConnectedComponentInsideHole() throws Exception {
        checkInputMatchesOutput(
                "MULTIPOLYGON (((0 0, 0 20, 40 20, 40 0, 0 0)," +
                "  (30 10, 35 10, 35 15, 5 15, 5 5, 30 5, 30 10))," +
                "  ((20 10, 20 12, 30 12, 30 10, 20 10)))");
    }

    @Test
    public void testMultipleIterationsNeededToSolve() throws Exception {
        checkInputMatchesOutput(
                "MULTIPOLYGON (((0 0, 0 70, 70 70, 70 0, 0 0), " +
                      "(20 10, 30 10, 30 20, 40 20, 40 10, 50 10, 50 20, 60 20, 60 30, 50 30, 50 40, 60 40, 60 50, 50 50, 50 60, 40 60, 40 50, 30 50, 30 60, 20 60, 20 50, 10 50, 10 40, 20 40, 20 30, 10 30, 10 20, 20 20, 20 10))," +
                "  ((20 20, 20 30, 30 30, 30 20, 20 20))," +
                "  ((40 20, 40 30, 50 30, 50 20, 40 20))," +
                "  ((30 30, 30 40, 40 40, 40 30, 30 30))," +
                "  ((20 40, 20 50, 30 50, 30 40, 20 40))," +
                "  ((40 40, 40 50, 50 50, 50 40, 40 40)))");
    }
    
    @Test
    public void testRegrNoTopologyException() throws Exception {
        Geometry poly = getPolygonsFromGeometryCollection("GEOMETRYCOLLECTION (LINESTRING (-82.727094 42.720942, -82.727089 42.720841, -82.727083 42.720756, -82.727079 42.720704, -82.72707 42.720533, -82.727071 42.720477, -82.72707 42.720422, -82.727068 42.720365, -82.727063 42.720303, -82.727054 42.720171, -82.72705 42.720107, -82.727047 42.720044, -82.727043 42.71998, -82.72704 42.719914, -82.727036 42.719846, -82.727031 42.719773, -82.727027 42.719696, -82.727017 42.719536, -82.727007 42.719382, -82.727003 42.719307, -82.72699 42.71909, -82.726987 42.719022, -82.726981 42.718893, -82.72698 42.718791, -82.726988 42.718728, -82.727011 42.718673, -82.727069 42.718633, -82.727145 42.718613, -82.724705 42.718701, -82.723486 42.718744, -82.723567 42.721062),    LINESTRING (-82.624127 42.664958, -82.625148 42.665203, -82.62525 42.665784, -82.625086 42.666494, -82.625375 42.666948, -82.625385 42.667085, -82.625857 42.667638, -82.625809 42.667759, -82.625545 42.667917, -82.626493 42.668687, -82.626869 42.668576, -82.628547 42.670132, -82.628313 42.670165, -82.628591 42.67039, -82.62864 42.670364, -82.62881 42.670376, -82.628864 42.670438, -82.628901 42.670577, -82.628662 42.670715, -82.628727 42.670903, -82.628975 42.671178, -82.629518 42.671814, -82.629927 42.672149, -82.630327 42.672422, -82.630541 42.672597, -82.63081 42.672744, -82.630881 42.672908, -82.630851 42.673169, -82.630937 42.673281, -82.631498 42.673604, -82.631838 42.673889, -82.632415 42.674124, -82.633028 42.674037, -82.633755 42.674095, -82.635325 42.674712, -82.635292 42.674868, -82.635124 42.674987, -82.634934 42.675107, -82.634955 42.675301, -82.635147 42.675479, -82.635472 42.675565, -82.635915 42.675602, -82.63634 42.675719, -82.636564 42.675758, -82.636756 42.675784, -82.636979 42.675774, -82.637168 42.67575, -82.637265 42.675712, -82.637306 42.675503, -82.638014 42.675507, -82.638109 42.675667, -82.638302 42.675775, -82.639643 42.67572, -82.639681 42.675505, -82.640246 42.675471, -82.640413 42.675622, -82.640535 42.675623, -82.640595 42.675516, -82.640803 42.675506, -82.641248 42.675432, -82.641144 42.675022, -82.641479 42.675095, -82.641596 42.675439, -82.642113 42.67547, -82.642711 42.675586, -82.643163 42.67561, -82.64357 42.67558, -82.643799 42.675767, -82.643932 42.675883, -82.644195 42.675907, -82.644473 42.675899, -82.644621 42.676012, -82.644855 42.676136, -82.645069 42.675972, -82.645268 42.675874, -82.645319 42.676052, -82.645471 42.676209, -82.645638 42.676194, -82.645754 42.676042, -82.645904 42.675957, -82.646105 42.675854, -82.646105 42.675768, -82.646138 42.675734, -82.646561 42.675761, -82.646851 42.675761, -82.647062 42.675719, -82.647167 42.676719, -82.647263 42.676819, -82.647343 42.676762, -82.647336 42.676625, -82.647282 42.67637, -82.647292 42.676188, -82.64728 42.675989, -82.647285 42.675636, -82.647291 42.675514, -82.647266 42.675282, -82.647521 42.675238, -82.647817 42.675216, -82.647975 42.675225, -82.64803 42.675294, -82.647969 42.675885, -82.647884 42.675977, -82.647868 42.676047, -82.647921 42.676115, -82.648221 42.676271, -82.648359 42.676224, -82.648449 42.676343, -82.648524 42.676499),    LINESTRING (-82.65818 42.680572, -82.657964 42.680598, -82.657413 42.680784, -82.657274 42.680696, -82.657224 42.680671, -82.656415 42.680355, -82.656041 42.680202, -82.655663 42.68004, -82.655839 42.679766, -82.655433 42.679667, -82.655224 42.679611, -82.654592 42.679445, -82.654419 42.679404, -82.652374 42.678871, -82.651727 42.678714, -82.651292 42.678596, -82.650367 42.678362, -82.649361 42.678117, -82.648497 42.677895, -82.647506 42.677659, -82.646492 42.677404, -82.646034 42.677279, -82.644643 42.676941, -82.64395 42.676767, -82.643424 42.676652, -82.64295 42.676564, -82.642353 42.676471, -82.641933 42.676416, -82.641509 42.676379, -82.640839 42.676342, -82.640352 42.676327, -82.63915 42.676318, -82.636744 42.676282, -82.636023 42.676186, -82.635207 42.676057, -82.632128 42.675505, -82.629298 42.674949, -82.628949 42.674869, -82.628524 42.674739, -82.628335 42.675071, -82.628303 42.675158, -82.628281 42.675247, -82.628275 42.675336, -82.628335 42.676821, -82.628443 42.679048, -82.628472 42.679858, -82.628299 42.679858, -82.627798 42.679847, -82.623083 42.679981, -82.617169 42.680147, -82.608563 42.680387),    LINESTRING (-82.710803 42.690242, -82.712767 42.691845, -82.713885 42.692758, -82.714947 42.693624, -82.716103 42.694569, -82.716697 42.695053, -82.723317 42.700441, -82.723108 42.700579, -82.723035 42.700606, -82.722697 42.700703, -82.722212 42.700981, -82.721459 42.701556, -82.720797 42.701991, -82.720684 42.702058, -82.720356 42.702229, -82.720028 42.702565, -82.719752 42.702945, -82.719664 42.703042, -82.720988 42.70344, -82.722822 42.703991, -82.729277 42.706059),    LINESTRING (-82.710008 42.721563, -82.710484 42.721554, -82.71084 42.721543, -82.712128 42.721471, -82.712167 42.7221, -82.712412 42.722096, -82.715509 42.721974, -82.715486 42.721604, -82.715497 42.721357, -82.715847 42.721336, -82.716298 42.721323, -82.717156 42.721291, -82.718741 42.721236, -82.719591 42.7212, -82.721027 42.721148, -82.723567 42.721062),    LINESTRING (-82.7087 42.688529, -82.709056 42.688816, -82.709608 42.689267, -82.710246 42.689788, -82.710803 42.690242),    LINESTRING (-82.709261 42.706841, -82.709272 42.707067, -82.709362 42.708806, -82.709451 42.710546, -82.709751 42.715916, -82.709815 42.717805, -82.709916 42.719694, -82.710008 42.721563),    LINESTRING (-82.620323 42.66498, -82.620349 42.665148, -82.620047 42.665119, -82.616443 42.665223, -82.616015 42.665202, -82.615652 42.665181, -82.615532 42.665085, -82.607999 42.665245, -82.607712 42.665457),    LINESTRING (-82.729277 42.706059, -82.729292 42.706354, -82.729564 42.711595, -82.729641 42.713423, -82.729867 42.718623, -82.729964 42.720843),    LINESTRING (-82.607712 42.665457, -82.607944 42.665541, -82.607711 42.666149, -82.607734 42.666336, -82.608111 42.672826, -82.608563 42.680387),    LINESTRING (-82.661314 42.681232, -82.661667 42.680659, -82.661799 42.680405, -82.66181 42.680361, -82.661806 42.680317, -82.661786 42.680272, -82.661753 42.680235, -82.661666 42.680173, -82.661478 42.680056, -82.661253 42.679904, -82.661038 42.679744, -82.660945 42.679686, -82.660896 42.67966, -82.660812 42.679625, -82.660756 42.67966, -82.660648 42.679961, -82.660597 42.680242, -82.660422 42.680963),    LINESTRING (-82.624127 42.664958, -82.622927 42.665116, -82.622719 42.664753, -82.622592 42.664321, -82.620241 42.664387, -82.620323 42.66498),    LINESTRING (-82.650359 42.67448, -82.650506 42.674472, -82.650593 42.674512, -82.650735 42.674546, -82.650862 42.674586, -82.652214 42.674799, -82.651784 42.673702, -82.652493 42.67378, -82.652842 42.674786, -82.653149 42.674788, -82.653188 42.674947, -82.653224 42.675097, -82.653721 42.675057, -82.653825 42.675056, -82.654064 42.675093, -82.654277 42.675148, -82.654428 42.675223, -82.654395 42.675454, -82.654289 42.675584, -82.654224 42.675699, -82.654179 42.675804, -82.654245 42.675913, -82.654558 42.676204, -82.654624 42.676332, -82.655051 42.677079, -82.655241 42.677539, -82.655274 42.67775, -82.655376 42.677947, -82.655564 42.678176, -82.655551 42.678295, -82.655457 42.678458, -82.655266 42.678659, -82.655157 42.678812, -82.655065 42.678925, -82.655018 42.679008, -82.655023 42.679121, -82.655128 42.679242, -82.655283 42.679325, -82.655454 42.679372, -82.655546 42.679256, -82.655377 42.679207, -82.655257 42.679136, -82.655304 42.679027, -82.655507 42.679023, -82.65565 42.678773, -82.655728 42.678703, -82.655958 42.678692, -82.656217 42.678777, -82.656411 42.67887, -82.656412 42.679033, -82.656776 42.679435, -82.657411 42.679849, -82.657619 42.680019, -82.657789 42.680284, -82.65792 42.680314, -82.658094 42.680354, -82.65818 42.680572),    LINESTRING (-82.660422 42.680963, -82.661314 42.681232),    LINESTRING (-82.727094 42.720942, -82.729964 42.720843),    LINESTRING (-82.7087 42.688529, -82.70823 42.688655, -82.708049 42.688697, -82.707071 42.688913, -82.706476 42.689045, -82.70452 42.689478, -82.703777 42.689632, -82.705063 42.690695),    LINESTRING (-82.718569 42.719613, -82.718492 42.718705, -82.718119 42.718175, -82.717913 42.718079, -82.713845 42.718228, -82.713701 42.71827, -82.713296 42.718827, -82.713297 42.719174, -82.713273 42.719651, -82.713442 42.719937, -82.713632 42.71996, -82.714196 42.719929, -82.715455 42.719857, -82.71573 42.719845, -82.717066 42.7198, -82.717111 42.7198, -82.717676 42.719742, -82.718133 42.719712, -82.718537 42.719639, -82.718569 42.719613),    LINESTRING (-82.705063 42.690695, -82.705001 42.690773, -82.704963 42.690808, -82.704641 42.691018, -82.704492 42.691119, -82.70424 42.691316, -82.704166 42.691387, -82.704112 42.691468, -82.704079 42.691555, -82.704048 42.691691, -82.704011 42.691866, -82.704129 42.692074, -82.70417 42.692159, -82.704255 42.692278, -82.704322 42.692354, -82.7044 42.692422, -82.704546 42.692524, -82.705468 42.69184, -82.705993 42.691436, -82.706642 42.691949, -82.707288 42.692462, -82.707546 42.692668, -82.70847 42.693408, -82.708519 42.693538, -82.708538 42.693626, -82.708599 42.694123, -82.708732 42.696953, -82.708925 42.699792, -82.708926 42.700144, -82.709261 42.706841),    LINESTRING (-82.650151 42.674732, -82.650367 42.674716, -82.650481 42.674584, -82.650468 42.674518, -82.650359 42.67448),    LINESTRING (-82.650151 42.674732, -82.650045 42.674741, -82.650133 42.676008, -82.649736 42.676309, -82.649434 42.676516, -82.649296 42.676587, -82.649131 42.676674, -82.648874 42.676688, -82.648632 42.676654, -82.648524 42.676499),    LINESTRING (-82.646707 42.675761, -82.646039 42.675235, -82.64609 42.67516, -82.646208 42.675123, -82.646378 42.675073, -82.646496 42.674985, -82.646581 42.67496, -82.646648 42.674998, -82.64667 42.675288, -82.646707 42.675761))");
    }
    
    @Test
    public void testRegrNoTopologyException2() throws Exception {
        Geometry poly = getPolygonsFromGeometryCollection("GEOMETRYCOLLECTION(LINESTRING (-114.978838 36.076338, -114.978723 36.076413, -114.978602 36.07648, -114.978428 36.076581, -114.978375 36.076608, -114.978174 36.076707, -114.97809 36.076738, -114.977839 36.076885, -114.977817 36.076897, -114.977712 36.076774, -114.977625 36.076694, -114.977533 36.07662, -114.97735 36.076465, -114.97726 36.07639, -114.977092 36.076253, -114.977013 36.07619, -114.976936 36.07613, -114.976787 36.07601, -114.976712 36.075949, -114.976632 36.075886, -114.976557 36.075942, -114.976449 36.076027, -114.976396 36.076062, -114.976353 36.076138, -114.976302 36.076197, -114.976275 36.076251, -114.976247 36.076317, -114.976224 36.076396, -114.97621 36.076486, -114.976203 36.076586, -114.976204 36.076693, -114.976216 36.07692, -114.976224 36.077159, -114.976231 36.077281, -114.976239 36.077405, -114.976248 36.077531, -114.976278 36.077919, -114.976296 36.078185, -114.976302 36.078285, -114.976305 36.078318, -114.976319 36.078577, -114.976324 36.078704, -114.976328 36.078829, -114.97633 36.078952, -114.97633 36.079073, -114.976328 36.079191, -114.976325 36.079309, -114.976323 36.079425, -114.976322 36.079541, -114.976323 36.079657, -114.976323 36.079772, -114.976322 36.079884, -114.976322 36.079992, -114.976329 36.080096, -114.976345 36.080196, -114.976371 36.080294, -114.976408 36.080389, -114.976457 36.08048, -114.976518 36.080565, -114.976592 36.080644, -114.976678 36.08072, -114.976773 36.080791, -114.976877 36.08086, -114.977203 36.08107, -114.977314 36.081141, -114.977529 36.081276, -114.977722 36.081396, -114.977879 36.081496, -114.977991 36.081571, -114.978046 36.081609, -114.978105 36.081648, -114.978164 36.08169, -114.978128 36.08175, -114.978057 36.081882, -114.977992 36.082019, -114.977932 36.082159, -114.977879 36.082294, -114.977833 36.082431, -114.977789 36.082575, -114.977754 36.08272, -114.977724 36.082861, -114.977702 36.082999, -114.977685 36.08314, -114.977675 36.083278, -114.977666 36.083415, -114.977661 36.083546, -114.97766 36.083677, -114.977663 36.083931, -114.977666 36.084054, -114.977676 36.084293, -114.977679 36.084402, -114.977681 36.084507, -114.977681 36.084632, -114.977684 36.084718, -114.97769 36.084824, -114.977687 36.084929, -114.977683 36.085141, -114.977683 36.085342, -114.977679 36.085427, -114.977674 36.085498, -114.977674 36.085564, -114.977676 36.085624, -114.977679 36.085768, -114.977687 36.085828, -114.977894 36.085853, -114.977975 36.085851, -114.978203 36.085843, -114.978347 36.085839, -114.978666 36.085831, -114.979167 36.08582, -114.979331 36.085817, -114.979498 36.085812, -114.979833 36.0858, -114.979998 36.085797, -114.98016 36.085795, -114.980319 36.085792, -114.980469 36.08579, -114.980885 36.085781, -114.981008 36.085777, -114.981124 36.085774, -114.981324 36.085771, -114.981404 36.085769, -114.981468 36.08577, -114.981558 36.085753, -114.98158 36.085732, -114.981756 36.085733, -114.981736 36.085206, -114.981751 36.085133, -114.981749 36.08508, -114.981743 36.085011, -114.981738 36.08493, -114.981728 36.084743, -114.981725 36.084531, -114.981726 36.084415, -114.981728 36.084298, -114.98173 36.084043, -114.981733 36.08378, -114.981735 36.083645, -114.981742 36.083367, -114.981747 36.083079, -114.981751 36.082782, -114.981752 36.082631, -114.981756 36.082323, -114.981759 36.082168, -114.981763 36.081855, -114.981766 36.081697, -114.981772 36.081221, -114.981773 36.080901, -114.981773 36.080088, -114.981774 36.079773, -114.981776 36.079459, -114.981785 36.078999, -114.981789 36.07885, -114.981793 36.078556, -114.981792 36.078412, -114.981793 36.078271, -114.98179 36.078129, -114.98179 36.077994, -114.981789 36.077747, -114.981789 36.077546, -114.981593 36.077543, -114.981535 36.07754, -114.981443 36.077537, -114.981369 36.077539, -114.981264 36.077545, -114.981149 36.077544, -114.981021 36.077542, -114.980888 36.077539, -114.980628 36.07753, -114.980509 36.077527, -114.980379 36.077527, -114.98038 36.07743, -114.980379 36.077375, -114.980376 36.07732, -114.980376 36.077271, -114.980383 36.077145, -114.980395 36.077082, -114.98042 36.077037, -114.98049 36.07701), LINESTRING (-114.97535 36.089831, -114.975598 36.101595, -114.975985 36.119968, -114.974146 36.120883, -114.97326 36.120316, -114.970433 36.121716, -114.968995 36.12195, -114.96826 36.122662, -114.965879 36.124974, -114.965867 36.125383, -114.965811 36.125591, -114.96426 36.128155, -114.963357 36.129094, -114.962765 36.129689, -114.962144 36.130627, -114.961806 36.131383, -114.961496 36.131749, -114.959944 36.1331, -114.959859 36.13326, -114.959465 36.133421, -114.958848 36.134474, -114.958173 36.135299, -114.957893 36.135871, -114.957561 36.138093, -114.956244 36.141459, -114.954789 36.145741, -114.954227 36.146954, -114.953441 36.148443, -114.952092 36.151731, -114.951648 36.152816, -114.951282 36.153274, -114.949031 36.155084, -114.948948 36.155381, -114.948835 36.155427, -114.948326 36.155565, -114.944248 36.158447, -114.943369 36.1595, -114.943029 36.160118, -114.942831 36.160256, -114.941697 36.161536, -114.941042 36.163528, -114.939738 36.165198, -114.93934 36.165999, -114.938601 36.167761, -114.938569 36.16902, -114.938114 36.169934, -114.937718 36.170346, -114.937406 36.170529, -114.93701 36.170529, -114.936189 36.170186, -114.934095 36.169155, -114.931554 36.169132, -114.931187 36.1692, -114.930227 36.168765, -114.929114 36.168708, -114.927968 36.168651, -114.927855 36.168697, -114.928079 36.169156, -114.927937 36.169248, -114.927116 36.169228, -114.926521 36.16939, -114.925898 36.169758, -114.925245 36.170265, -114.924365 36.171851, -114.919875 36.178356, -114.919194 36.179345, -114.91809 36.179142, -114.91707 36.179214, -114.917087 36.179276, -114.917677 36.17945, -114.918196 36.179626, -114.919968 36.180888, -114.920643 36.181269, -114.922046 36.181773, -114.923434 36.182128, -114.923723 36.182253, -114.923833 36.182749, -114.923892 36.183606, -114.923697 36.183978, -114.923556 36.184529, -114.923307 36.184745, -114.922833 36.184613, -114.921806 36.184713, -114.921001 36.185227, -114.920558 36.185369, -114.918892 36.185515, -114.918421 36.185613, -114.918108 36.184659, -114.917434 36.18272, -114.917323 36.18237), LINESTRING (-114.904899 36.122235, -114.904878 36.122379, -114.904821 36.122688, -114.904737 36.122932, -114.9046 36.123274, -114.904489 36.123463, -114.904394 36.123597, -114.90429 36.123712, -114.903988 36.124018, -114.903712 36.124318, -114.903633 36.124443, -114.903539 36.124665, -114.903516 36.124762, -114.903509 36.124877, -114.903509 36.125095, -114.903522 36.125206, -114.903588 36.125428, -114.903634 36.125536, -114.903741 36.125711, -114.903997 36.125995, -114.904498 36.126509, -114.9048 36.126811, -114.905292 36.12733, -114.906118 36.128163, -114.906401 36.128457, -114.906588 36.128659, -114.90675 36.128872, -114.906875 36.129047, -114.906984 36.129225, -114.907224 36.129719, -114.907284 36.129859, -114.907358 36.1301, -114.907443 36.130499, -114.90745 36.1306, -114.907434 36.131005, -114.907446 36.131134, -114.907532 36.131574, -114.907586 36.131764, -114.907665 36.131953, -114.907735 36.1321, -114.907977 36.132524, -114.908112 36.13277, -114.908174 36.132895, -114.90829 36.13321, -114.908336 36.13342, -114.90835 36.133558, -114.908343 36.133809, -114.908299 36.13406, -114.908261 36.134198, -114.90821 36.134323, -114.908113 36.134512, -114.907953 36.13477, -114.907872 36.134884, -114.907736 36.135026, -114.907538 36.135193, -114.907324 36.135335, -114.907212 36.135393, -114.906974 36.135494, -114.906761 36.135565, -114.905876 36.135827, -114.905178 36.136049, -114.904118 36.136363, -114.903762 36.136472, -114.903279 36.136646, -114.903041 36.136737, -114.902676 36.136888, -114.902294 36.137063, -114.902092 36.137166, -114.900289 36.138121, -114.899628 36.138455, -114.899304 36.138607, -114.898986 36.138742, -114.898398 36.138967, -114.898128 36.139057, -114.897899 36.139124, -114.897666 36.139184, -114.897137 36.139307, -114.896841 36.139368, -114.89614 36.139497, -114.894665 36.139752, -114.894335 36.139816, -114.894046 36.139887, -114.893761 36.139966, -114.893515 36.140041, -114.893038 36.140194, -114.892806 36.140274, -114.892529 36.140384, -114.892257 36.140503, -114.891963 36.140644, -114.891531 36.140859, -114.891256 36.141006, -114.890958 36.141232, -114.890812 36.141334, -114.890364 36.141632, -114.890164 36.141776, -114.889837 36.142029, -114.889707 36.142135, -114.889456 36.142353, -114.889243 36.142555, -114.888818 36.142986, -114.888753 36.143069, -114.889159 36.14327, -114.88959 36.143451, -114.890107 36.143723, -114.890322 36.143877, -114.890671 36.144218, -114.890736 36.144299, -114.890844 36.144482, -114.89092 36.144656, -114.890992 36.144898, -114.891012 36.145029, -114.891026 36.145297, -114.891 36.14554, -114.890941 36.145789, -114.890833 36.146061, -114.890669 36.146313, -114.890445 36.14657, -114.890135 36.146862, -114.889715 36.147199, -114.888481 36.14823, -114.88808 36.148582, -114.887708 36.148973, -114.88759 36.149118, -114.88744 36.149342, -114.887328 36.149568, -114.887248 36.149813, -114.887198 36.150103, -114.887179 36.150539, -114.887208 36.150838, -114.887248 36.151013, -114.887352 36.151282, -114.887449 36.151485, -114.887608 36.151739, -114.887711 36.151873, -114.887793 36.151959, -114.891272 36.152534, -114.894002 36.152342, -114.895204 36.152676, -114.895746 36.152861, -114.896393 36.152872, -114.898644 36.153734, -114.899247 36.154059, -114.899276 36.154463, -114.899592 36.15517, -114.90013 36.156142, -114.900664 36.156904, -114.900941 36.15722, -114.902742 36.158079, -114.904782 36.158129, -114.904821 36.157928, -114.905047 36.157935, -114.905114 36.15746, -114.905602 36.157407, -114.905711 36.157451, -114.905891 36.157331, -114.906142 36.157498, -114.906311 36.157493, -114.907489 36.157696, -114.907987 36.157785, -114.908121 36.157673, -114.908303 36.157612, -114.908451 36.157826, -114.908434 36.158007, -114.908512 36.15847, -114.908738 36.158964, -114.908852 36.160154, -114.909216 36.161367, -114.909357 36.161504, -114.909385 36.161687, -114.909835 36.162489, -114.910764 36.163496, -114.91296 36.165373, -114.913044 36.165738, -114.913042 36.166449, -114.912814 36.167365, -114.912813 36.167869, -114.912953 36.168075, -114.913492 36.168297, -114.913661 36.168562, -114.913374 36.169311, -114.912975 36.16972, -114.912595 36.170065, -114.912568 36.170591, -114.913 36.172421, -114.91283 36.172409, -114.912783 36.172443, -114.912848 36.172658, -114.912825 36.172712, -114.912704 36.17274, -114.913036 36.173806, -114.9132 36.174414, -114.913575 36.175627, -114.913764 36.176192, -114.913931 36.176523, -114.914367 36.177251, -114.915164 36.178446, -114.916325 36.180222, -114.916673 36.180816, -114.91688 36.181206, -114.917104 36.18173, -114.917221 36.182051, -114.917323 36.18237), LINESTRING (-114.904899 36.122235, -114.905259 36.122155, -114.905503 36.122111, -114.905557 36.122078, -114.905631 36.122067, -114.905699 36.122029, -114.906288 36.121782, -114.906417 36.121782, -114.907114 36.121601, -114.907514 36.121463, -114.907785 36.12131, -114.907819 36.121271, -114.907853 36.121172, -114.907846 36.121117, -114.907988 36.121013, -114.908171 36.120793, -114.908401 36.12076, -114.908523 36.120761, -114.907928 36.120403, -114.908151 36.120441, -114.908429 36.120145, -114.90851 36.120107, -114.908598 36.120101, -114.908876 36.120228, -114.909011 36.120206, -114.909316 36.1202, -114.909424 36.120112, -114.909533 36.120074, -114.909648 36.120118, -114.909918 36.120261, -114.910115 36.120332, -114.910189 36.120316, -114.910548 36.120272, -114.910697 36.120316, -114.910887 36.120448, -114.910948 36.120437, -114.911483 36.120217, -114.911828 36.119987, -114.912024 36.119641, -114.912174 36.119509, -114.912411 36.11941, -114.912857 36.119289, -114.913135 36.11907, -114.91323 36.119004, -114.913393 36.118954, -114.91367 36.118938, -114.913799 36.118922, -114.913819 36.118933, -114.914225 36.118889, -114.914422 36.118823, -114.914517 36.118718, -114.914625 36.118427, -114.914673 36.118383, -114.914767 36.118339, -114.915025 36.118153, -114.915126 36.118065, -114.915451 36.117587, -114.915607 36.117472, -114.915966 36.117329, -114.916149 36.117164, -114.9164 36.11684, -114.916494 36.116774, -114.916731 36.11678, -114.916846 36.11673, -114.917138 36.116406, -114.917619 36.115923, -114.917768 36.115698, -114.917781 36.115665, -114.917856 36.115269, -114.91833 36.114621, -114.918574 36.11439, -114.918635 36.114209, -114.918784 36.113984, -114.918858 36.11389, -114.919373 36.113495, -114.919434 36.113467, -114.919779 36.113138, -114.920206 36.11249, -114.920477 36.112188, -114.920646 36.111803, -114.920748 36.111666, -114.921005 36.111463, -114.921256 36.111182, -114.921364 36.110974, -114.92154 36.110886, -114.921621 36.110814, -114.921743 36.110578, -114.921771 36.11049, -114.921974 36.110221, -114.922001 36.110089, -114.921926 36.10987, -114.921845 36.109677, -114.921933 36.109633, -114.922055 36.109628, -114.92213 36.109578, -114.92217 36.109513, -114.922157 36.109392, -114.922184 36.109298, -114.922231 36.109249, -114.92236 36.109238, -114.92259 36.109315, -114.922719 36.109276, -114.92301 36.109068, -114.923315 36.108947, -114.923403 36.108842, -114.923531 36.108584, -114.923606 36.108518, -114.923856 36.108442, -114.923917 36.108431, -114.924026 36.108442, -114.924195 36.108392, -114.924411 36.108288, -114.924608 36.108205, -114.924824 36.108057, -114.92494 36.107964, -114.925177 36.107733, -114.925569 36.107431, -114.925739 36.107156, -114.926057 36.106893, -114.926138 36.106794, -114.926226 36.106558, -114.926328 36.106398, -114.926341 36.106354, -114.926463 36.106195, -114.926545 36.106019, -114.926633 36.105915, -114.928198 36.106961, -114.928624 36.10663, -114.929034 36.106484, -114.929558 36.106266, -114.929575 36.10627, -114.929609 36.106135, -114.929665 36.106037, -114.929803 36.10588, -114.929923 36.105794, -114.93005 36.105732, -114.930213 36.105686, -114.930311 36.105672, -114.930691 36.105653, -114.9308 36.105643, -114.930929 36.105617, -114.933186 36.102976, -114.9332 36.103009, -114.933369 36.103136, -114.933525 36.103399, -114.933735 36.103652, -114.934093 36.103883, -114.934147 36.103872, -114.934337 36.103982, -114.934391 36.103976, -114.934491 36.10403), LINESTRING (-114.978838 36.076338, -114.978915 36.076429, -114.978984 36.076515, -114.979048 36.076601, -114.979108 36.076686, -114.979166 36.076769, -114.979219 36.07685, -114.979266 36.076934, -114.979309 36.077014, -114.97935 36.077087, -114.979363 36.077113, -114.979411 36.077055, -114.979456 36.076999, -114.979557 36.076966, -114.979619 36.076948, -114.97969 36.076922, -114.979765 36.076895, -114.979846 36.076867, -114.979924 36.076839, -114.97999 36.076814, -114.980067 36.076784, -114.980182 36.076713, -114.980229 36.076771, -114.980277 36.076825, -114.980367 36.076917, -114.980441 36.076985, -114.98049 36.07701), LINESTRING (-114.95044 36.095617, -114.956672 36.094768, -114.962145 36.093417, -114.965016 36.092981, -114.967724 36.091925, -114.970443 36.090947, -114.972632 36.090159, -114.972724 36.090194, -114.97292 36.090199, -114.973062 36.090166, -114.973299 36.090062, -114.973509 36.090073, -114.973658 36.090045, -114.973854 36.089941, -114.973922 36.089913, -114.974111 36.089897, -114.974314 36.089847, -114.974443 36.089842, -114.974768 36.089902, -114.974923 36.089897, -114.975248 36.089842, -114.97535 36.089831), LINESTRING (-114.934491 36.10403, -114.934622 36.104119, -114.934351 36.102812, -114.934439 36.102691, -114.93455 36.1026, -114.934709 36.102537, -114.934906 36.102504, -114.934946 36.102488, -114.935068 36.102411, -114.935447 36.102125, -114.935585 36.102106, -114.936031 36.101871, -114.936289 36.101737, -114.938014 36.101698, -114.938483 36.101716, -114.938473 36.102004, -114.938568 36.101982, -114.939001 36.10201, -114.939029 36.102021, -114.939306 36.10201, -114.939597 36.101938, -114.939699 36.101933, -114.939929 36.101955, -114.940098 36.101944, -114.94024 36.101911, -114.940315 36.101916, -114.940355 36.101905, -114.94043 36.101905, -114.940897 36.101806, -114.941364 36.101669, -114.941527 36.101636, -114.941709 36.101526, -114.941926 36.101235, -114.941987 36.101191, -114.942176 36.101103, -114.942441 36.100916, -114.942759 36.100625, -114.943036 36.100493, -114.943219 36.100323, -114.94353 36.10007, -114.943612 36.100021, -114.943706 36.099911, -114.943842 36.099686, -114.944004 36.099285, -114.944058 36.099252, -114.944282 36.099175, -114.944295 36.099142, -114.944295 36.099021, -114.944343 36.098944, -114.944465 36.098862, -114.944871 36.098653, -114.945148 36.098516, -114.945426 36.098307, -114.945764 36.098071, -114.945974 36.097829, -114.946096 36.097604, -114.94615 36.097527, -114.946597 36.097268, -114.946854 36.097219, -114.946895 36.097225, -114.947071 36.097159, -114.947233 36.097038, -114.947294 36.097016, -114.947734 36.097032, -114.947836 36.097016, -114.94833 36.096686, -114.949995 36.095678, -114.95044 36.095617), LINESTRING (-114.938473 36.102004, -114.938456 36.102009, -114.938453 36.102133, -114.938473 36.102004), LINESTRING (-114.903509 36.125038, -114.899374 36.125003, -114.899318 36.125344, -114.90016 36.125357, -114.900783 36.125368, -114.902672 36.125139, -114.903509 36.125038))");
    }
}