{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Triângulo de Sierpinski\n",
    "\n",
    "O [Triângulo de Sierpinski](https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle), também conhecido como Junta de Sierpinski, é um fractal e um [conjunto fixo atrativo](https://pt.wikipedia.org/wiki/Ponto_fixo) com a forma global de um triângulo equilátero, subdividido recursivamente em triângulos equiláteros menores. Originalmente construído como uma curva, ele é um exemplo básico de conjuntos auto-similares, é um padrão gerado matematicamente que é possível reproduzir em qualquer ampliação ou redução. \n",
    "\n",
    "O nome é dado em homenagem ao matemático polonês **Wacław Sierpiński** que contribuiu muito para com os campos de teoria dos conjuntos, teoria dos números, teoria das funções e topologia.\n",
    "\n",
    "## Biblioteca turtle\n",
    "\n",
    "Existe em Python uma biblioteca chamada [**turtle**](https://docs.python.org/3.3/library/turtle.html?highlight=turtle) que nos permite desenhar diversos formas de maneira relativamente simples.\n",
    "\n",
    "Nesse caso iremos gerar o fractal recursivamente, ao quebrarmos o triângulo em três triângulos menores, depois quebrando esses triângulos em três triângulos menores e assim por diante. Teoricamente é possível fazermos isso infinitamente, porém para ilustração vamos utilizar apenas quatro vezes.\n",
    "\n",
    "O algoritmo segue a seguinte ideia:\n",
    "\n",
    "1. Especificamos três vértices para nosso triângulo equilátero.\n",
    "2. Desenha o triângulo inferior esquerdo ao utilizar o vértice inferior esquerdo, o ponto médio entre esse vértice e o vértice superior, e o ponto médio entre esse vértice e o vértice inferior direito:\n",
    "    - Se nós não tivermos atingido o caso base (o nível mais baixo do fractal), rodamos esse algoritmo recursivamente para esse triângulo.\n",
    "3. Desenha o triângulo superior ao utilizar o vértice superior, o ponto médio entre esse vértice e o vértice inferior direito, e o ponto médio entre esse vértice e o vértice inferior esquerdo:\n",
    "    - Se nós não tivermos atingido o caso base (o nível mais baixo do fractal), rodamos esse algoritmo recursivamente para esse triângulo.\n",
    "4. Desenha o triângulo inferior direito ao utilizar o vértice inferior direito, o ponto médio entre esse vértice e o vértice inferior esquerdo, e o ponto médio entre esse vértice e o vértice superior:\n",
    "    - Se nós não tivermos atingido o caso base (o nível mais baixo do fractal), rodamos esse algoritmo recursivamente para esse triângulo.\n",
    "    \n",
    "Dessa maneira talvez seja um pouco difícil de visualizarmos e compreendermos a ideia, para isso é importante que vejamos um exemplo do algoritmo em ação:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import turtle\n",
    "\n",
    "# Função que faz a biblioteca turtle desenhar um triângulo,\n",
    "# A unidade básica do nosso fractal\n",
    "def draw_triangle(vertices,tartaruga):\n",
    "    tartaruga.up()\n",
    "    tartaruga.goto(vertices[0][0],vertices[0][1])\n",
    "    tartaruga.down()\n",
    "    tartaruga.goto(vertices[1][0],vertices[1][1])\n",
    "    tartaruga.goto(vertices[2][0],vertices[2][1])\n",
    "    tartaruga.goto(vertices[0][0],vertices[0][1])\n",
    "    \n",
    "# Função que define os pontos médios\n",
    "def midpoint(p1, p2):\n",
    "    return [(p1[0] + p2[0])/2, (p1[1] + p2[1])/2]\n",
    "\n",
    "# Função recursiva que desenha os diferentes \"níveis\" do fractal\n",
    "def draw_fractal(vertices,level,tartaruga):\n",
    "    # Desenha um triângulo\n",
    "    draw_triangle(vertices,tartaruga)\n",
    "    # Chama a função recursivamente para desenhar todos os níveis do fractal\n",
    "    if level > 0:\n",
    "        # Desenha o primeiro segmento do fractal\n",
    "        # Os vértices sendo passados são o cantor inferior da primeira\n",
    "        # seção, o canto inferior da segunda seção e o canto inferior da terceira seção\n",
    "        draw_fractal([vertices[0],\n",
    "                      midpoint(vertices[0], vertices[1]),\n",
    "                      midpoint(vertices[0], vertices[2])],\n",
    "                      level - 1, tartaruga)\n",
    "        draw_fractal([vertices[1],\n",
    "                      midpoint(vertices[0], vertices[1]),\n",
    "                      midpoint(vertices[1], vertices[2])],\n",
    "                      level - 1, tartaruga)\n",
    "        draw_fractal([vertices[2],\n",
    "                      midpoint(vertices[2], vertices[1]),\n",
    "                      midpoint(vertices[0], vertices[2])],\n",
    "                      level - 1, tartaruga)\n",
    "\n",
    "tartaruga = turtle.Turtle()\n",
    "tartaruga.hideturtle()\n",
    "screen = turtle.Screen()\n",
    "vertices = [[-300, -200], [0, 300], [300, -200]]\n",
    "level = 4 # Define quão profunda a recursão para desenharmos o fractal\n",
    "draw_fractal(vertices, level, tartaruga)\n",
    "screen.exitonclick()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualização Gráfica do Triângulo Gerado:\n",
    "\n",
    "![img](https://raw.githubusercontent.com/the-akira/Python-Matematica/master/imagens/sierpinski.png)"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}