Hatena::ブログ(Diary)

永字八法 RSSフィード Twitter

 | 

2012-02-27 Monday

点の集合で囲まれた領域の内外判定

領域判定の注意点 - 永字八法の続きと言うかメモ

2012/05/29に全面的に書き直されました。

任意の点Aが、任意の多角形(各頂点をP1〜Pnとする)の内部にあるかどうかを判別するには。
もっとも高速な判定アルゴリズムは既に判明している。任意の点Aから任意の方向に向かって線を引く。その線と、多角形の辺とが交差した回数が奇数であれば任意の点Aは内部になり、偶数であれば外部になる。
なのでプログラム的には、ある方向は任意の点Aのx座標かy座標かどちらかを増加させることで直線の判定を行う。
また、多角形は頂点の集合として捉える。
仮に、x座標を増加させることで解決を図るとする。
1.頂点を取捨選択する。
x座標を増加させるので、x座標が任意の点Aのx座標よりも小さい頂点は、判定の対象にならない。これらの頂点を一旦取り除く。
2.判定の対象になる辺のリストを作る。
1で残った頂点を含む辺のみをリストアップする。(辺は頂点の対として表現できる)
3.交差判定
2でリストアップされた辺と、任意の点Aから伸ばした線との交差を判定する。ここは他の記事を参照すること。
任意の点Aと、それとy座標を同じくしx座標を交差判定の線分のx座標の最大値とするのがよいだろう。
4.偶数奇数判定
3で交差すると判定された線分が何本あるかで、内外が判定できる。

トラックバック - http://d.hatena.ne.jp/eiji8pou/20120227/1330275398
 | 

Notice

コメント等は基本的に自由ですが、通りすがりとかななしさんとかの場合、いじっても面白くないので放置する可能性があります。

最近のエントリー

カウンター:
<< 2012/02 >>
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29
あわせて読みたい
過去ログ
0000 | 00 |
1800 | 10 |
1908 | 06 |
1983 | 06 | 12 |
1985 | 01 | 08 | 09 | 10 | 11 |
1986 | 10 |
1990 | 01 | 02 | 03 | 04 | 05 | 06 |
1995 | 01 |
1996 | 02 | 03 | 04 | 05 | 06 |
1997 | 03 | 05 |
1999 | 02 | 09 |
2000 | 00 |
2001 | 12 |
2002 | 01 | 02 | 03 | 04 |
2003 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2004 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2015 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2016 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2017 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2018 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |

Mail Form
お名前
メールアドレス
本文
公開の是非 公開してもよござんす/公開してはいけません
ブロ電™切符
RSS feed meter for http://d.hatena.ne.jp/eiji8pou/
著作権保護期間の70年延長に反対
NHK(日本放置協会)は放置される側の団体です
やる気の無いサイトリング
時間のないサイト運営者リング
ヒロインリコメンダー
私設コミケカタログ
「ひぐらしのなく頃に」を応援しています。
07th Expansion
「ひぐらしのなく頃に」のネタばれがあるのです。

最新コメント一覧

1. 08/21 無明長夜
2. 05/06 えぐち
3. 09/18 ABC1979
4. 10/14 eiji8pou
5. 10/14 ななし
6. 10/14 ななし
7. 06/30 うなぎ
8. 01/12 ねこ
9. 10/18 とおりすがり
10. 04/29 柊
11. 02/13 湖都
12. 02/13 eiji8pou
13. 02/13 湖都
14. 10/06 湖都
15. 10/06 リメ

最新トラックバック一覧

1. 03/03 Twitter / @uxIDiYlDhqWLm83
2. 03/02 Twitter / @roboko_bot
3. 03/02 Twitter / @Blue_Reimu
4. 10/17 Twitter / @Rek7z
5. 11/16 Twitter / @Lyri_m
6. 09/01 Twitter / @shinriyo
7. 04/10 Twitter / @psychedesire
8. 10/25 Twitter / @karafuto1979
9. 10/23 Twitter / @kkk_iso
10. 10/23 Twitter / @tacticsrealize
11. 10/22 Twitter / @kkk_iso
12. 10/18 Twitter / @kkk_iso
13. 04/24 Twitter / @fakestarbaby
14. 02/11 Twitter / @karafuto1979
15. 04/10 buynowforsaleの日記 - 灯で形態素解析もどき&マルコフ連鎖で文章...

言及URL

1. FrontPage - 朱鷺魅
2. Renee PDF Aideのダウンロード : Vector ソフトを探す!
3. NScripter−Tips:常駐ボタンの作り方
4. eiji8pouさんの採点結果[71点] まぁだいだいできたかなぁ〜|paizaオンラインハッカソンLite
5. 線形合同法 - Wikipedia
6. システムカスタマイズについてダラダラやるよーその8 - 永字八法
7. システムカスタマイズについてダラダラやるよーその7 - 永字八法
8. pretextgosubとgettag - 永字八法
9. システムカスタマイズについてダラダラやるよーその6.5 - 永字八法
10. システムカスタマイズについてダラダラやるよーその6 - 永字八法

言及ISBN/ASIN

