345 [Hard] 2D Triangle Mesh Generator.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "pseudo\n",
    "\n",
    "    sort points along axis\n",
    "    \n",
    "    take first 2 points and create convex hull\n",
    "    \n",
    "    for each other point\n",
    "        find r tangent\n",
    "        find l tangent\n",
    "            add all edges between point and points []between r and l\n",
    "            remove points ][ between r and l and replace with new point\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list,\n",
       "            {(0, 0): [(0, 6), (2, 2), (4, 2), (6, 0)],\n",
       "             (0, 6): [(0, 0), (2, 2), (2, 4), (4, 2), (4, 4), (6, 6)],\n",
       "             (2, 2): [(0, 6), (0, 0), (2, 4), (4, 2)],\n",
       "             (2, 4): [(0, 6), (2, 2), (4, 2)],\n",
       "             (4, 2): [(0, 6), (2, 4), (2, 2), (0, 0), (4, 4), (6, 0)],\n",
       "             (4, 4): [(0, 6), (4, 2), (6, 0), (6, 6)],\n",
       "             (6, 0): [(4, 4), (4, 2), (0, 0), (6, 6)],\n",
       "             (6, 6): [(0, 6), (4, 4), (6, 0)]})"
      ]
     },
     "execution_count": 170,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class triangulate():\n",
    "    \n",
    "    def __init__(self,inx):\n",
    "        # input format\n",
    "        linx = inx.split('\\n')\n",
    "        self.points = [tuple(int(x) for x in z.split(' ')[:2]) for z in linx[1:]]\n",
    "        # sort along axis\n",
    "        self.points.sort(key = lambda x:(x[0],x[1]))  \n",
    "        self.edges = defaultdict(list)\n",
    "        # hull\n",
    "        self.H = self.points[:2] + self.points[:1]\n",
    "        self.n = len(self.H)\n",
    "        # possible tangents\n",
    "        self.T = {'top':{(0,-1),(-1,-1)},'bottom':{(1,1),(1,0)}}\n",
    "        \n",
    "    def tang(self,a,b,P):\n",
    "        # P below,on or above line a-b\n",
    "        t = (P[0]-b[0])*(a[1]-b[1]) - (a[0]-b[0])*(P[1]-b[1]) \n",
    "        if t > 0: return 1\n",
    "        if not t: return 0\n",
    "        return -1\n",
    "       \n",
    "    def binary_search_hull(self,P,direction):\n",
    "        sol = self.T[direction]\n",
    "        # test Hull[0]\n",
    "        if (self.tang(self.H[0],self.H[-2],P), self.tang(self.H[0],self.H[1],P)) in sol:\n",
    "            return 0\n",
    "        \n",
    "        start = 0\n",
    "        end = self.n - 1\n",
    "        while True:\n",
    "            mid = (start+end)//2\n",
    "            t_in = self.tang(self.H[mid],self.H[mid-1],P)\n",
    "            t_out = self.tang(self.H[mid],self.H[mid+1],P)        \n",
    "            if (t_in,t_out) in sol:\n",
    "                return mid\n",
    "            \n",
    "            next_start = self.tang(self.H[start+1],P,self.H[start])\n",
    "            start_mid = self.tang(self.H[start],P,self.H[mid]) \n",
    "            if direction == 'top':\n",
    "                if next_start == 1:\n",
    "                    if t_out == -1 or start_mid == 1: end = mid\n",
    "                    else: start = mid\n",
    "                else:\n",
    "                    if t_out >= 0 or start_mid >= 0: start = mid\n",
    "                    else: end = mid\n",
    "            else:\n",
    "                if next_start == -1:\n",
    "                    if t_out >= 0 or start_mid == -1: end = mid\n",
    "                    else: start = mid\n",
    "                else:\n",
    "                    if t_out == -1 or start_mid <= 0: start = mid\n",
    "                    else: end = mid    \n",
    "                    \n",
    "    def polygon_tangents(self,P):\n",
    "        b = self.binary_search_hull(P,'bottom')\n",
    "        t = self.binary_search_hull(P,'top')\n",
    "        return b,t\n",
    "\n",
    "    def grow_hull(self,P):\n",
    "        # intial n > 2 points colinear\n",
    "        if len(self.H) == 3: \n",
    "            if P[0] == self.H[0][0] == self.H[1][0]:\n",
    "                self.H[1] = point\n",
    "                pass \n",
    "            else:\n",
    "                # initial edges\n",
    "                for x,y in zip(self.H[:2],self.H[:2][::-1]):\n",
    "                    self.edges[x].append(y)           \n",
    "        b,t = self.polygon_tangents(P)\n",
    "        if b < t:\n",
    "            for x in self.H[b:t+1]:\n",
    "                self.edges[x].append(P)\n",
    "                self.edges[P].append(x)\n",
    "            self.H[b+1:t] = []\n",
    "        else:\n",
    "            for x in self.H[b:-1]+self.H[:1]:\n",
    "                self.edges[x].append(P)\n",
    "                self.edges[P].append(x)\n",
    "            self.H[b+1:-1] = []\n",
    "        self.H.insert(b+1,P)\n",
    "        self.n = len(self.H)\n",
    "        pass \n",
    "\n",
    "    def solve(self):\n",
    "        for P in self.points[2:]:\n",
    "            self.grow_hull(P)\n",
    "        return self.edges\n",
    "\n",
    "inx = '8\\n0 0 \\n0 6 \\n6 0 \\n6 6 \\n2 2 \\n2 4 \\n4 2 \\n4 4'\n",
    "\n",
    "problem = triangulate(inx)\n",
    "problem.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 1: 279 µs per loop\n"
     ]
    }
   ],
   "source": [
    "problem = triangulate(inx)\n",
    "\n",
    "%timeit -n1 -r1 problem.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from math import floor\n",
    "L = [' '.join(list(map(str,[floor(random.random()*10000),floor(random.random()*10000)]))) for x in range(1000)]\n",
    "inx = '1000\\n'+'\\n'.join(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 1: 113 ms per loop\n"
     ]
    }
   ],
   "source": [
    "problem = triangulate(inx)\n",
    "\n",
    "%timeit -n1 -r1 problem.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 747),\n",
       " (11, 984),\n",
       " (116, 985),\n",
       " (142, 943),\n",
       " (159, 337),\n",
       " (159, 209),\n",
       " (154, 29),\n",
       " (88, 7),\n",
       " (4, 59),\n",
       " (1, 747)]"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "problem.H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "48"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(problem.edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(159, 862)"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "problem.points[48]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}