holyfuck.js

// An attempt at implementing the polygon labeling algo at:
// http://mapcontext.com/autocarto/proceedings/auto-carto-8/pdf/an-algorithm-for-locating-candidate-labeling-boxes-within-a-polygon.pdf
// I'm so sorry if you ever have to try and fix this code. Godspeed
function findOptimalLabelLocation(section_point_array, name) {
  var xy_objs = _.map(section_point_array, function(xy) { return {x: xy[0], y: xy[1]} });
  var simplified = simplify(xy_objs, 1);
  var edges = [];
  for (var i = 0; i < simplified.length-1; i++) {
    var current_point = simplified[i];
    var next_point = (i == simplified.length-1) ? simplified[0] : simplified[i+1];
    edges.push([current_point, next_point]);
  }

  var sorted_y = _.sortBy(simplified, function(xy){ return xy.y; });
  var strips = [];
  var previous_point = sorted_y[0];

  // Initialize the active segments
  // TODO: figure out why this doesn't always yield 2 elements
  var active_edges = _.filter(edges, function(edge) {
    return _.any(edge, function(point) {
      return point.x == previous_point.x && point.y == previous_point.y;
    });
  });


  for (var i = 1; i < sorted_y.length-1; i++) {
    var strip_lower_bound = previous_point.y;
    var strip_upper_bound = sorted_y[i].y;

    // Save the strips, their bounds, and current active edges
    strips[i] = {
      upper_bound: strip_upper_bound,
      lower_bound: strip_lower_bound,
      active_edges: _.clone(active_edges)
    };

    // Now remove active edges if the current y ends them
    _.remove(active_edges, function(edge) {
      return _.any(edge, function(point){
        return (point.y == strip_upper_bound);
      }) && _.any(edge, function(point){return point.y < strip_upper_bound});
    });

    // And active the edges that this segment begins
    var to_activate = _.filter(edges, function(edge) {
      return _.any(edge, function(point){
        return (point.y == strip_upper_bound);
      }) && _.any(edge, function(point){return point.y > strip_upper_bound});
    });

    active_edges = active_edges.concat(to_activate);
    console.log(active_edges.length%2==0 ? "Even active" : "WTF");
    previous_point = sorted_y[i];
  }

  // Now generate the segments based on active edges at each strip
  var vertical_segments = [];
  for (var k = 1; k < strips.length; k++) {
    var strip = strips[k];
    _.each(strip.active_edges, function(edge){
      var generatePointAtHorizontal = function(y) {
        // A little S&M to keep this function terrible
        // This will find the x value for a given y of the segment
        // I promise: https://www.wolframalpha.com/input/?i=solve+for+x%3B+y%3D%28%28y1%E2%88%92y2%29%2F%28x1%E2%88%92x2%29%29*%28x%E2%88%92x1%29%2By1
        var x = ((edge[0].x*y)-(edge[0].x*edge[1].y)-(edge[1].x*y)+(edge[1].x*edge[0].y))/(edge[0].y-edge[1].y);
        return {x: x, y: y};
      }
      var upper_point = generatePointAtHorizontal(strip.upper_bound);
      var lower_point = generatePointAtHorizontal(strip.lower_bound);
      vertical_segments.push({strip: k, upper_point: upper_point, lower_point: lower_point});
    });
  }

  var segment_midpoints = _.map(vertical_segments, function(segment){
    return {strip: segment.strip, segment_x: (segment.upper_point.x+segment.lower_point.x)/2};
  });

  // Get ordered vertical segments by x value
  var sorted_vertical_segments = _.sortBy(segment_midpoints, function(vertical_segment){ return vertical_segment.segment_x });

  // Create an array to do all the box-creation an initialize all values to 0
  var working_array = [];
  for (var i = 0; i < 4000; i++) {
    working_array[i] = {top: 0, left: 0, bottom: 0, right: 0};
  }
  var bottom, top;
  var boxes = [];
  for (var i = 0; i < sorted_vertical_segments.length-1; i++) {
    // Get the number of the current strip
    var s = sorted_vertical_segments[i].strip;

    // Establish the cluster limits
    bottom = s+1;
    while (working_array[bottom].left > 0) {
      bottom = working_array[bottom].bottom+1;
    }
    bottom--;
    top = s-1;
    while (working_array[top].left > 0) {
      top = working_array[top].top-1;
    }
    top++;

    if (working_array[s].left == 0) {
      // Process the left-defining-segment of the current strip
      working_array[s].left = i;
      working_array[s].right = 0;
      working_array[s].bottom = bottom;
      working_array[s].top = top;
    } else {
      // Process the right-defining-segment of the current strip
      for (var m = top; m < bottom; m++) {
        if (working_array[m].bottom <= s && s <= working_array[m].top) {
          // Update the right limit
          working_array[m].right = i;

          // Save the box
          var box = {
            top: working_array[m].top,
            bottom: working_array[m].bottom,
            right: working_array[m].right,
            left: working_array[m].left,
          };
          boxes.push(box);

          // Now update the working array entry
          if (s > m) {
            working_array[m].top = s+1;
            working_array[m].right = 0;
          } else if (s == m) {
            working_array[m].left = 0;
          } else {
            working_array[m].bottom = s-1;
            working_array[m].right = 0;
          }
        }
      }
    }
  }

  if (boxes.length) {
    var boxes_with_coords = _.map(boxes, function(box) {
      var width = sorted_vertical_segments[box.right].segment_x - sorted_vertical_segments[box.left].segment_x;
      var height = strips[box.top].upper_bound - strips[box.bottom].lower_bound;
      return {x: sorted_vertical_segments[box.left].segment_x, y: strips[box.bottom].lower_bound, height: height, width: width};
    });

    return boxes_with_coords;
  } else {
    return false;
  }
};