Google Maps API Winding path within polygon with rotate/grow/shrink/order options

Question

I'm not certain what I'm trying to achieve is possible, but I know there are some creative people here and admittedly, I'm going to need some hand holding on this one.

Here is a mockup of what I'd like to add:

Auto-generating/filling a shape inside a polygon. For my purpose, I don't need boxes, I need a single winding path to fill every user-created polygon. I need that winding path to hug the boundaries of the polygon as in my picture above. Draw small boxes inside a polygon

Here is the code I'm trying to apply this feature to:

//debugger;

/////////////////////////////////////////////////////////////
//Map Specifications

function initialize() {
  var map = new google.maps.Map(document.getElementById('map'), {
    zoom: 18,
    center: new google.maps.LatLng(33.27144940863937, -117.2983479390361),
    mapTypeId: google.maps.MapTypeId.SATELLITE,
    mapTypeId: google.maps.MapTypeId.HYBRID,
    tilt: 0,
    disableDefaultUI: true,
    zoomControl: true,
    mapTypeControl: false,
    scaleControl: true,
    streetViewControl: true,
    rotateControl: true,
    fullscreenControl: false
  });

  // Creates a drawing manager attached to the map that allows the user to draw
  // markers, lines, and shapes.
  drawingManager = new google.maps.drawing.DrawingManager({
    drawingControlOptions: {
      position: google.maps.ControlPosition.TOP_CENTER,
      drawingModes: [
        google.maps.drawing.OverlayType.POLYLINE,
        google.maps.drawing.OverlayType.POLYGON
      ]
    },
    markerOptions: {
      draggable: false
    },
    //https://developers.google.com/maps/documentation/javascript/reference#PolygonOptions
    polygonOptions: {
      clickable: true,
      draggable: false,
      editable: true,
      fillColor: '#00FF00',
      fillOpacity: 0.45,
      geodesic: false,
      strokeColor: '#000000',
      strokeOpacity: 08,
      //strokePosition: CENTER,
      strokeWeight: 3,
      visible: true,
      zIndex: 0
    },
    //https://developers.google.com/maps/documentation/javascript/reference#PolylineOptions
    polylineOptions: {
      clickable: true,
      draggable: false,
      editable: true,
      geodesic: false,
      //icons: ,
      strokeColor: '#FF00FF',
      strokeOpacity: 0.8,
      strokeWeight: 3,
      visible: true,
      zIndex: 0
    }
  });

  ////////////////////////////////////////////////////////////////////////////////
  var drawingManager;
  var deleteSelectedShape;
  var selectedShape;

  function clearSelection() {
    if (selectedShape) {
      if (selectedShape.type !== 'marker') {
        selectedShape.setEditable(false);
      }

      selectedShape = null;
    }
  }

  function setSelection(shape) {
    if (shape.type !== 'marker') {
      clearSelection();
      shape.setEditable(true);
    }

    selectedShape = shape;
  }
  DeleteShape = function deleteSelectedShape() {
    if (selectedShape) {
      selectedShape.setMap(null);
    }
    if (selectedShape.type == 'polygon') {
      document.getElementById("action_gon").value = 'adds, moves, deletions'
    } else if (selectedShape.type == 'polyline') {
      document.getElementById("action_line").value = 'adds, moves, deletions'
    }
  };

  /////////////////////////////////////////////////////////////
  //Populate textboxes with geo data when new polygon and polyline shape added

  drawingManager.setMap(map);

  google.maps.event.addDomListener(drawingManager, 'markercomplete', function(marker) {
    document.getElementById("action").value += "#marker\n";
    document.getElementById("action").value += marker.getPosition() + "\n";
  });

  google.maps.event.addDomListener(drawingManager, 'polylinecomplete', function(line) {
    path = line.getPath();
    //document.getElementById("action_line").value = ''
    document.getElementById("action_line").value = "#polyline shape added\n";
    for (var i = 0; i < path.length; i++) {
      document.getElementById("action_line").value += path.getAt(i) + "\n";
    }
  });

  google.maps.event.addDomListener(drawingManager, 'polygoncomplete', function(polygon) {
    var markerCnt = 0;
    path = polygon.getPath();
    //document.getElementById("action_gon").value = ''
    document.getElementById("action_gon").value = "#polygon shape added\n";
    for (var i = 0; i < path.length; i++) {
      document.getElementById("action_gon").value += path.getAt(i) + '\n';
    }
  });

  //////////////////////////////////////////////////////////////////////

  google.maps.event.addListener(drawingManager, 'overlaycomplete', function(e) {

    var newShape = e.overlay;
    newShape.type = e.type;

    if (e.type !== google.maps.drawing.OverlayType.MARKER) {
      // Switch back to non-drawing mode after drawing a shape.
      drawingManager.setDrawingMode(null);

      if (e.type == google.maps.drawing.OverlayType.POLYGON) {
        var coordinatesArray = e.overlay.getPath().getArray();
        document.getElementById("count_gon").value += "#\n";
        document.getElementById("count_gon").value += coordinatesArray + "\n";
      }

      //Catch vertex modifications (moves)
      function processVertices(e) {
        var ele;
        if (newShape.type == "polygon") {
          ele = document.getElementById("action_gon");
          //ele.value = "Modified vertex: "+e+"\n"+this.getAt(e)+"\nPolygon coords :\n";
          ele.value = "#polygon vertex " + e + " moved\n" + this.getAt(e) + "\n";
        } else if (newShape.type == "polyline") {
          ele = document.getElementById("action_line");
          //ele.value = "Modified vertex: "+e+"\n"+this.getAt(e)+"\nPolyline coords :\n";
          ele.value = "#polyline vertex " + e + " moved\n" + this.getAt(e) + "\n";
        } else return;
        for (var i = 0; i < newShape.getPath().getLength(); i++) {
          ele.value += newShape.getPath().getAt(i) + '\n';
        };
      };

      google.maps.event.addListener(newShape.getPath(), 'set_at', processVertices);
      google.maps.event.addListener(newShape.getPath(), 'insert_at', processVertices);

      /////////////////////////////////////////////////////////////
      // Add an event listener that selects the newly-drawn shape when the user clicks it.
      google.maps.event.addListener(newShape, 'click', function(e) {
        if (e.vertex !== undefined) {
          if (newShape.type === google.maps.drawing.OverlayType.POLYGON) {
            var path = newShape.getPaths().getAt(e.path);
            path.removeAt(e.vertex);

            /////////////////////////////////////////////////////////////
            //Update textboxes with geo data when polygon vertex deleted
            document.getElementById("action_gon").value = "#polygon vertex deleted\n";
            for (var i = 0; i < path.length; i++) {
              document.getElementById("action_gon").value += path.getAt(i) + '\n';
            }

            if (path.length < 3) {
              newShape.setMap(null);
              document.getElementById("action_gon").value = 'This box shows updated coords for POLYGONS based on user interactions (adds, moves, deletions).'
            }
          }

          if (newShape.type === google.maps.drawing.OverlayType.POLYLINE) {
            var path = newShape.getPath();
            path.removeAt(e.vertex);
            /////////////////////////////////////////////////////////////
            //Update textboxes with geo data when polyline vertex deleted
            document.getElementById("action_line").value = "#polyline vertex deleted\n";
            for (var i = 0; i < path.length; i++) {
              document.getElementById("action_line").value += path.getAt(i) + '\n';
            }

            if (path.length < 2) {
              newShape.setMap(null);
              document.getElementById("action_line").value = 'This box shows updated coords for POLYLINES based on user interactions (adds, moves, deletions).'
            }
          }
        }

        setSelection(newShape);
      });
      setSelection(newShape);
    } else {
      google.maps.event.addListener(newShape, 'click', function(e) {
        setSelection(newShape);
      });
      setSelection(newShape);
    }
  });

  // Link delete button to the UI element.
  var delbtn = /** @type {HTMLInputElement} */ (
    document.getElementById('delete-button'));
  map.controls[google.maps.ControlPosition.TOP_RIGHT].push(delbtn);

  // Clear the current selection when the drawing mode is changed, or when the
  // map is clicked.
  google.maps.event.addListener(drawingManager, 'drawingmode_changed', clearSelection);
  google.maps.event.addListener(map, 'click', clearSelection);

  // Listen for delete button click.
  google.maps.event.addDomListener(document.getElementById('delete-button'), 'click', deleteSelectedShape);

  /////////////////////////////////////////////////////////////////////

  //Places Search Box Setup
  var markers = [];
  var input = /** @type {HTMLInputElement} */ (
    document.getElementById('pac-input'));
  map.controls[google.maps.ControlPosition.TOP_LEFT].push(input);

  var searchBox = new google.maps.places.SearchBox(
    /** @type {HTMLInputElement} */
    (input));

  // [START region_getplaces]
  // Listen for the event fired when the user selects an item from the
  // pick list. Retrieve the matching places for that item.
  google.maps.event.addListener(searchBox, 'places_changed', function() {
    var places = searchBox.getPlaces();

    if (places.length == 0) {
      return;
    }
    for (var i = 0, marker; marker = markers[i]; i++) {
      marker.setMap(null);
    }

    // For each place, get the icon, place name, and location.
    markers = [];
    var bounds = new google.maps.LatLngBounds();
    for (var i = 0, place; place = places[i]; i++) {
      var image = {
        url: place.icon,
        size: new google.maps.Size(71, 71),
        origin: new google.maps.Point(0, 0),
        anchor: new google.maps.Point(17, 34),
        scaledSize: new google.maps.Size(25, 25)
      };

      bounds.extend(place.geometry.location);
    }

    map.fitBounds(bounds);
  });
}

