octech https://blog.hatena.ne.jp/octech/ octech https://octech.hatenadiary.org/ c++ プログラミング ある点が多角形（ポリゴン）の内部にあるかどうかをチェックするアルゴリズムを実装したくてちょっと調べてみました。凸多角形限定のアルゴリズムは以前実装したことがあったのですが、このページ（http://bal4u.dip.jp/mt/program/archives/2004/11/_ph.html）を見たら限定でなくても結構簡単に実装できるみたいなので、C++的に書き直しながら内部を把握してみました。 ちなみに、高速化を考え、線上は外側とみなすようにしてあります。 （追記）これ、原理的には穴が開いている多角形でも対応可能なのですが、ただ与えられた頂点配列の処理のしかたがそこまで対応できていません… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Foctech.hatenadiary.org%2Fentry%2F20070504%2F1178261941" title="点の多角形内包チェック - octech" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/o/octech/20070504/20070504161420.png Hatena Blog https://hatena.blog 2007-05-04 15:59:01 rich https://octech.hatenadiary.org/entry/20070504/1178261941 1.0 100%