title: Detecting which polyline-grids a line crosses
body: <p>Last year I built an extensive multi-tiered system to create a grid of qtr-mins.  It works well.
  My client would now like to pass in lines (two nodes of LatLng) and would like me to return which Qtr Mins it touches.  FWIW, a QtrMin is a polygon that is 1/60/4 (1/4 minute) by 1/60/4.</p>
  
  <p>Below is the stripped down script.  I have an entry function where I will pass in the line nodes and I will write an external function to pass out the QtrMins touched.</p>
  
  <p>Part of the problem is that I have drawn my Qtr Mins from polylines but that is how it is.</p>
  
  <p>I will be leveraging the script via Delphi and making a function call to pass in the Lat/Lng pairs.</p>
  
  <pre><code>function getQtrMinTouched(oLat,oLng, fLat,fLng){
      // Lost and confused here
  }   
  </code></pre>
  
  <p>and depending how the result is returned, I will make a call through a com object to pass the QtrMin to my program.  Passing in arguments to functions and passing out results are already solved.  Including that here would contribute little but would entail several modules to simply run.
  My question is: using the grids I create below, is there a way to determine which of those grids are touched by a line (LatLng, LatLng)?  A line may span multiple grids.  A line will always be defined as two nodes (LatLng, LatLng).</p>
  
  <pre><code>&lt;html&gt;
  &lt;head&gt;
      &lt;title&gt;Find your Qtr minute locator
      &lt;/title&gt;
      &lt;script type="text/javascript"
              src="https://maps.googleapis.com/maps/api/js?v=3.24&amp;amp;libraries=geometry"&gt;
      &lt;/script&gt;
      &lt;meta http-equiv="X-UA-Compatible" content="IE=edge"&gt;
  &lt;/head&gt;
  
  &lt;body&gt;
  &lt;div id="map-canvas" style="HEIGHT: 100%; WIDTH: 100%" onclick=""&gt;&lt;/div&gt;
  
  
  &lt;div id="map"&gt;&lt;/div&gt;
  
  &lt;script type="text/javascript"&gt;
      var map;
      var llOffset = 1/60/4;
      var qtrNELatLngCode;
      var qtrNorth;
      var qtrEast;
      var qtrSWLatLngCode;
      var qtrSouth;
      var qtrWest;
      var latPolylines = [];
      var lngPolylines = [];
      var lngLabels = [];
  
      function initialize() {
          geocoder = new google.maps.Geocoder();
          map = new google.maps.Map(document.getElementById("map-canvas"), {
              center: new google.maps.LatLng(34.0, -84.0),
              zoom: 16,
              streetViewControl: true,
              mapTypeId: google.maps.MapTypeId.ROADMAP,
              scaleControl: true
          });
  
          google.maps.event.addListener(map, "idle", function () {
              var sLat = map.getCenter().lat();
              var sLng = map.getCenter().lng();
  
              //external.ShowMarker(sLat,sLng);
              createGridLines(map.getBounds());
          });
      }  // initialize
  
      google.maps.event.addDomListener(window, "load", initialize);
  
      function createGridLines(bounds) {
          for (var i = 0; i &lt; latPolylines.length; i++) {
              latPolylines[i].setMap(null);
          }
  
          latPolylines = [];
          for (var j = 0; j &lt; lngPolylines.length; j++) {
              lngPolylines[j].setMap(null);
          }
          lngPolylines = [];
  
          for (var k = 0; k &lt; lngLabels.length; k++) {
              lngLabels[k].setMap(null);
          }
          lngLabels = [];
  
          if (map.getZoom() &lt; 12) {
              return;
          }
          var north = bounds.getNorthEast().lat();
          var east = bounds.getNorthEast().lng();
          var south = bounds.getSouthWest().lat();
          var west = bounds.getSouthWest().lng();
  
          // define the size of the grid
          var topLat = Math.ceil(north / llOffset) * llOffset;
          var rightLong = Math.ceil(east / llOffset) * llOffset;
  
          var bottomLat = Math.floor(south / llOffset) * llOffset;
          var leftLong = Math.floor(west / llOffset) * llOffset;
  
  
          qtrNELatLngCode = ddToQM(topLat, rightLong);
          qtrNorth = qtrNELatLngCode.substring(0, 5);
          qtrEast = qtrNELatLngCode.substring(5, 12);
          qtrSWLatLngCode = ddToQM(bottomLat, leftLong);
          qtrSouth = qtrSWLatLngCode.substring(0, 5);
          qtrWest = qtrSWLatLngCode.substring(5, 12);
  
          for (var latitude = bottomLat; latitude &lt;= topLat; latitude += llOffset) latPolylines.push(new google.maps.Polyline({
              path: [
                  new google.maps.LatLng(latitude, leftLong), new google.maps.LatLng(latitude, rightLong)],
              map: map,
              geodesic: true,
              strokeColor: "#0000FF",
              strokeOpacity: 0.1,
              strokeWeight: 1
          }));
          for (var longitude = leftLong; longitude &lt;= rightLong; longitude += llOffset) lngPolylines.push(new google.maps.Polyline({
              path: [
                  new google.maps.LatLng(topLat, longitude), new google.maps.LatLng(bottomLat, longitude)],
              map: map,
              geodesic: true,
              strokeColor: "#0000FF",
              strokeOpacity: 0.1,
              strokeWeight: 1
          }));
  
          if ((map.getZoom() &lt; 16)) {
              for (var l = 0; l &lt; lngLabels.length; l++) {
                  lngLabels[l].setMap(null);
              }
              lngLabels = [];
              return;
          }  // set lngLabels to null
  
          for (var x = 0; x &lt; latPolylines.length; ++x) {
              for (var y = 0; y &lt; lngPolylines.length; ++y) {
                  var latLng = new google.maps.LatLng(latPolylines[x].getPath().getAt(0).lat(),
                          lngPolylines[y].getPath().getAt(0).lng());
  
                  var qtrLatLng = ddToQM(latLng.lat(), latLng.lng());
  </code></pre>
  
  <p>Does the line touch this grid?  I would think that at point of drawing the vertices, I would test to see if the line (knowing the (latlng,latlng)). </p>
  
  <pre><code>                lngLabels.push(new google.maps.Marker({
                      map: map,
                      position: latLng,
                      icon: {
                          url: "https://chart.googleapis.com/chart?"
                          + "chst=d_bubble_text_small&amp;chld=bbbr|"
                          + qtrLatLng
                          + "|FFFFFF|000000",
                          anchor: new google.maps.Point(126, 42)
                      }
                  }));
              }
          }
      }  // end createGridLines
  
  function getQtrMinTouched(oLat,oLng, fLat,fLng){
      // Lost and confused here
  }   
  
  
  
      function ddToQM(alat, alng) {
          var latResult, lngResult, dmsResult;
  
          alat = parseFloat(alat);
          alng = parseFloat(alng);
  
          latResult = "";
          lngResult = "";
  
          latResult += getDms(alat);
          lngResult += getDms(alng);
  
          dmsResult = latResult + lngResult;
  
          // Return the resultant string.
          return dmsResult;
      }
  
      function getDms(val) {
          // Required variables
          var valDeg, valMin, valSec, interimResult;
          var qtrMin;
          val = Math.abs(val);
  
          // ---- Degrees ----
          valDeg = Math.floor(val);
          valMin = Math.floor((val - valDeg) * 60);
          valSec = Math.round((val - valDeg - valMin / 60) * 3600 * 1000) / 1000;
  
          if (valSec == 60) {
              valMin += 1;
              valSec = 0;
          }
          if (valMin == 60) {
              valMin += 1;
              valSec = 0;
          }
          interimResult = valDeg + "";
  
          if (valMin &lt; 10) {
              valMin = "0" + valMin;
          }
  
          interimResult += valMin + "";
  
          switch (valSec) {
              case  0 :
                  qtrMin = "D";
                  break;
              case 15 :
                  qtrMin = "C";
                  break;
              case 30 :
                  qtrMin = "B";
                  break;
              case 45 :
                  qtrMin = "A";
                  break;
          }
          interimResult += qtrMin;
          return interimResult;
      }
  &lt;/script&gt;
  &lt;/body&gt;
  &lt;/html&gt;   
  </code></pre>