google.maps.event.addDomListener(window, 'load', initialize);

#map,
html,
body {
  padding: 0;
  margin: 0;
  width: 100%;
  height: 100%;
}
#geoinfoboxes {
  display: none;
}
#delete-button {
  background: #0084ff;
  background-image: -webkit-linear-gradient(top, #0084ff, #000000);
  background-image: -moz-linear-gradient(top, #0084ff, #000000);
  background-image: -o-linear-gradient(top, #0084ff, #000000);
  background-image: linear-gradient(to bottom, #0084ff, #000000);
  border-radius: 30px;
  text-shadow: 0px 1px 3px #cfcdcf;
  -webkit-box-shadow: 0px 1px 3px #666666;
  -moz-box-shadow: 0px 1px 3px #666666;
  box-shadow: 0px 1px 3px #666666;
  font-family: Arial;
  margin-top: 5px;
  right: 0.5%;
  color: #ffffff;
  font-size: 15px;
  padding: 8px 10px 8px 10px;
  border: solid #a8a8a8 2px;
  text-decoration: none;
}
#delete-button:hover {
  background: #09ff00;
  background-image: -webkit-linear-gradient(top, #09ff00, #000000);
  background-image: -moz-linear-gradient(top, #09ff00, #000000);
  background-image: -o-linear-gradient(top, #09ff00, #000000);
  background-image: linear-gradient(to bottom, #09ff00, #000000);
  text-decoration: none;
}
.controls {
  border: 1px solid transparent;
  border-radius: 30px 30px 30px 30px;
  box-sizing: border-box;
  -moz-box-sizing: border-box;
  height: 32px;
  outline: none;
  box-shadow: 0 2px 6px rgba(0, 0, 0, 0.3);
  margin-top: 5px;
}
#pac-input {
  background-color: #fff;
  font-family: Roboto;
  font-size: 15px;
  font-weight: 300;
  margin-left: 12px;
  padding: 0 11px 0 13px;
  text-overflow: ellipsis;
  width: 400px;
}
#pac-input:focus {
  border-color: #4d90fe;
}
.pac-container {
  font-family: Roboto;
}

<!DOCTYPE html>
<!-- saved from url=(0014)about:internet -->
<html>

<head>
  <meta http-equiv="X-UA-Compatible" content="IE=Edge" />
  <meta name="viewport" content="initial-scale=1.0, user-scalable=no">
  <meta charset="UTF-8">
  <title>Test</title>
  <script type="text/javascript" src="http://maps.google.com/maps/api/js?key=AIzaSyBgmfaITmUDhXxk-0V33IPmNPd43mMd4ZU&libraries=drawing,places"></script>
</head>
<!-- -->

<body>
  <input id="pac-input" class="controls" type="text" placeholder="Search...">
  <input id="delete-button" onclick="DeleteShape();" type=button value="Delete Selected Shape">
  <div id="geoinfoboxes">
    <textarea id="action_line" rows="8" cols="46"></textarea>
    <textarea id="action_gon" rows="8" cols="46"></textarea>
    <textarea id="count_gon" rows="8" cols="46"></textarea>
  </div>
  <div id="map"></div>
</body>

</html>

EDIT: Looks like the grid-filled polygon from my image has been done using the Google API in the Android App, Tower. Here's an exact example of the grid type I'm wanting to create (skip to 2:10): https://www.youtube.com/watch?v=u-k8ax2JGC4. Looks like they offer the source code here: https://github.com/DroidPlanner/Tower, but I'd have no idea how to extract what I need and convert to javascript...

Here are a few more examples of how the generated polylines might wind:

This would use the curve of the polygon to continue back and forth around the gap, but this isn't very efficient.

This way would be ideal in the case where the polygon is concaved like this. The polyline path could work it's way down one side and back up the other.

I'm open to any way of accomplishing this the most efficient way possible (least distance traveled).

Answer 1

How to build the winding path

You can build the winding path the following way, suitable for areas without complex cavities.

1. Find the rectangle that contains user's polyline - getBounds example.
2. With a given directon taken as a line move from a corner with d (which must be less than winding size) to find first pair of intersections I1 and I2 with a polyline. So we have first segment of a path needed. Let it be points P[0] and P[1].
3. Move the intersection line for D distance lower and find the next pair of intersections I3 and I4. Make a short path from P[1] to I4. In case the path contains N polyline path points, we add N+1 points to path: P[2] ... P[N+2]
4. Then take I4 as the next point of the winding path.
5. Do 3. and 4. many times while next intersection exists. If not, finish creating the path.
6. Change direction manually to find a min way and max coverage.

First try

First let's do this for an invisible rectangle, that covers the polyline. Make a for loop and move down from a NW corner to EW corner. After deriving intersections, add two points to a windingPath. The example code is here.

While I was creating the example, I realized, that it would be easier to find intersections of a moving line with a rectangle or a polyline in a more universal manner than a set of conditions for different borders of a rectangle.

Finding intersections of the moving line with the polyline

One can find intersections using geometry formulae and a for loop for every segment of user's polyline. If a segment of a moving line intersects any of user's segments, we keep it as a point for a winding path.

The working code is here. Intersection between the moving line and the user's shape is found using var getLinePolylineCollisions = function(firstPoint, secondPoint, shape), this function uses a modified solution found in a very useful SO post here. I just changed x and y to lat() and lng() methods.

What else?

You can note that small segments of a winding path are straight lines and they can be outside the shape when it meets concaves. The next step is to make this segments to repeat exactly user's polyline segments.

P.S. you can avoid using first rectangle just to make every moving line with a constant length L = width / Math.cos(angleRadians).