Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Introduction to Graph Drawing

Introduction to Graph Drawing

「第29回 学生エンジニアLT大会!!! in 東京」での登壇資料です。
https://student-lt.connpass.com/event/139923/

Yosuke Onoue

August 18, 2019
Tweet

More Decks by Yosuke Onoue

Other Decks in Programming

Transcript

  1. άϥϑʢάϥϑཧ࿦ʣ w ϊʔυʢ௖఺ʣͱϊʔυؒΛ
 ͭͳ͙Τοδʢลʣ͔ΒͳΔ
 ߏ଄Λද͢਺ֶత֓೦ w άϥϑ( 7 & 

    w 7ɿϊʔυू߹
 &ɿΤοδू߹ w º๮άϥϑɺંΕઢάϥϑɺԁάϥϑ w 4/4Ͱͷަ༑ؔ܎ɺੜԽֶ൓ԠɺίϯϐϡʔλωοτϫʔΫͳͲ w ਓੜ୭͠΋ωοτϫʔΫΛՄࢹԽͨ͘͠ͳΔ͜ͱ͕͋Δ
  2. ӡಈͷγϛϡϨʔγϣϯ w ཻࢠʢϊʔυʣͷي੻ΛٻΊΔӡಈํఔࣜΛղ͘ w άϥϑඳըͷγϛϡʔϨγϣϯͰ͸ݫີੑ͸ඞཁͳ͍ͷͰɺ
 ͋Δఔ౓͍͍Ճݮʹ਺஋తʹղ͘ d2 dt2 r =

    F(t) m = a <latexit sha1_base64="Atc1ZV/bj8wGOvJ+iRBRSPE+rWg=">AAACEHicbZDLSgMxFIYzXmu9jbp0Eyxi3ZSZKuhGKArisoK9QDuWTCbThmYuJGeEMswjuPFV3LhQxK1Ld76NaTsLbT2Q8PP955Cc340FV2BZ38bC4tLyymphrbi+sbm1be7sNlWUSMoaNBKRbLtEMcFD1gAOgrVjyUjgCtZyh1djv/XApOJReAejmDkB6Yfc55SARj3zqOtLQlPvvpqlHugbS3yBp/C6DMdZGmQakJ5ZsirWpPC8sHNRQnnVe+ZX14toErAQqCBKdWwrBiclEjgVLCt2E8ViQoekzzpahiRgykknC2X4UBMP+5HUJwQ8ob8nUhIoNQpc3RkQGKhZbwz/8zoJ+OdOysM4ARbS6UN+IjBEeJwO9rhkFMRIC0Il13/FdEB0GKAzLOoQ7NmV50WzWrFPKvbtaal2mcdRQPvoAJWRjc5QDd2gOmogih7RM3pFb8aT8WK8Gx/T1gUjn9lDf8r4/AHKCZvF</latexit>
  3. 7FSMFUੵ෼ w ͋Δ࣌ࠁUͷ࠲ඪS U ΛUͷ·ΘΓͰςΠϥʔల։͢Δ w ඍখ࣌ؒ϶มԽͨ࣌͠ͷ࠲ඪΛߟ͑Δ w ͳΜ΍Β͔Μ΍Β͋ͬͯ଎౓ͷߋ৽͕ࣜಘΒΕΔ r(t)

    ' r(t0) + (t t0)v(t0) + (t t0)2 2 a(t0) <latexit sha1_base64="easryxov4QVwfzamJZmeu5/C2k8=">AAACLnicbZBdSwJBFIZn7cu2L6vLboYkUCLZtaAupQi6NMgPUJPZcVYHZz+aOSvI4i/qpr9SF0FFdNvPaFwtSjsw8PC+53DmvE4ouALLejFSC4tLyyvpVXNtfWNzK7O9U1VBJCmr0EAEsu4QxQT3WQU4CFYPJSOeI1jN6V+M/dqAScUD/waGIWt5pOtzl1MCWmpnLk2ZgzxuKu6xO6y5beXxIc4BPsIJD76lpisJjX+M2+IoLo4wSex2JmsVrKTwPNhTyKJplduZp2YnoJHHfKCCKNWwrRBaMZHAqWAjsxkpFhLaJ13W0OgTj6lWnJw7wgda6WA3kPr5gBP190RMPKWGnqM7PQI9NeuNxf+8RgTuWSvmfhgB8+lkkRsJDAEeZ4c7XDIKYqiBUMn1XzHtER0L6IRNHYI9e/I8VIsF+7hgX59kS+fTONJoD+2jHLLRKSqhK1RGFUTRPXpEr+jNeDCejXfjY9KaMqYzu+hPGZ9fiwGiyw==</latexit> r(t0 + ) ' r(t0) + v(t0) + 2 2 a(t0) <latexit sha1_base64="FCMKDU4u0OWt9duOtEyACdJdS54=">AAACMnicbZDLSgMxFIYzXmu9VV26CRahRSgzVdBlURe6U7BWaGvJpGfa0MzF5EyhDH0mNz6J4EIXirj1IUynRdR6IPDn+88hOb8bSaHRtp+tmdm5+YXFzFJ2eWV1bT23sXmtw1hxqPJQhurGZRqkCKCKAiXcRAqY70qoub2TkV/rg9IiDK5wEEHTZ51AeIIzNKiVO1cFbNl0jzZOQSIr0oYWPtzRFBe/Oe1/3z3FeDKmt+VhUh5SlnqtXN4u2WnRaeFMRJ5M6qKVe2y0Qx77ECCXTOu6Y0fYTJhCwSUMs41YQ8R4j3WgbmTAfNDNJF15SHcNaVMvVOYESFP6cyJhvtYD3zWdPsOu/uuN4H9ePUbvqJmIIIoRAj5+yIslxZCO8qNtoYCjHBjBuBLmr5R3mckETcpZE4Lzd+VpcV0uOfsl5/IgXzmexJEh22SHFIhDDkmFnJELUiWc3JMn8krerAfrxXq3PsatM9ZkZov8KuvzC8u2pks=</latexit> v(t0 + ) ' v(t0) + 2 (a(t0 + ) + a(t0)) <latexit sha1_base64="7qI3rFNd/R/xGvDN6pgxU+LcsOs=">AAACQHicbZA7SwNBFIVnfRtfUUubwSAkCGFXBS1FLSwVjBGyIdyd3E0GZx/O3BXCkp9m40+ws7axUMTWysmj0OiFgcM59zAzX5Aqach1n52p6ZnZufmFxcLS8srqWnF949okmRZYE4lK9E0ABpWMsUaSFN6kGiEKFNaD29NBXr9HbWQSX1EvxWYEnViGUgBZq1Ws35ep5fJd7p+hIqhw38gI7/jQrgz8UIPIR2k/3+tzX2FIZZio7XIYNXwtO12qtIolt+oOh/8V3liU2HguWsUnv52ILMKYhAJjGp6bUjMHTVIo7Bf8zGAK4hY62LAyhghNMx8C6PMd67R5mGh7YuJD92cjh8iYXhTYzQioayazgflf1sgoPGrmMk4zwliMLgozxSnhA5q8LTUKUj0rQGhp38pFFywxsswLFoI3+eW/4nqv6u1XvcuD0vHJGMcC22LbrMw8dsiO2Tm7YDUm2AN7YW/s3Xl0Xp0P53O0OuWMO5vs1zhf31mPq3c=</latexit>
  4. ݁ہ͜͏͍͏͜ͱ // ଷ䰤΄ๅෛ x += vx; y += vy; //

    ᭛ଶ΄ๅෛ vx += ax; vy += ay;
  5. ۭؾ఍߅Λߟྀͨ͠όωͷӡಈ // ଷ䰤΄ๅෛ x += vx; y += vy; //

    ᭛ଶ΄ๅෛ vx += 0; vy += ks * (L - abs(y0 - y)); vy += -kr * vy;
  6. /ମ໰୊ // ଷ䰤΄ๅෛ x[i] += vx[i]; y[i] += vy[i]; //

    ᭛ଶ΄ๅෛ float d = dist(x[i], y[i], x[j], y[j]); float w = -k * q[i] * q[j] / (d * d); vx[i] += (x[j] - x[i]) * w; vy[i] += (y[j] - y[i]) * w;