1. 日本語〈上〉 (岩波新書)
2. ラプンツェル
3. ツバメしんどろ~む (Volume2) (角川コミックスドラゴンJr.)
4. ツバメしんどろ~む (3) (角川コミックスドラゴンJr)
5. ツバメしんどろ~む4 (カドカワコミックスドラゴンJr)
6. ツバメしんどろ~む v.6 (角川コミックス ドラゴンJr. 48-11)
7. ツバメしんどろ~む v.7 (角川コミックス ドラゴンJr. 48-13)
8. ツバメしんどろ~む v.8 (角川コミックス ドラゴンJr. 48-14)
9. だから僕は、Hができない。 4 (ドラゴンコミックスエイジ お 3-2-4)
10. キカイダー02(5) (角川コミックス・エース)
11. ストライクウィッチーズ 天空の乙女たち (1) (角川コミックス・エース 82-6)
12. J1 1 (あすかコミックスDX)
13. J1 2 (あすかコミックスDX)
14. 東方三月精 〜 Strange and Bright Nature Deity. (1) (角川コミックス)
15. のりタマ 1 (電撃コミックス)
16. ヘヴィーオブジェクト (電撃コミックス)
17. 京騒戯画鏡書院と迷子の栞 (電撃コミックス)
18. あぶない丘の家 3 (あすかコミックス)
19. ダークマーメイド―邪神伝説シリーズ 2 (ノーラコミックス 邪神伝説シリーズ)
20. まあめいど―都築和彦CGコミックス (ノーラコミックス・デラックス)
21. ワダチ 1 (マガジンKC)
22. ワダチ 2 (マガジンKC)
23. シミュレーションの発想―新しい問題解決法 (ブルーバックス (B‐523))
24. クレオパトラの謎 (講談社現代新書 (683))
25. ワーグナー (講談社現代新書)
26. 悪魔の話 (講談社現代新書)
27. 西洋占星術―科学と魔術のあいだ (講談社現代新書)
28. ChuしてBOMB! 1 (講談社コミックスフレンド)
29. ChuしてBOMB! 2 (講談社コミックスフレンド)
30. 星の島のるるちゃん 1 (講談社コミックスなかよし)

言及JAN/EAN

1. コミックメガストア 2009年12月号
2. 二次元ドリームマガジン2005年2月号
3. 二次元ドリームマガジン2006年2月号
4. 二次元ドリームマガジン2007年2月号
5. 二次元ドリームマガジン2005年4月号
6. 二次元ドリームマガジン2006年4月号
7. 二次元ドリームマガジン2007年4月号
8. 二次元ドリームマガジン2005年6月号
9. 二次元ドリームマガジン2006年6月号
10. 二次元ドリームマガジン2004年8月号
11. 二次元ドリームマガジン2005年8月号
12. 二次元ドリームマガジン2006年8月号
13. 二次元ドリームマガジン2005年10月号
14. 二次元ドリームマガジン2006年10月号
15. 二次元ドリームマガジン2005年12月号
16. 二次元ドリームマガジン2006年12月号
17. まんがタイムきららMAX 2010年01月号
18. ウルトラジャンプ 2009年11月号
19. コミックメガストアH 2009年10月号
20. 二次元ドリームマガジン 2009年12月号 Vol.49
21. コミック二次元ドリームVol.01
22. まんが学園4年生
23. まんがパレット2010年5月号
24. まんが4コマKINGSぱれっと 2009年12月号
25. まんがタイムきらら 2010年1月号
26. まんがタイムきらら 2010年4月号
27. まんがタイムきらら 2009年11月号
28. まんがタイムきららMAX 2009年12月号
29. まんがタイムきらら Carat 2009年12月号
30. HGST 3.5inch 7200rpm 2.0TB 64MB SATA 6.0Gbps

eiji8pouのアンテナ

1. 女子高生Cの場合
2. はてなダイアリー - ACADEMIC RESOURCE GUIDEの作業メモ
3. カレントアウェアネス・ポータル | 国立国会図書館
4. のらゴコロ
5. 労働者の図書館 〓図書館で働く者の義務と権利〓
6. blue-black
7. 図書館ばなし
8. 山中湖情報創造館
9. marginBlog
10. 競馬まとめのまとめ
11. lib_blog
12. ウパ日記
13. マロニエの花咲く 光町立図書館blog
14. 海外競馬巡回記
15. 東京の図書館をもっとよくする会
16. HimawariWatch
17. うさだ
18. 初音ミクニュース
19. himaginaryの日記
20. diary / nowadays


注目ISBN/ASIN

1. 真野恵里菜メジャーデビュー10周年記念フォトエッセイ 『 軌跡 』
.
.
.
.
.
.
.
.
.

最新JAN/EAN

1. 6CD Gabriel Fauré
2. The Art of Violin 3 Alfonso Mosesti
3. Brahms: Tre Sonate pianoforte e violino op.78-100-108
4. うな次郎
5. BBC Music Magazine Vol.18.3 Sergei Prokofiev

注目JAN/EAN

1. まんがタイムきららCarat 2009年1月号
.
.
.
.

書いたコメント