martijnvermaat/example.png

## example.png

      
    Raw
  

              example.png
            
          
## overlap-relative-centers.ipynb
{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Overlap-relative centers"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Given a list of regions (represented as a list of pairs), get the center of each region relative to the overlap of all regions.\n",
      "\n",
      "Example:\n",
      "\n",
      "![](https://gist.github.com/martijnvermaat/9008606/raw/69b42ca0623db3bc4ea341f0304053ad7d569744/example.png)\n",
      "\n",
      "In this example, we are interested in the numbers 3, 9, 10, 18, 25, 29.\n",
      "\n",
      "Let's go there in three steps.\n",
      "\n",
      "(Note that we don't pay particular attention to what constitutes overlap exactly and there may be off-by-one errors in the code below.)"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Preliminaries"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "\n",
      "import random\n",
      "from matplotlib import pyplot as plt\n",
      "\n",
      "def plot(regions):\n",
      "    \"\"\"Plot a list of regions.\"\"\"\n",
      "    plt.figure(figsize=(16, 4))\n",
      "    plt.xlim(0, 100)\n",
      "    plt.yticks([])\n",
      "    plt.ylim(-1, len(regions))\n",
      "    for i, region in enumerate(regions):\n",
      "        plt.plot(region, [i, i], 'b')\n",
      "\n",
      "def plot_no_overlap(regions):\n",
      "    \"\"\"Plot a list of non-overlapping regions.\"\"\"\n",
      "    plt.figure(figsize=(16, 1))\n",
      "    plt.xlim(0, 100)\n",
      "    plt.yticks([])\n",
      "    plt.ylim(-1, 1)\n",
      "    for region in regions:\n",
      "        plt.plot(region, [0, 0], 'b')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Test data"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Just re-run this cell to get new test regions."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "xs = [random.randint(1, 95) for _ in range(15)]\n",
      "ys = [random.randint(x + 5, min(100, x + 20)) for x in xs]\n",
      "regions = zip(xs, ys)\n",
      "plot(regions)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAA5YAAAD7CAYAAAARiQtnAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAADKpJREFUeJzt3V9o1XUfwPHPT86u+mdFTnTGIo05M6eUQVD0BwsCLVKi\nBSL+6UaCjK66ky7UiqgFXRXFKEi7SokaIZEUZRJLixSU2GjOEkKMzMhcv+ei5/HBnmdny4/62zl7\nve52dvbzc+DD+L237zxFWZZlAAAAwDmaUvUAAAAANDZhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGW\nAAAApNTG+8Surq7Yt2/fhZwFAACAiixYsCD27t17Tl9bjPd9LIuiCG95SaPbuHFjbNy4seoxIM0u\n0wzsMc3CLtMsMs3nKCwAAAApwhIAAIAUYcmkcuedd1Y9ApwXdplmYI9pFnYZ/I0lAAAA4W8sAQAA\nqJCwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAAUoQlAAAAKcISAACAlFrVAwAAABNPUVQ9wYVR\nllVP0JyEJQAA8D8EGP+Eo7AAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAi\nLAEAAEgRlgAAAKQISwAAAFKEJQAAACnCEgAAgJRa1QNAsyqKqiegkZVl1RMAAIyfsIQLRBgAADBZ\nOAoLAABAirAEAAAgRVgCAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQA\nACBFWAIAAJBSq3oAAACAeoqi6gnOTVlWPcHFIywBAIAJbTIFWqNyFBYAAIAUYQkAAECKsAQAACBF\nWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkFKregAm\nrqKoegKaWVlWPQEAAOeLsGRUbvwBAIDxcBQWAACAFGEJAABAirAEAAAgRVgCAACQIiwBAABIEZYA\nAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJBSq3oAGI+iqHoCGJ+yrHoCAICL\nT1jSENysAwDAxOUoLAAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAA\nUoQlAAAAKcISAACAFGEJAABAirAEAAAgpVb1AAAAQERRVD0Bza4sL9y1hSUAAEwAF/KmHy40R2EB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQI\nSwAAAFKEJQAAACm1qgcAAAAiiqLqCSaHsqx6guYkLAEAYAIQPDQyR2EBAABIEZYAAACkCEsAAABS\nhCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAAACm1qgcA\nAGgmRVH1BOemLKueAGhkwhIA4DwSaMBk5CgsAAAAKcISAACAFGEJAABAirAEAAAgRVgCAACQIiwB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACClVvUAAHCxFUXVE3C+lWXVEwBM\nbsISgElHhADA+eUoLAAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAA\nUoQlAAAAKcISAACAFGEJAABAirAEAAAgpVb1AAAAwPgURdUTUIWyrHqCsQlLAABoEI0QGExOjsIC\nAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgR\nlgAAAKQISwAAAFJqVQ8AAABQT1FUPcHEV5bV/vvCEgAAmNCqjibG5igsAAAAKcISAACAFGEJAABA\nirAEAAAgRVgCAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACClVvUA\nMNEURdUTwPiUZdUTAAD8RVjC37hZBwCAf8ZRWAAAAFKEJQAAACnCEgAAgBRhCQAAQIqwBAAAIEVY\nAgAAkCIsAQAASBGWAAAApAhLAAAAUoQlAAAAKcISAACAFGEJAABASq3qAQAAmklRVD0B/0RZVj0B\nNAdhCQBwHgkVYDJyFBYAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAA\nACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkFKregCgsRRF1RMwUZVl1RMAAFURlsA/Ih4AAPg7R2EB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQI\nSwAAAFKEJQAAACm1qgcA8oqi6gmYqMqy6gkAgMlAWEITEA8AAFTJUVgAAABShCUAAAApwhIAAIAU\nYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISyaVjz/+uOoR4LywyzQDe0yzsMsgLJlkfOOn\nWdhlmoE9plnYZRCWAAAAJAlLAAAAUoqyLMvxPLGrqyv27dt3oecBAACgAgsWLIi9e/ee09eOOywB\nAADg/3EUFgAAgBRhCQAAQMqYYdnX1xcdHR0xZ86cePbZZy/GTHBeDA0NxV133RXz5s2LG2+8MV5+\n+eWIiDh27FgsWbIkbrjhhrj33nvj+PHjFU8KYxsZGYmFCxfG0qVLI8Ie05iOHz8eK1asiLlz50Zn\nZ2d88cUXdpmGs3nz5pg3b17Mnz8/Hn300fj999/tMQ1hzZo10draGvPnzz/zWL3d3bx5c8yZMyc6\nOjriww8/HPP6dcNyZGQkHn/88ejr64v9+/fH22+/HQcOHEi8HLh4Wlpa4sUXX4xvv/02du/eHa+8\n8kocOHAgtmzZEkuWLImDBw/GPffcE1u2bKl6VBhTT09PdHZ2RlEUERH2mIb0xBNPxP333x8HDhyI\nr7/+Ojo6OuwyDWVwcDBeffXV6O/vj2+++SZGRkZi69at9piGsHr16ujr6zvrsdF2d//+/bFt27bY\nv39/9PX1xfr16+PPP/+se/26Yblnz56YPXt2tLe3R0tLSzzyyCOxffv25EuCi2P69OnR1dUVERGX\nXnppzJ07N4aHh2PHjh2xatWqiIhYtWpVvPvuu1WOCWM6fPhwvP/++7Fu3br4z/+3Zo9pND///HN8\n8sknsWbNmoiIqNVqccUVV9hlGsrll18eLS0tcfLkyTh9+nScPHkyZsyYYY9pCLfffntceeWVZz02\n2u5u3749uru7o6WlJdrb22P27NmxZ8+eutevG5bDw8Mxa9asMx+3tbXF8PDwOb0QqNLg4GB89dVX\nceutt8bRo0ejtbU1IiJaW1vj6NGjFU8H9T355JPx/PPPx5Qp//2WbY9pNAMDA3HNNdfE6tWrY9Gi\nRfHYY4/Fr7/+apdpKFdddVU89dRTce2118aMGTNi6tSpsWTJEntMwxptd48cORJtbW1nnjeeDqwb\nlv85cgWN7MSJE7F8+fLo6emJyy677KzPFUVhz5nQ3nvvvZg2bVosXLgwRnt3KHtMIzh9+nT09/fH\n+vXro7+/Py655JL/OS5ol5novvvuu3jppZdicHAwjhw5EidOnIi33nrrrOfYYxrVWLs71l7XDcuZ\nM2fG0NDQmY+HhobOKleY6P74449Yvnx5rFy5Mh588MGI+OunMT/++GNERPzwww8xbdq0KkeEuj77\n7LPYsWNHXHfdddHd3R0fffRRrFy50h7TcNra2qKtrS1uueWWiIhYsWJF9Pf3x/Tp0+0yDePLL7+M\n2267La6++uqo1Wrx0EMPxeeff26PaVij3U/8vQMPHz4cM2fOrHutumF58803x6FDh2JwcDBOnToV\n27Zti2XLlmXnh4uiLMtYu3ZtdHZ2xoYNG848vmzZsujt7Y2IiN7e3jPBCRPRpk2bYmhoKAYGBmLr\n1q1x9913x5tvvmmPaTjTp0+PWbNmxcGDByMiYufOnTFv3rxYunSpXaZhdHR0xO7du+O3336Lsixj\n586d0dnZaY9pWKPdTyxbtiy2bt0ap06dioGBgTh06FAsXry47rWKcrSzVf/2wQcfxIYNG2JkZCTW\nrl0bTz/99Hl6GXBhffrpp3HHHXfETTfddOZX95s3b47FixfHww8/HN9//320t7fHO++8E1OnTq14\nWhjbrl274oUXXogdO3bEsWPH7DENZ9++fbFu3bo4depUXH/99fHGG2/EyMiIXaahPPfcc9Hb2xtT\npkyJRYsWxWuvvRa//PKLPWbC6+7ujl27dsVPP/0Ura2t8cwzz8QDDzww6u5u2rQpXn/99ajVatHT\n0xP33Xdf3euPGZYAAABQT92jsAAAADAWYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAA\nAFKEJQAAACn/AoMq5KDi0u1fAAAAAElFTkSuQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x22faf50>"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Overlaps"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let's first just calculate the overlaps from the regions. We iterate over the regions (sorted by start position) and keep track of the current overlap. Whenever we reach a gap, we store the current overlap and start a new one. We have to be careful to not store the initial (0, 0) overlap."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def overlaps(regions):\n",
      "    regions = sorted(regions)\n",
      "\n",
      "    overlaps = []\n",
      "    overlap_x, overlap_y = 0, 0\n",
      "\n",
      "    for x, y in regions:\n",
      "        if overlap_y < x:\n",
      "            if overlap_y != 0:\n",
      "                overlaps.append( (overlap_x, overlap_y) )\n",
      "            overlap_x = x\n",
      "        overlap_y = max(overlap_y, y)\n",
      "\n",
      "    if overlap_y != 0:\n",
      "        overlaps.append( (overlap_x, overlap_y) )\n",
      "    return overlaps"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plot(regions)\n",
      "plot_no_overlap(overlaps(regions))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAA5YAAAD7CAYAAAARiQtnAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAADKpJREFUeJzt3V9o1XUfwPHPT86u+mdFTnTGIo05M6eUQVD0BwsCLVKi\nBSL+6UaCjK66ky7UiqgFXRXFKEi7SokaIZEUZRJLixSU2GjOEkKMzMhcv+ei5/HBnmdny4/62zl7\nve52dvbzc+DD+L237zxFWZZlAAAAwDmaUvUAAAAANDZhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGW\nAAAApNTG+8Surq7Yt2/fhZwFAACAiixYsCD27t17Tl9bjPd9LIuiCG95SaPbuHFjbNy4seoxIM0u\n0wzsMc3CLtMsMs3nKCwAAAApwhIAAIAUYcmkcuedd1Y9ApwXdplmYI9pFnYZ/I0lAAAA4W8sAQAA\nqJCwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAAUoQlAAAAKcISAACAlFrVAwAAABNPUVQ9wYVR\nllVP0JyEJQAA8D8EGP+Eo7AAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAi\nLAEAAEgRlgAAAKQISwAAAFKEJQAAACnCEgAAgJRa1QNAsyqKqiegkZVl1RMAAIyfsIQLRBgAADBZ\nOAoLAABAirAEAAAgRVgCAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQA\nACBFWAIAAJBSq3oAAACAeoqi6gnOTVlWPcHFIywBAIAJbTIFWqNyFBYAAIAUYQkAAECKsAQAACBF\nWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkFKregAm\nrqKoegKaWVlWPQEAAOeLsGRUbvwBAIDxcBQWAACAFGEJAABAirAEAAAgRVgCAACQIiwBAABIEZYA\nAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJBSq3oAGI+iqHoCGJ+yrHoCAICL\nT1jSENysAwDAxOUoLAAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAA\nUoQlAAAAKcISAACAFGEJAABAirAEAAAgpVb1AAAAQERRVD0Bza4sL9y1hSUAAEwAF/KmHy40R2EB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQI\nSwAAAFKEJQAAACm1qgcAAAAiiqLqCSaHsqx6guYkLAEAYAIQPDQyR2EBAABIEZYAAACkCEsAAABS\nhCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAAACm1qgcA\nAGgmRVH1BOemLKueAGhkwhIA4DwSaMBk5CgsAAAAKcISAACAFGEJAABAirAEAAAgRVgCAACQIiwB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACClVvUAAHCxFUXVE3C+lWXVEwBM\nbsISgElHhADA+eUoLAAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAA\nUoQlAAAAKcISAACAFGEJAABAirAEAAAgpVb1AAAAwPgURdUTUIWyrHqCsQlLAABoEI0QGExOjsIC\nAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgR\nlgAAAKQISwAAAFJqVQ8AAABQT1FUPcHEV5bV/vvCEgAAmNCqjibG5igsAAAAKcISAACAFGEJAABA\nirAEAAAgRVgCAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACClVvUA\nMNEURdUTwPiUZdUTAAD8RVjC37hZBwCAf8ZRWAAAAFKEJQAAACnCEgAAgBRhCQAAQIqwBAAAIEVY\nAgAAkCIsAQAASBGWAAAApAhLAAAAUoQlAAAAKcISAACAFGEJAABASq3qAQAAmklRVD0B/0RZVj0B\nNAdhCQBwHgkVYDJyFBYAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAA\nACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkFKregCgsRRF1RMwUZVl1RMAAFURlsA/Ih4AAPg7R2EB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQI\nSwAAAFKEJQAAACm1qgcA8oqi6gmYqMqy6gkAgMlAWEITEA8AAFTJUVgAAABShCUAAAApwhIAAIAU\nYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISyaVjz/+uOoR4LywyzQDe0yzsMsgLJlkfOOn\nWdhlmoE9plnYZRCWAAAAJAlLAAAAUoqyLMvxPLGrqyv27dt3oecBAACgAgsWLIi9e/ee09eOOywB\nAADg/3EUFgAAgBRhCQAAQMqYYdnX1xcdHR0xZ86cePbZZy/GTHBeDA0NxV133RXz5s2LG2+8MV5+\n+eWIiDh27FgsWbIkbrjhhrj33nvj+PHjFU8KYxsZGYmFCxfG0qVLI8Ie05iOHz8eK1asiLlz50Zn\nZ2d88cUXdpmGs3nz5pg3b17Mnz8/Hn300fj999/tMQ1hzZo10draGvPnzz/zWL3d3bx5c8yZMyc6\nOjriww8/HPP6dcNyZGQkHn/88ejr64v9+/fH22+/HQcOHEi8HLh4Wlpa4sUXX4xvv/02du/eHa+8\n8kocOHAgtmzZEkuWLImDBw/GPffcE1u2bKl6VBhTT09PdHZ2RlEUERH2mIb0xBNPxP333x8HDhyI\nr7/+Ojo6OuwyDWVwcDBeffXV6O/vj2+++SZGRkZi69at9piGsHr16ujr6zvrsdF2d//+/bFt27bY\nv39/9PX1xfr16+PPP/+se/26Yblnz56YPXt2tLe3R0tLSzzyyCOxffv25EuCi2P69OnR1dUVERGX\nXnppzJ07N4aHh2PHjh2xatWqiIhYtWpVvPvuu1WOCWM6fPhwvP/++7Fu3br4z/+3Zo9pND///HN8\n8sknsWbNmoiIqNVqccUVV9hlGsrll18eLS0tcfLkyTh9+nScPHkyZsyYYY9pCLfffntceeWVZz02\n2u5u3749uru7o6WlJdrb22P27NmxZ8+eutevG5bDw8Mxa9asMx+3tbXF8PDwOb0QqNLg4GB89dVX\nceutt8bRo0ejtbU1IiJaW1vj6NGjFU8H9T355JPx/PPPx5Qp//2WbY9pNAMDA3HNNdfE6tWrY9Gi\nRfHYY4/Fr7/+apdpKFdddVU89dRTce2118aMGTNi6tSpsWTJEntMwxptd48cORJtbW1nnjeeDqwb\nlv85cgWN7MSJE7F8+fLo6emJyy677KzPFUVhz5nQ3nvvvZg2bVosXLgwRnt3KHtMIzh9+nT09/fH\n+vXro7+/Py655JL/OS5ol5novvvuu3jppZdicHAwjhw5EidOnIi33nrrrOfYYxrVWLs71l7XDcuZ\nM2fG0NDQmY+HhobOKleY6P74449Yvnx5rFy5Mh588MGI+OunMT/++GNERPzwww8xbdq0KkeEuj77\n7LPYsWNHXHfdddHd3R0fffRRrFy50h7TcNra2qKtrS1uueWWiIhYsWJF9Pf3x/Tp0+0yDePLL7+M\n2267La6++uqo1Wrx0EMPxeeff26PaVij3U/8vQMPHz4cM2fOrHutumF58803x6FDh2JwcDBOnToV\n27Zti2XLlmXnh4uiLMtYu3ZtdHZ2xoYNG848vmzZsujt7Y2IiN7e3jPBCRPRpk2bYmhoKAYGBmLr\n1q1x9913x5tvvmmPaTjTp0+PWbNmxcGDByMiYufOnTFv3rxYunSpXaZhdHR0xO7du+O3336Lsixj\n586d0dnZaY9pWKPdTyxbtiy2bt0ap06dioGBgTh06FAsXry47rWKcrSzVf/2wQcfxIYNG2JkZCTW\nrl0bTz/99Hl6GXBhffrpp3HHHXfETTfddOZX95s3b47FixfHww8/HN9//320t7fHO++8E1OnTq14\nWhjbrl274oUXXogdO3bEsWPH7DENZ9++fbFu3bo4depUXH/99fHGG2/EyMiIXaahPPfcc9Hb2xtT\npkyJRYsWxWuvvRa//PKLPWbC6+7ujl27dsVPP/0Ura2t8cwzz8QDDzww6u5u2rQpXn/99ajVatHT\n0xP33Xdf3euPGZYAAABQT92jsAAAADAWYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAA\nAFKEJQAAACn/AoMq5KDi0u1fAAAAAElFTkSuQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x2eddf50>"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAA5YAAABUCAYAAAD5w6hcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAB+JJREFUeJzt3V9o1vUCx/HPZLvqnxW5oTMWacwtc0oZBEV/WEHgipRo\ngYh/upEgo6vupAtnRdSCropiFDS7yhE1QiIpyiSWK9pAiY3mLCHEyIyW6zkX5xwPnnO2iV9tPuv1\nutvjsx/fBz487K2/+dRUKpVKAAAA4BzNm+0DAAAAUN2EJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWE\nJQAAAEVqz/aJbW1tGRwcvJBnAQAAYJasWLEiBw4cOKfvrTnbz7GsqamJj7yk2m3fvj3bt2+f7WNA\nMVtmLrBj5gpbZq4oaT63wgIAAFBEWAIAAFBEWPK3cuedd872EeC8sGXmAjtmrrBl8DuWAAAAxO9Y\nAgAAMIuEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAA\nAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWEJQAAAEWE\nJQAAAEWEJQAAAEWEJQAAAEVqZ/sAXLxqamb7BEA1qVRm+wRnz/vb3HMx7c++qovt8HdyIfcuLJnS\nxfRGC3A+eX/jQrIvzpXtUM3cCgsAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkA\nAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEAR\nYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYQkAAEARYcnfyscffzzbR4DzwpaZC+yYucKW\nQVjyN+ONn7nClpkL7Ji5wpZBWAIAAFBIWAIAAFCkplKpVM7miW1tbRkcHLzQ5wEAAGAWrFixIgcO\nHDin7z3rsAQAAID/x62wAAAAFBGWAAAAFJkxLPv7+9Pc3JylS5fm2Wef/SvOBOfF2NhY7rrrrrS2\ntubGG2/Myy+/nCQ5duxY2tvbc8MNN+Tee+/N8ePHZ/mkMLPJycmsXLkya9asSWLHVKfjx49n3bp1\nWbZsWVpaWvLFF1/YMlWnq6srra2tWb58eR599NH8/vvvdkxV2LRpU+rr67N8+fLTj0233a6urixd\nujTNzc358MMPZ7z+tGE5OTmZxx9/PP39/RkaGsrbb7+d4eHhgpcDf526urq8+OKL+fbbb7Nv3768\n8sorGR4ezs6dO9Pe3p6DBw/mnnvuyc6dO2f7qDCj7u7utLS0pKamJknsmKr0xBNP5P7778/w8HC+\n/vrrNDc32zJVZXR0NK+++moGBgbyzTffZHJyMr29vXZMVdi4cWP6+/vPeGyq7Q4NDWXXrl0ZGhpK\nf39/tm7dmj///HPa608blvv378+SJUvS1NSUurq6PPLII9m9e3fhS4K/RkNDQ9ra2pIkl156aZYt\nW5bx8fH09fVlw4YNSZINGzbk3Xffnc1jwowOHz6c999/P1u2bMm//781O6ba/Pzzz/nkk0+yadOm\nJEltbW2uuOIKW6aqXH755amrq8vJkydz6tSpnDx5MgsXLrRjqsLtt9+eK6+88ozHptru7t2709nZ\nmbq6ujQ1NWXJkiXZv3//tNefNizHx8ezePHi0183NjZmfHz8nF4IzKbR0dF89dVXufXWW3P06NHU\n19cnSerr63P06NFZPh1M78knn8zzzz+fefP+85Ztx1SbkZGRXHPNNdm4cWNWrVqVxx57LL/++qst\nU1WuuuqqPPXUU7n22muzcOHCzJ8/P+3t7XZM1Zpqu0eOHEljY+Pp551NB04blv++5Qqq2YkTJ7J2\n7dp0d3fnsssuO+PPampq7JyL2nvvvZcFCxZk5cqVmerToeyYanDq1KkMDAxk69atGRgYyCWXXPI/\ntwvaMhe77777Li+99FJGR0dz5MiRnDhxIm+99dYZz7FjqtVM251p19OG5aJFizI2Nnb667GxsTPK\nFS52f/zxR9auXZv169fnwQcfTPLPv4358ccfkyQ//PBDFixYMJtHhGl99tln6evry3XXXZfOzs58\n9NFHWb9+vR1TdRobG9PY2JhbbrklSbJu3boMDAykoaHBlqkaX375ZW677bZcffXVqa2tzUMPPZTP\nP//cjqlaU/088d8dePjw4SxatGjaa00bljfffHMOHTqU0dHRTExMZNeuXeno6Cg9P/wlKpVKNm/e\nnJaWlmzbtu304x0dHenp6UmS9PT0nA5OuBjt2LEjY2NjGRkZSW9vb+6+++68+eabdkzVaWhoyOLF\ni3Pw4MEkyZ49e9La2po1a9bYMlWjubk5+/bty2+//ZZKpZI9e/akpaXFjqlaU/080dHRkd7e3kxM\nTGRkZCSHDh3K6tWrp71WTWWqe6v+5YMPPsi2bdsyOTmZzZs35+mnnz5PLwMurE8//TR33HFHbrrp\nptP/dN/V1ZXVq1fn4Ycfzvfff5+mpqa88847mT9//iyfFma2d+/evPDCC+nr68uxY8fsmKozODiY\nLVu2ZGJiItdff33eeOONTE5O2jJV5bnnnktPT0/mzZuXVatW5bXXXssvv/xix1z0Ojs7s3fv3vz0\n00+pr6/PM888kwceeGDK7e7YsSOvv/56amtr093dnfvuu2/a688YlgAAADCdaW+FBQAAgJkISwAA\nAIoISwAAAIoISwAAAIoISwAAAIoISwAAAIoISwAAAIoISwAAAIr8A3MYtzDqpeu4AAAAAElFTkSu\nQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x2eddd50>"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Gaps"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Likewise, we can also calculate the gaps between the regions. It's actually a bit easier since we have less to keep track of."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def gaps(regions):\n",
      "    regions = sorted(regions)\n",
      "\n",
      "    gaps = []\n",
      "    gap_x = 0\n",
      "\n",
      "    for x, y in regions:\n",
      "        if gap_x < x:\n",
      "            if gap_x != 0:\n",
      "                gaps.append( (gap_x, x) )\n",
      "        gap_x = max(gap_x, y)\n",
      "\n",
      "    return gaps"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plot(regions)\n",
      "plot_no_overlap(gaps(regions))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAA5YAAAD7CAYAAAARiQtnAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAADKpJREFUeJzt3V9o1XUfwPHPT86u+mdFTnTGIo05M6eUQVD0BwsCLVKi\nBSL+6UaCjK66ky7UiqgFXRXFKEi7SokaIZEUZRJLixSU2GjOEkKMzMhcv+ei5/HBnmdny4/62zl7\nve52dvbzc+DD+L237zxFWZZlAAAAwDmaUvUAAAAANDZhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGW\nAAAApNTG+8Surq7Yt2/fhZwFAACAiixYsCD27t17Tl9bjPd9LIuiCG95SaPbuHFjbNy4seoxIM0u\n0wzsMc3CLtMsMs3nKCwAAAApwhIAAIAUYcmkcuedd1Y9ApwXdplmYI9pFnYZ/I0lAAAA4W8sAQAA\nqJCwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAAUoQlAAAAKcISAACAlFrVAwAAABNPUVQ9wYVR\nllVP0JyEJQAA8D8EGP+Eo7AAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAi\nLAEAAEgRlgAAAKQISwAAAFKEJQAAACnCEgAAgJRa1QNAsyqKqiegkZVl1RMAAIyfsIQLRBgAADBZ\nOAoLAABAirAEAAAgRVgCAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQA\nACBFWAIAAJBSq3oAAACAeoqi6gnOTVlWPcHFIywBAIAJbTIFWqNyFBYAAIAUYQkAAECKsAQAACBF\nWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkFKregAm\nrqKoegKaWVlWPQEAAOeLsGRUbvwBAIDxcBQWAACAFGEJAABAirAEAAAgRVgCAACQIiwBAABIEZYA\nAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJBSq3oAGI+iqHoCGJ+yrHoCAICL\nT1jSENysAwDAxOUoLAAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAA\nUoQlAAAAKcISAACAFGEJAABAirAEAAAgpVb1AAAAQERRVD0Bza4sL9y1hSUAAEwAF/KmHy40R2EB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQI\nSwAAAFKEJQAAACm1qgcAAAAiiqLqCSaHsqx6guYkLAEAYAIQPDQyR2EBAABIEZYAAACkCEsAAABS\nhCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAAACm1qgcA\nAGgmRVH1BOemLKueAGhkwhIA4DwSaMBk5CgsAAAAKcISAACAFGEJAABAirAEAAAgRVgCAACQIiwB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACClVvUAAHCxFUXVE3C+lWXVEwBM\nbsISgElHhADA+eUoLAAAACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkCIsAQAASBGWAAAApAhLAAAA\nUoQlAAAAKcISAACAFGEJAABAirAEAAAgpVb1AAAAwPgURdUTUIWyrHqCsQlLAABoEI0QGExOjsIC\nAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgR\nlgAAAKQISwAAAFJqVQ8AAABQT1FUPcHEV5bV/vvCEgAAmNCqjibG5igsAAAAKcISAACAFGEJAABA\nirAEAAAgRVgCAACQIiwBAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACClVvUA\nMNEURdUTwPiUZdUTAAD8RVjC37hZBwCAf8ZRWAAAAFKEJQAAACnCEgAAgBRhCQAAQIqwBAAAIEVY\nAgAAkCIsAQAASBGWAAAApAhLAAAAUoQlAAAAKcISAACAFGEJAABASq3qAQAAmklRVD0B/0RZVj0B\nNAdhCQBwHgkVYDJyFBYAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAAAFKEJQAA\nACnCEgAAgBRhCQAAQIqwBAAAIEVYAgAAkFKregCgsRRF1RMwUZVl1RMAAFURlsA/Ih4AAPg7R2EB\nAABIEZYAAACkCEsAAABShCUAAAApwhIAAIAUYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQI\nSwAAAFKEJQAAACm1qgcA8oqi6gmYqMqy6gkAgMlAWEITEA8AAFTJUVgAAABShCUAAAApwhIAAIAU\nYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISyaVjz/+uOoR4LywyzQDe0yzsMsgLJlkfOOn\nWdhlmoE9plnYZRCWAAAAJAlLAAAAUoqyLMvxPLGrqyv27dt3oecBAACgAgsWLIi9e/ee09eOOywB\nAADg/3EUFgAAgBRhCQAAQMqYYdnX1xcdHR0xZ86cePbZZy/GTHBeDA0NxV133RXz5s2LG2+8MV5+\n+eWIiDh27FgsWbIkbrjhhrj33nvj+PHjFU8KYxsZGYmFCxfG0qVLI8Ie05iOHz8eK1asiLlz50Zn\nZ2d88cUXdpmGs3nz5pg3b17Mnz8/Hn300fj999/tMQ1hzZo10draGvPnzz/zWL3d3bx5c8yZMyc6\nOjriww8/HPP6dcNyZGQkHn/88ejr64v9+/fH22+/HQcOHEi8HLh4Wlpa4sUXX4xvv/02du/eHa+8\n8kocOHAgtmzZEkuWLImDBw/GPffcE1u2bKl6VBhTT09PdHZ2RlEUERH2mIb0xBNPxP333x8HDhyI\nr7/+Ojo6OuwyDWVwcDBeffXV6O/vj2+++SZGRkZi69at9piGsHr16ujr6zvrsdF2d//+/bFt27bY\nv39/9PX1xfr16+PPP/+se/26Yblnz56YPXt2tLe3R0tLSzzyyCOxffv25EuCi2P69OnR1dUVERGX\nXnppzJ07N4aHh2PHjh2xatWqiIhYtWpVvPvuu1WOCWM6fPhwvP/++7Fu3br4z/+3Zo9pND///HN8\n8sknsWbNmoiIqNVqccUVV9hlGsrll18eLS0tcfLkyTh9+nScPHkyZsyYYY9pCLfffntceeWVZz02\n2u5u3749uru7o6WlJdrb22P27NmxZ8+eutevG5bDw8Mxa9asMx+3tbXF8PDwOb0QqNLg4GB89dVX\nceutt8bRo0ejtbU1IiJaW1vj6NGjFU8H9T355JPx/PPPx5Qp//2WbY9pNAMDA3HNNdfE6tWrY9Gi\nRfHYY4/Fr7/+apdpKFdddVU89dRTce2118aMGTNi6tSpsWTJEntMwxptd48cORJtbW1nnjeeDqwb\nlv85cgWN7MSJE7F8+fLo6emJyy677KzPFUVhz5nQ3nvvvZg2bVosXLgwRnt3KHtMIzh9+nT09/fH\n+vXro7+/Py655JL/OS5ol5novvvuu3jppZdicHAwjhw5EidOnIi33nrrrOfYYxrVWLs71l7XDcuZ\nM2fG0NDQmY+HhobOKleY6P74449Yvnx5rFy5Mh588MGI+OunMT/++GNERPzwww8xbdq0KkeEuj77\n7LPYsWNHXHfdddHd3R0fffRRrFy50h7TcNra2qKtrS1uueWWiIhYsWJF9Pf3x/Tp0+0yDePLL7+M\n2267La6++uqo1Wrx0EMPxeeff26PaVij3U/8vQMPHz4cM2fOrHutumF58803x6FDh2JwcDBOnToV\n27Zti2XLlmXnh4uiLMtYu3ZtdHZ2xoYNG848vmzZsujt7Y2IiN7e3jPBCRPRpk2bYmhoKAYGBmLr\n1q1x9913x5tvvmmPaTjTp0+PWbNmxcGDByMiYufOnTFv3rxYunSpXaZhdHR0xO7du+O3336Lsixj\n586d0dnZaY9pWKPdTyxbtiy2bt0ap06dioGBgTh06FAsXry47rWKcrSzVf/2wQcfxIYNG2JkZCTW\nrl0bTz/99Hl6GXBhffrpp3HHHXfETTfddOZX95s3b47FixfHww8/HN9//320t7fHO++8E1OnTq14\nWhjbrl274oUXXogdO3bEsWPH7DENZ9++fbFu3bo4depUXH/99fHGG2/EyMiIXaahPPfcc9Hb2xtT\npkyJRYsWxWuvvRa//PKLPWbC6+7ujl27dsVPP/0Ura2t8cwzz8QDDzww6u5u2rQpXn/99ajVatHT\n0xP33Xdf3euPGZYAAABQT92jsAAAADAWYQkAAECKsAQAACBFWAIAAJAiLAEAAEgRlgAAAKQISwAA\nAFKEJQAAACn/AoMq5KDi0u1fAAAAAElFTkSuQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x2d30790>"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAA5YAAABUCAYAAAD5w6hcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAB9hJREFUeJzt3V9o1fXjx/HXZLvqnxW5oTMWacwtc0oZBEV/WEHgipRo\ngYh/upEgo6vupAtnRdSCropiFDS7yhE1QiIpyiSWK9pAiY3mLCHEyIyW6/wufr+vP/z9vm5+fVvH\nsx6Pux3PPrwPvBjnqZ956iqVSiUAAABwnuZV+wAAAADUNmEJAABAEWEJAABAEWEJAABAEWEJAABA\nEWEJAABAkfpzfWJHR0eGh4f/yrMAAABQJStWrMiBAwfO63vrzvVzLOvq6uIjL6l127dvz/bt26t9\nDChmy8wFdsxcYcvMFSXN51ZYAAAAighLAAAAighL/lHuvPPOah8BLghbZi6wY+YKWwa/YwkAAED8\njiUAAABVJCwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwB\nAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAoIiwBAAAo\nIiwBAAAoIiwBAAAoIiwBAAAoUl/tAwBQ++rqqn2C/1ylUu0TcKFcjPuzr9pgO3DhCEsAinkjRDXZ\nH+fLduDCcSssAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQl\nAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQlAAAA\nRYQlAAAARYQlAAAARYQlAAAARYQlAAAARYQl/ygff/xxtY8AF4QtMxfYMXOFLYOw5B/GD37mCltm\nLrBj5gpbBmEJAABAIWEJAABAkbpKpVI5lyd2dHRkeHj4rz4PAAAAVbBixYocOHDgvL73nMMSAAAA\n/h23wgIAAFBEWAIAAFBk1rAcHBxMa2trli5dmmefffbvOBNcEBMTE7nrrrvS3t6eG2+8MS+//HKS\n5NixY+ns7MwNN9yQe++9N8ePH6/ySWF209PTWblyZdasWZPEjqlNx48fz7p167Js2bK0tbXliy++\nsGVqTk9PT9rb27N8+fI8+uij+f333+2YmrBp06Y0NjZm+fLlpx+babs9PT1ZunRpWltb8+GHH856\n/RnDcnp6Oo8//ngGBwczMjKSt99+O6OjowUvB/4+DQ0NefHFF/Ptt99m3759eeWVVzI6OpqdO3em\ns7MzBw8ezD333JOdO3dW+6gwq97e3rS1taWuri5J7Jia9MQTT+T+++/P6Ohovv7667S2ttoyNWV8\nfDyvvvpqhoaG8s0332R6ejr9/f12TE3YuHFjBgcHz3jsbNsdGRnJrl27MjIyksHBwWzdujV//vnn\njNefMSz379+fJUuWpKWlJQ0NDXnkkUeye/fuwpcEf4+mpqZ0dHQkSS699NIsW7Ysk5OTGRgYyIYN\nG5IkGzZsyLvvvlvNY8KsDh8+nPfffz9btmzJv/6/NTum1vz888/55JNPsmnTpiRJfX19rrjiClum\nplx++eVpaGjIyZMnc+rUqZw8eTILFy60Y2rC7bffniuvvPKMx8623d27d6e7uzsNDQ1paWnJkiVL\nsn///hmvP2NYTk5OZvHixae/bm5uzuTk5Hm9EKim8fHxfPXVV7n11ltz9OjRNDY2JkkaGxtz9OjR\nKp8OZvbkk0/m+eefz7x5//sj246pNWNjY7nmmmuycePGrFq1Ko899lh+/fVXW6amXHXVVXnqqady\n7bXXZuHChZk/f346OzvtmJp1tu0eOXIkzc3Np593Lh04Y1j+65YrqGUnTpzI2rVr09vbm8suu+yM\nP6urq7NzLmrvvfdeFixYkJUrV+Zsnw5lx9SCU6dOZWhoKFu3bs3Q0FAuueSS/3e7oC1zsfvuu+/y\n0ksvZXx8PEeOHMmJEyfy1ltvnfEcO6ZWzbbd2XY9Y1guWrQoExMTp7+emJg4o1zhYvfHH39k7dq1\nWb9+fR588MEk//23MT/++GOS5IcffsiCBQuqeUSY0WeffZaBgYFcd9116e7uzkcffZT169fbMTWn\nubk5zc3NueWWW5Ik69aty9DQUJqammyZmvHll1/mtttuy9VXX536+vo89NBD+fzzz+2YmnW29xP/\ntwMPHz6cRYsWzXitGcPy5ptvzqFDhzI+Pp6pqans2rUrXV1dpeeHv0WlUsnmzZvT1taWbdu2nX68\nq6srfX19SZK+vr7TwQkXox07dmRiYiJjY2Pp7+/P3XffnTfffNOOqTlNTU1ZvHhxDh48mCTZs2dP\n2tvbs2bNGlumZrS2tmbfvn357bffUqlUsmfPnrS1tdkxNets7ye6urrS39+fqampjI2N5dChQ1m9\nevWM16qrnO3eqv/xwQcfZNu2bZmens7mzZvz9NNPX6CXAX+tTz/9NHfccUduuumm0/9039PTk9Wr\nV+fhhx/O999/n5aWlrzzzjuZP39+lU8Ls9u7d29eeOGFDAwM5NixY3ZMzRkeHs6WLVsyNTWV66+/\nPm+88Uamp6dtmZry3HPPpa+vL/PmzcuqVavy2muv5ZdffrFjLnrd3d3Zu3dvfvrppzQ2NuaZZ57J\nAw88cNbt7tixI6+//nrq6+vT29ub++67b8brzxqWAAAAMJMZb4UFAACA2QhLAAAAighLAAAAighL\nAAAAighLAAAAighLAAAAighLAAAAighLAAAAivwX3yizMiNlZnwAAAAASUVORK5CYII=\n",
       "text": [
        "<matplotlib.figure.Figure at 0x2d30b90>"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Overlap-relative centers"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The algorithm only has to be modified slightly to report the overlap-relative centers. We accumulate the gap sizes to correct for them in the reported positions."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def overlap_relative_centers(regions):\n",
      "    regions = sorted(regions)\n",
      "\n",
      "    centers = []\n",
      "    gapsize = 0\n",
      "    gap_x = 0\n",
      "\n",
      "    for x, y in regions:\n",
      "        if gap_x < x:\n",
      "            gapsize += x - gap_x\n",
      "        gap_x = max(gap_x, y)\n",
      "\n",
      "        centers.append((y - x) // 2 + x - gapsize)\n",
      "\n",
      "    return centers"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "overlap_relative_centers(regions)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "[8, 13, 16, 17, 19, 22, 36, 45, 49, 60, 63, 63, 62, 65, 67]"
       ]
      }
     ],
     "prompt_number": 8
    }
   ],
   "metadata": {}
  }
 ]
}