compute_intersection_single_element.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import numba\n",
    "from numba import jit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# @jit(nopython=True, parallel=True)\n",
    "def compute_intersection_single_element(x1,y1, x2,y2, x3,y3, x4,y4, \n",
    "                                        delta_x_tolerance=1e-6, grad_diff_tolerance=1e-6,\n",
    "                                       verbose=False):\n",
    "    \n",
    "    \n",
    "    inf_slope_status = np.array([0,0], np.int32)\n",
    "    parallel_flag = False # for readability\n",
    "    # check line 1 conditions\n",
    "    dx_line_1 = x2 - x1\n",
    "    dy_line_1 = y2 - y1\n",
    "    if np.abs(dx_line_1) < delta_x_tolerance:\n",
    "        inf_slope_status[0] = 1\n",
    "    \n",
    "    # check line 2 conditions\n",
    "    dx_line_2 = x4 - x3\n",
    "    dy_line_2 = y4 - y3\n",
    "    if np.abs(dx_line_2) < delta_x_tolerance:\n",
    "        inf_slope_status[1] = 1\n",
    "    \n",
    "    # if both have inf slope, they are parallel\n",
    "    parallel_flag = (np.sum(inf_slope_status) == 2)\n",
    "    if parallel_flag:\n",
    "        if verbose:\n",
    "            print(\"compute_intersection_single_element: Lines are parallel and have inf slope\")\n",
    "        return (-9999,-9999) # this value is chosen as it will be outside \n",
    "                             #  of our detection range (to be filtered later)\n",
    "    \n",
    "    # since one is inf and the other is not, they are not parallel\n",
    "    if (np.sum(inf_slope_status) > 0):\n",
    "        # there is one line that has inf slope\n",
    "        if (inf_slope_status[0] == 1): # line one has infinite slope\n",
    "            x = x1 # pick either one point x1 or x2 as they are the \"equal\"\n",
    "            y = (x - x3)*(y4-y3) / (x4-x3) + y3\n",
    "            if verbose:\n",
    "                print(\"compute_intersection_single_element: Line1 has inf slope\")\n",
    "            return (x, y)\n",
    "        \n",
    "        if (inf_slope_status[1] == 1):\n",
    "            x = x3 # pick either one point x3 or x4 as they are the \"equal\"\n",
    "            y = (x - x1)*(y2-y1) / (x2-x1) + y1\n",
    "            if verbose:\n",
    "                print(\"compute_intersection_single_element: Line2 has inf slope\")\n",
    "            return (x, y)\n",
    "            \n",
    "    else:\n",
    "        \n",
    "        # check both line conditions\n",
    "        m1 = dy_line_1 / dx_line_1\n",
    "        m2 = dy_line_2 / dx_line_2\n",
    "\n",
    "        # Note: if the two lines are collinear, they are parallel\n",
    "        if np.abs(m1 - m2) < grad_diff_tolerance:\n",
    "            parallel_flag = True\n",
    "\n",
    "\n",
    "        if parallel_flag:\n",
    "            if verbose:\n",
    "                print(\"compute_intersection_single_element: Lines are parallel\")\n",
    "            return (-9999,-9999) # this value is chosen as it will be outside \n",
    "                                 #  of our detection range (to be filtered later)\n",
    "\n",
    "        if verbose:\n",
    "            print(\"compute_intersection_single_element: No line has inf slope\")\n",
    "\n",
    "        x = (m2 *x4 - m1* x2 - y4 + y2) / (m2 - m1)\n",
    "        y = m2 * (x - x4) + y4\n",
    "        return (x, y)\n",
    "    \n",
    "    raise ValueError # np.sum(inf_slope_status) is abnormal\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# from PointPillar\n",
    "def compute_intersection_single_element(x1,y1, x2,y2, x3,y3, x4,y4, verbose=True):\n",
    "    num = (x1*y2 - y1*x2) * (x3-x4) - (x1-x2) * (x3*y4 - y3*x4);\n",
    "    den = (x1-x2) * (y3-y4) - (y1-y2) * (x3-x4);\n",
    "    x = num/(den + 1e-6)\n",
    "    \n",
    "    num = (x1*y2 - y1*x2) * (y3-y4) - (y1-y2) * (x3*y4 - y3*x4);\n",
    "    den = (x1-x2) * (y3-y4) - (y1-y2) * (x3-x4);\n",
    "    y = num/(den + 1e-6)\n",
    "    return (x,y)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TestCase1i\n",
      "(0.0, -8000000.0)\n",
      "TestCase2i\n",
      "(30000000.0, -30000000.0)\n",
      "TestCase3i\n",
      "(-0.0, 1.0000000185185187)\n",
      "TestCase3ii\n",
      "(0.8333333391203704, 1.1666666747685186)\n",
      "TestCase4i\n",
      "(0.8333333564814821, 1.1666666990740748)\n",
      "TestCase4ii\n",
      "(0.8333333101851859, 1.1666666342592602)\n",
      "TestCase5i\n",
      "(5.000000050000001, 2.0000000200000003)\n",
      "TestCase5ii\n",
      "(4.99999995, 1.9999999800000003)\n",
      "TestCase6i\n",
      "(5.000000125000003, 2.000000050000001)\n",
      "TestCase6ii\n",
      "(4.999999875000004, 1.9999999500000014)\n"
     ]
    }
   ],
   "source": [
    "# test the compute_intersection_single_element:\n",
    "# test cases:\n",
    "#     1. two lines have inf slope, both lines are parallel\n",
    "#     2. no line has inf slope, both lines are parallel\n",
    "#     3. two lines intersect internally, both lines are not parallel, no line has inf slope\n",
    "#     4. two lines intersect externally, both lines are not parallel, no line has inf slope\n",
    "#     5. two lines intersect internally, both lines are not parallel, 1 line has inf slope\n",
    "#     6. two lines intersect externally, both lines are not parallel, 1 line has inf slope\n",
    "#     7. two lines intersect internally, both lines are not parallel, one line has 0 slope\n",
    "#     8. two lines intersect externally, both lines are not parallel, one line has 0 slope\n",
    "#     9. two lines intersect internally, both lines are not parallel, 1 line has inf slope, 1 line has 0 slope\n",
    "#     10. two lines intersect externally, both lines are not parallel, 1 line has inf slope, 1 line has 0 slope\n",
    "\n",
    "# case 1 (i)\n",
    "class TestCase1i():\n",
    "    line1 = (-2, 1, -2, 3)\n",
    "    line2 = (-6, 2, -6, 3)\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test1i = TestCase1i()\n",
    "\n",
    "class TestCase2i():\n",
    "    line1 = (0, 2, 2, 0)\n",
    "    line2 = (-3, 0, 0, -3)\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test2i = TestCase2i()\n",
    "\n",
    "\n",
    "class TestCase3i():\n",
    "    line1 = (-2, -1, 1, 2)\n",
    "    line2 = (-4, 5, 5, -4)\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test3i = TestCase3i()\n",
    "\n",
    "\n",
    "\n",
    "class TestCase3ii():\n",
    "    line1 = (-10, -1, 5, 2)\n",
    "    line2 = (-4, 6, 4, -2)\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test3ii = TestCase3ii()\n",
    "\n",
    "\n",
    "\n",
    "class TestCase4i():\n",
    "    line1 = (-10, -1, 5, 2)\n",
    "    line2 = (-4, 6, -2, 4)\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "#         intersection = compute_intersection_single_element(*self.line2, *self.line1, verbose=True)\n",
    "#         print(intersection)\n",
    "\n",
    "test4i = TestCase4i()\n",
    "\n",
    "class TestCase4ii():\n",
    "    line1 = (-10, -1, 5, 2)\n",
    "    line2 = (-2, 4, -4, 6) # reverse the order of points\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "#         intersection = compute_intersection_single_element(*self.line2, *self.line1, verbose=True)\n",
    "#         print(intersection)\n",
    "\n",
    "test4ii = TestCase4ii()\n",
    "\n",
    "class TestCase5i():\n",
    "    line1 = (-10, -1, 15, 4)\n",
    "    line2 = (5, 4, 5, 0) # inf slope\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test5i = TestCase5i()\n",
    "\n",
    "class TestCase5ii():\n",
    "    line1 = (5, 4, 5, 0) # inf slope\n",
    "    line2 = (-10, -1, 15, 4)\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test5ii = TestCase5ii()\n",
    "\n",
    "class TestCase6i():\n",
    "    line1 = (-10, -1, 0, 1)\n",
    "    line2 = (5, 4, 5, 0) # inf slope\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test6i = TestCase6i()\n",
    "\n",
    "class TestCase6ii():\n",
    "    line1 = (5, 4, 5, 0) # inf slope\n",
    "    line2 = (-10, -1, 0, 1)\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test6ii = TestCase6ii()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TestCase7i\n",
      "(1.4999999750000004, 3.9999999333333345)\n",
      "TestCase7ii\n",
      "(1.5000000250000003, 4.000000066666668)\n",
      "TestCase8i\n",
      "(1.4999999250000036, 3.9999998000000097)\n",
      "TestCase9i\n",
      "(3.0000000375000004, 4.000000050000001)\n",
      "TestCase10i\n",
      "(3.0000001500000075, 4.00000020000001)\n"
     ]
    }
   ],
   "source": [
    "# Test cases\n",
    "#     7. two lines intersect internally, both lines are not parallel, one line has 0 slope\n",
    "#     8. two lines intersect externally, both lines are not parallel, one line has 0 slope\n",
    "#     9. two lines intersect internally, both lines are not parallel, 1 line has inf slope, 1 line has 0 slope\n",
    "#     10. two lines intersect externally, both lines are not parallel, 1 line has inf slope, 1 line has 0 slope\n",
    "\n",
    "\n",
    "class TestCase7i():\n",
    "    line1 = (-2, -3, 4, 9)\n",
    "    line2 = (5, 4, 0, 4) # 0 slope\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test7i = TestCase7i()\n",
    "\n",
    "class TestCase7ii():\n",
    "    line1 = (5, 4, 0, 4) # 0 slope\n",
    "    line2 = (-2, -3, 4, 9)\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test7ii = TestCase7ii()\n",
    "\n",
    "class TestCase8i():\n",
    "    line1 = (-2, -3, 0, 1)\n",
    "    line2 = (5, 4, 0, 4) # 0 slope\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test8i = TestCase8i()\n",
    "\n",
    "\n",
    "class TestCase9i():\n",
    "    line1 = (-2, 4, 6, 4)\n",
    "    line2 = (3, 6, 3, -4) # 0 slope\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test9i = TestCase9i()\n",
    "\n",
    "class TestCase10i():\n",
    "    line1 = (-2, 4, 0, 4)\n",
    "    line2 = (3, 6, 3, -4) # 0 slope\n",
    "    \n",
    "    def __init__(self):\n",
    "        print(type(self).__name__)\n",
    "        intersection = compute_intersection_single_element(*self.line1, *self.line2, verbose=True)\n",
    "        print(intersection)\n",
    "\n",
    "test10i = TestCase10i()"
   ]
  }
 ],
 "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}