計算幾何学
【computational geometry】計算機科学の一分野で、コンピュータによって図形を扱うことを研究する学問。
このタグの解説について
この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。関連ブログ
HTMLのcanvasで任意の4点をクリックして四角形を描く
なんか、ライブラリであるかな？と思ったけど、意外と書いちゃった方が楽なんじゃないかと思って書いた。 結論から申し上げますと、外積がメッチャ役に立った。 任意の4点から四角形を描く方法 なんかこれどう考えればいいんだろう？って思ったけど、良いのがあった。 4点をpi(i=1,2,3,4)とします. 逆の発想で線分が交わるかどうかを考えます. 線分p1-p2と線分p3-p4が交わりかつ重なっていない場合には, 四角形p1 p3 p2 p4は凸四角形になります (証明は幾何学か計算幾何学の本に載っていると思います). なので線分p1-p2と線分p3-p4, 線分p1-p3とp2-p4, 線分p1-p…
ネットで話題
もっと見る
language-and-engineering.hatenablog.jp
gihyo.jp
hossy.net
www.amazon.co.jp
codeiq.hatenablog.com
www.nakanihon.co.jp
you-got.hatenadiary.org
www.amazon.co.jp
www.amazon.co.jp関連ブログ
アルゴリズム本、書きました！
1. はじめに お久しぶりです！ けんちょんです。 これまで 3 年間にわたって、Qiita に、アルゴリズムに関するさまざまな話題を投稿し続けてきました: アルゴリズムとは何か！？ 計算量オーダーの求め方を総整理！ 動的計画法超入門！ 再帰関数を学ぶと、どんな世界が広がるか スタックとキューを極める！ ソートを極める！ DFS (深さ優先探索) 超入門！ 実世界で超頻出！二部マッチングの解法を総整理！ このたび、それらの記事を有機的にまとめ上げ、さらに多数のトピックを追加する形で、アルゴリズム入門書を上梓させていただくことになりました！ 大槻兼資著、秋葉拓哉監修：問題解決力を鍛える!アルゴ…
イラストで学ぶ 離散数学
ラムダ計算などを学ぶために「計算モデルとプログラミング」という本を読んでいたら、集合や論理など数学の基礎知識が必要でした。 集合や論理は「離散数学」という分野の話だったので、離散数学の分かりやすい本を読んでみることにしました。 イラストで分かりやすく説明した本が「イラストで学ぶ 離散数学」です。 イラストで学ぶ 離散数学 (KS情報科学専門書) 作者:伊藤 大雄 発売日: 2019/09/07 メディア: 単行本（ソフトカバー） 目次 著者紹介 出版社情報 書評 離散数学とは？ YouTubeの離散数学解説動画 目次 第1章 離散数学の魅力――まず面白さを感じて下さい 1.1 ピックの定理 1…
【記号摂動】幾何計算で退化に対処したい
幾何学計算は、誤差が全くないような整数同士の演算であっても特定の状況で正しく計算ができなくなることで私のような一般学生を困らせる。 二次元の凸包を作るときには三角形の符号付面積が0になる状況、二次元のドロネー図を得るときには三角形の外接円周上に三角形の頂点以外の点がのっている状況などが、正しく計算できない状況ということになる。 このような状況を退化といい、退化の状況は幾何アルゴリズムによって千差万別だ。 以下計算には誤差がないと仮定して記述する。*1 個別に対処するのはしんどい 凸包を作るときに三角形の符号付面積が0になる状況が退化と呼ばれるというのは先ほど述べた通りだ。この状況では何らかの特…
幾何ライブラリ 解説1
幾何ライブラリの説明をしていきます。 ここで扱うものはAOJの計算幾何学に入っている問題です。 参照している問題に書いてある変数等の宣言はしないので、URLが書いてあるものについては一度見てください。 おそらく幾つかに分けることになると思います。 高校数学を前提知識としていますのでその部分の説明はあまりしません。 また、include文などを逐次記述していると膨れてしまうので、記述しません。 最低限理解できればいいと思って書いているので、式変形や変数の定義など書かない時が多々あります。ここでは、一度記述したものについては再度記述することなく使用しますので、標準のヘッダから提供される関数等と混同…
１．計算幾何の基本 シリーズ：「基礎的計算幾何ライブラリの作り方」
シリーズの構成 １．計算幾何の基本 ←いまここ ２．計算幾何のインフラ整備 ３．直線、線分の計算幾何 ４．円の計算幾何 ５．多角形の計算幾何 ６．AOJにある問題の解説
競プロ始めてから一年間のうちに勉強したアルゴリズム（≒AtCoder緑になるのに必要な知識？）
おはようございます。おはようございますです。（私の名前はおはようございますです）競プロを始めてもうちょいで１年になります。折角なのでここまで勉強したデータ構造とアルゴリズムについての知識を列挙してみようと思います。現在の僕のレートが緑なので、この辺を覚えておけば緑になるには十分なのではないかと思います。数学とかいうのは知りません。 僕よりも後に始めた初心者（主に灰色、茶色）向けです。 なのでなるべく分かりやすい説明を心がけたいとは思いますが、変数や基本的な制御構文（for文とかif文とか）は知っているものと仮定します。 仕様言語はC++を前提にするので、Pythonを使っている人は少し分かりづ…
【ティンダロスの保護観察犬】「正方形問題」のあっけない解決方法？
こうして私の脳内に「基本円（Unit Circle）/基本円柱（Unit Cylnder）/基本球面（Unit sphere）からの脱出口」を見出したティンダロスの猟犬こと正2/(2N+1)角形群が私の記憶を探って新たなビジュアルを手に入れようとしています。例えばエッシャーのだまし絵とか… 最近、水木しげる画伯を追う形で「あちら側の世界」に存在をシフトされた吾妻ひでお画伯が最後に残したこういう絵とか… その3 pic.twitter.com/2EvCHpsFt8 — 吾妻ひでお (@azuma_hideo) June 6, 2017 あけましておめでとう pic.twitter.com/U7e…
