December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
286
■
9
章 計算幾何学
凸包走査
を使って上側の凸包を計算する様子を図9-3に示す。この方式は、全体
として、
P
のすべての点を左から右へ訪問するので、多数の失敗が起こり得る。し
かし、上側の凸包部分を正しく計算する途中で、
3
点の中央の点を取り除く処理を、
場合によっては連続して行うことで、修正できることに注意しよう。
図9-3 上側の部分凸包の増分的構築
9.3.1
入出力
入力は、平面上の
2
次元の点集合
P
である。
凸包走査
は
P
の凸包をなす
h
個の節点を時計回りに整列したリストを計算する。
凸包は、
L
0
, L
1
,
…
, L
h
−
1
で定義される多角形となる。ここで、
h
を
L
にある点の個
数とする。この多角形は、
h
個の線分＜
L
0
, L
1
＞
,
＜
L
1
, L
2
＞
,
…
,
＜
L
h
−
1
, L
0
＞に
よって作られることに注意する。
自明な解を避けるために、
|P |
≧
3
と仮定する。どの
2
つの点も「近すぎる」こと
はない（実装に依存して決まる）。
2
つの点が近すぎて、片方が凸包の点であるなら、
凸包走査
は、間違った点を選んだり（あるいは、正しい凸包点を捨てたりする）が、
それらの相違は無視できる。
9.3.2
文脈
凸包走査
は、（乗除算のような）基本演算だけで済むので、
3
章で示した三角恒等
式を用いる
グラハム走査
（
Graham, 1972
）よりも実装が容易である。
凸包走査
は再
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.