What spot in Manhattan is farthest from any subway stop?

I thought I’d have a crack and writing some code to answer this Quora question.

Here is the resulting map, pixel value (grey scale) indicates pixel distance from nearest subway station:

I’m afraid the overlay is a bit of a mess, I’ll try and fix this tomorrow. But according to this map the answer is the far corner of Battery Park.

Here’s the code I used:


#include <png++/png.hpp>
#include <iostream>
#include <math.h>

using namespace std;

bool is_black(png::image< png::rgba_pixel > &image,size_t x,size_t y) {

  if(((image[y][x].red == 0) && (image[y][x].green == 0) && (image[y][x].blue == 0))) return true;

  return false;
}

int get_distance(int x,int y,int cx,int cy) {
  int xd = (cx-x);
  if(xd<0) xd = 0-xd;

  int yd = cy-y;
  if(yd<0) yd = 0-yd;

  return sqrt((xd*xd)+(yd*yd));
}

int get_nextdist(png::image< png::rgba_pixel > &image,size_t xin,size_t yin) {

  int x = xin;
  int y = yin;

  int mindist = 10000;
  for(int cx=(x-500);cx<(x+500);cx++) {
    for(int cy(y-500);cy<(y+500);cy++) {

      if((cx > 0) && (cy > 0) && (cx < image.get_width()) && (cy < image.get_height())) {

        if(is_black(image,cx,cy)) {
          int dist = get_distance(x,y,cx,cy);
          if(dist < mindist) mindist = dist;
        }

      }
    }
  }

  return mindist;
}


int main() {

  png::image< png::rgba_pixel > image("input.png");

  // Make image black and white.
  for (size_t y = 0; y < image.get_height(); ++y) {
    for (size_t x = 0; x < image.get_width(); ++x) {
      if(((image[y][x].red <  80 ) && (image[y][x].green <  80 ) && (image[y][x].blue <  80 ) && (image[y][x].alpha != 0)) ||
         ((image[y][x].red == 255) && (image[y][x].green == 255) && (image[y][x].blue == 255) && (image[y][x].alpha != 0))) {
        image[y][x] = png::rgba_pixel(0, 0, 0);
      } else {
        image[y][x] = png::rgba_pixel(255, 255, 255);
      }
    }
  }

  png::image< png::rgba_pixel > oimage = image;
  // Filter out isolated pixels...
  for (size_t y = 1; y < (image.get_height()-1); ++y) {
    for (size_t x = 1; x < (image.get_width()-1); ++x) {
      if(is_black(oimage,x,y)) {
        int adj = 0;
        if(is_black(oimage,x+1,y  )) {adj++; }
        if(is_black(oimage,x-1,y  )) {adj++; }
        if(is_black(oimage,x  ,y+1)) {adj++; }
        if(is_black(oimage,x  ,y-1)) {adj++; }
        if(adj > 3) {
          // do nothing...
          image[y][x] = png::rgba_pixel(0, 0, 0,255);
        } else {
          image[y][x] = png::rgba_pixel(255, 255, 255,255);
        }
      }
    }
  }


  oimage = image;
  // Set each pixel value to min distance to nearest pixel.

  for (size_t y = 0; y < image.get_height(); ++y) {
    for (size_t x = 0; x < image.get_width(); ++x) {
      if(!is_black(oimage,x,y)) {
        cout << "processing: " << x << "," << y << endl;

        int distance = get_nextdist(oimage,x,y);

        image[y][x] = png::rgba_pixel(distance, distance, distance,255);
      }
    }
  }


 image.write("output.png");
}

Assorted files used…

Input to the above code:

Original image:

Maps from:
http://www.mta.info/nyct/maps/submap.htm (cropped from PDF).