PA1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PA1: Poly2mask\n",
    "\n",
    "实现扫描线将给定的多边形转变为梯形mask, 辅助函数和整体框架已实现, 请填补`poly2mask`函数中缺失的部分, 最终效果如下图:\n",
    "![pa1_show](./data/pa1_show.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from PIL import Image\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`line_inter`求直线AB和CD的交点.\n",
    "\n",
    "`get_trapezoids`接收相邻两条扫描线和多边形的交点`bottom_inter`(下底交点)/`top_inter`(上底交点), 返回两条扫描线之间能构成的梯形列表."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def line_inter(A, B, C, D):\n",
    "    return A + (B - A) * np.cross(C - A, D - C) / np.cross(B - A, D - C)\n",
    "\n",
    "\n",
    "def get_trapezoids(top_inter, bottom_inter):\n",
    "    assert len(top_inter) % 2 == 0 and len(top_inter) == len(bottom_inter)\n",
    "\n",
    "    if len(top_inter) == 0:\n",
    "        return []\n",
    "\n",
    "    top_inter = top_inter[np.argsort(top_inter[:, 0])]\n",
    "    bottom_inter = bottom_inter[np.argsort(bottom_inter[:, 0])]\n",
    "\n",
    "    trape_list = list()\n",
    "    for i in range(0, len(bottom_inter), 2):\n",
    "        trape_list.append(\n",
    "            np.concatenate([top_inter[[i, i + 1]], bottom_inter[[i + 1, i]]])\n",
    "        )\n",
    "    return trape_list\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`poly2mask`流程:\n",
    "1. 接收多边形`poly`, 将顶点按照Y从小到大排序, 遍历顶点.\n",
    "2. 利用`line_inter`函数求当前扫描线作为梯形上底时和多边形的交点`top_inter`.\n",
    "3. (当前扫描线为首条时跳过此步) 由上一条扫描线作为梯形下底, 当前扫描线作为梯形上底, 调用`get_trapezoids`函数得到当前扫描线和上一条扫描线之间的梯形.\n",
    "4. 更新当前顶点`idx`相邻的边: 若已遍历过从`edge_set`中删除, 未遍历过则加入`edge_set`.\n",
    "5. 利用`line_inter`函数求当前扫描线作为梯形下底时和多边形的交点`bottom_inter` (遍历到下条扫描线时才会用到)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def poly2mask(poly):\n",
    "    N = len(poly)\n",
    "\n",
    "    # Q1: sort indices of vertices by Y (use np.argsort)\n",
    "    sorted_indices = None\n",
    "\n",
    "    edge_set = set()\n",
    "    trape_list = list()\n",
    "    bottom_inter = None\n",
    "\n",
    "    for idx in sorted_indices:\n",
    "        cur_y = poly[idx][1]\n",
    "\n",
    "        top_inter = list()\n",
    "        for e in edge_set:\n",
    "            # Q2: get intersection of edge e and line Y = cur_y\n",
    "            inter = None\n",
    "            top_inter.append(inter)\n",
    "\n",
    "        if bottom_inter:\n",
    "            trape_list.extend(\n",
    "                get_trapezoids(np.stack(bottom_inter), np.stack(top_inter))\n",
    "            )\n",
    "\n",
    "        le_idx = (idx + N - 1) % N  # left neighbor vertex\n",
    "        if poly[le_idx, 1] <= cur_y:  # if the left edge is lower than cur_y\n",
    "            # Q3: remove edge le_idx from edge_set\n",
    "            pass\n",
    "        else:\n",
    "            # Q4: add edge le_idx into edge_set\n",
    "            pass\n",
    "\n",
    "        ri_idx = (idx + 1) % N  # right neighbor vertex\n",
    "        if poly[ri_idx, 1] <= cur_y:  # if the right edge is lower than cur_y\n",
    "            # Q5: remove edge idx from edge_set\n",
    "            pass\n",
    "        else:\n",
    "            # Q6: add edge le_idx into edge_set\n",
    "            pass\n",
    "\n",
    "        bottom_inter = list()\n",
    "        for e in edge_set:\n",
    "            # Q7: get intersection of edge e and line y = cur_y\n",
    "            inter = None\n",
    "            bottom_inter.append(inter)\n",
    "\n",
    "    return trape_list\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行下面代码块得到可视化结果, 验证代码实现的正确性."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "img = Image.open(\"./data/pa1.png\")\n",
    "with open(\"./data/pa1.txt\", \"r\") as f:\n",
    "    poly = []\n",
    "    for line in f.readlines():\n",
    "        x, y = map(int, line.split(\",\"))\n",
    "        poly.append([x, y])\n",
    "    poly = np.array(poly)\n",
    "\n",
    "ax = plt.subplots(1, 2, figsize=(15, 15))[1]\n",
    "ax[0].imshow(img)\n",
    "ax[0].plot(poly[:, 0], poly[:, 1], linewidth=5)\n",
    "\n",
    "ax[1].imshow(img)\n",
    "trape_list = poly2mask(poly)\n",
    "for tr in trape_list:\n",
    "    ax[1].fill(tr[:, 0], tr[:, 1], alpha=0.8)\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7.13 ('tvm': venv)",
   "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.13"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "341a80c59a3ec9d769ab0e0928ba401a5b9b98de67015334e0ba45c81c270ad5"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}