{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Arrangements and Visibility"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from skgeom import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this chapter we create a 2D arrangement, and explore how to use it in order to compute the visibility from different positions inside this arrangement.\n",
    "\n",
    "A 2D arrangement consists of vertices, segments, and faces.\n",
    "\n",
    "We can use the `insert`, and `insert_point` function on the arrangement to insert new points into it.\n",
    "\n",
    "Then, the arrangement can be queried or iterated upon by using either the `find` function or the iterators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = 10\n",
    "outer = [\n",
    "    Segment2(Point2(-M, -M), Point2(-M, M)), Segment2(Point2(-M, M), Point2(M, M)),\n",
    "    Segment2(Point2(M, M), Point2(M, -M)), Segment2(Point2(M, -M), Point2(-M, -M))\n",
    "]\n",
    "\n",
    "segments = [\n",
    "    Segment2(Point2(0, 0), Point2(0, 4)), Segment2(Point2(2, 4), Point2(8, 4)),\n",
    "    Segment2(Point2(3, 4), Point2(-8, 0)), Segment2(Point2(1, 0), Point2(0, 5)),\n",
    "]\n",
    "arr = arrangement.Arrangement()\n",
    "\n",
    "for s in outer:\n",
    "    arr.insert(s)\n",
    "\n",
    "for s in segments:\n",
    "    arr.insert(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the arrangement can be iterated upon with the `halfedges` iterator property. Note that the segments that have been inserted are split at their intersections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for he in arr.halfedges:\n",
    "    draw.draw(he.curve())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding things in the arrangement\n",
    "\n",
    "We can find the face associated with a certain point in the arrangement, and use the `outer_ccb` circulator to iterate over the halfedges associated with the face."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Point2(-2.5, 5)\n",
    "face = arr.find(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "i = face.outer_ccb\n",
    "first = next(i)\n",
    "halfedge = next(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while first != halfedge:\n",
    "    print(halfedge.source().point(), halfedge.target().point())\n",
    "    halfedge = next(i)\n",
    "print(halfedge.source().point(), halfedge.target().point())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, if we query a point that is lying on a halfedge, or a vertex itself we get either a halfedge or a vertex in return."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vertex = arr.find(Point2(0, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vertex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Computing Visibility\n",
    "\n",
    "We can use the `RotationalSweepVisibility` class to compute the visibility from a specific point inside the arrangement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vs = RotationalSweepVisibility(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Point2(-2.5, 5)\n",
    "face = arr.find(q)\n",
    "vx = vs.compute_visibility(q, face)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for he in arr.halfedges:\n",
    "    draw.draw(he.curve(), visible_point=False)\n",
    "for v in vx.halfedges:\n",
    "    draw.draw(v.curve(), color='red', visible_point=False)\n",
    "    \n",
    "draw.draw(q, color='magenta')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An additional, faster method to compute the visibility is also available, the `TriangularExpansionVisibility`.\n",
    "However, the `TriangularExpansionVisibility` requires a one-time initialization cost to be paid. You can read more about both algorithms here: https://doc.cgal.org/latest/Visibility_2/index.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ts = RotationalSweepVisibility(arr)\n",
    "tx = ts.compute_visibility(q, face)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for he in arr.halfedges:\n",
    "    draw.draw(he.curve(), visible_point=False)\n",
    "for v in tx.halfedges:\n",
    "    draw.draw(v.curve(), color='red', visible_point=False)\n",
    "    \n",
    "draw.draw(q, color='magenta')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}