【第2回】点の多角形に対する内外判定｜【技業LOG】技術者が紹介するNTTPCのテクノロジー｜【公式】NTTPC
前回(と言っても一年近く経過していますね・・・。遅くなりました。)に引き続き、地図上に存在するエリアと現在地との関係性を計算機上で把握する手法の第2回目です。今回は、第3工程にあたる、「内外判定」について解説します。 現在地があるエリアの内側にいるか外側にいるかを考える場合、２次元平面上に存在する任意の点Pと多角形Tについて、点Pが多角形Tの内側にいるか外側にいるかを判定するにはどうしたらよいかを考えます。 この時、主に次の2つのアルゴリズムが利用されていることがわかりました。 Crossing Number Algorithm Winding Number Algorithm そこで、今回はこれらのアルゴリズムと実装方法(コード)について説明します。 まずはそれぞれのアルゴリズムの概要を簡単に説明します。 1.1.Crossing Number Algorithm（交差数判定）の概要 こ
Pythonを用いてPoint-in-Polygon (PIP) アルゴリズムによりポリゴン内の点判定する方法 - Qiita
はじめに この記事では、ある点がポリゴン内に存在するかどうかを判定する方法について説明します。具体的な実装コードを基に、それぞれの関数やステップを説明していきます。 実行例は、google colab でも確認できます。 Point-in-Polygon (PIP) アルゴリズム Point-in-Polygon (PIP) アルゴリズムは、与えられた点が多角形の内部にあるか、外部にあるか、境界上にあるかを判定するためのアルゴリズムです。このアルゴリズムは、GIS (地理情報システム) やコンピュータグラフィックスなどの分野で一般的に使用されます。 以下は、PIP アルゴリズムの一つである「Ray Casting（光線投射）アルゴリズム」の基本的な考え方です： 与えられた点から任意の方向に無限に伸びる半直線（光線）を投射します。 この光線が多角形の辺を何回交差するかをカウントします。 もし
Python で整数を可逆スクランブルする - Qiita
発端 ケース1 とあるサービスで, ユーザ ID を整数の連番で採番しており, ユーザにユーザ ID を見せる際, そのままユーザに見せてしまうと, ユーザ数が予測されてしまう. そこで, ユーザ ID を別の整数に可逆変換し, その値をユーザに見せたい. ケース2 雑誌などに, 整数のみで構成されたシリアルキーを掲載する際, ランダムでシリアルキーを生成したいが, 件数が増えると重複チェックで大量にリソースを消費する. そこで 連番の整数を別の整数に可逆変換し, その値をシリアルキーとしたい. 解決策 偉大な先人の知恵を借りる 整数を可逆スクランブルする - C Sharpens you up 数値を変換する関数を Python で実装 先人の知恵を拝借し, 全単射な変換関数を Python で実装する. def scramble(number, salt, inverse_salt):
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
微分積分
