2018-11-24 長津田散歩

長津田に住んで1年が経った．長津田には3年間の滞在になると考えているのであまり愛着を持とうとしなかったが，なんたる失礼，自分の住んでいるまちについて知らないのもいかなるものかと思った．実は駅の南側にはよく散歩に行くのだが，北側はよく知らないので今回は北側をせめる．

いざ散歩

長津田駅がスタート・ゴールで時計回りに．約5kmのルート．

長津田駅南口入り口交差点より (B)

御野立落雁（おのたちらくがん）周辺 (C,D)

大正時代，この場所から皇太子(昭和天皇)が軍事演習を視察したらしい． 確かに見晴らしが良い．恩田川が見渡せたようだ．

近くの坂も趣がある．

横浜市立長津田小学校の裏．この先でわんこの落とし物を踏むことになる…

地下道付近 (E，F)

ものすごく吸い込まれる感じがした．夜来たら怖い．

大変によろしい感じである．真下から電車が見られる部分があったが，当該線路が使用されているかはわからない．

長津田検車区 (G)

東急の車両がいっぱいとまっていた．鉄道マニヤの方々にも人気があるらしく，僕がいる間に2人が訪れていた．また，女性につくし野駅への行き方を尋ねられた．たしかこの橋を進めば着くはずであるので，そのように伝えた．

ちょうど洗車のために車両が入ってきた．前々から気になっていたパンタグラフの上の部分の撮影に成功．

義民原嶋源右衛門処刑執行の地 (H)

実はこの写真は処刑の地とは関係がない．日露戦争のときに白襷隊として亡くなった中里好治の碑である．子孫が管理されているようで，いかに白襷隊の作戦が無謀だったかについて説明書があった．

処刑の地の碑もその隣(写真右奥)にあったが，小さかった．別の場所に本物があると書いてあったような気もする．実際この近くに町田(東京)と長津田(神奈川)の境があるのでおもしろい．最近，境界杭について興味があるのでタイムリーな話題だったが，境界杭を見つけることはできず．

あかね台入り口交差点 (I)

本当はこの後あかね台に行く予定だったが，徹夜の影響もあり体力的に断念．本当にこのあたりはhogehoge台がいっぱいある．

終わりに

長津田は東急の多摩田園都市計画地域に含まれていた．その景色は大きく変わってしまったと思う． 今でも，この1年だけでどんどん新しい建物が建っていく．まちを壊している気がしてなんだか申し訳ない気分になる．

実はこの後秋葉原に行くなどした．(徹夜で断念とは)

DDCC2019予選参加記

予選はAtCoder上でオンラインで行われました．一昨年18卒枠で通過したこともあり，今年もぜひ通過したい．(去年は都合により参加できず) beta.atcoder.jp

参加1時間前にコンテストの存在を思い出し，久しぶりの競技プログラミングですこし焦る．

A

https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3645503

4の累乗を求める問題．intでオーバーフローしないのでループを回した．

B

https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3646296

Nが奇数のときと偶数のときで場合分けて，規則性を見つける．

幾何っぽく解くと面倒だと思う．

C

https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3647677

数列Pの最大値P_maxを決め打ちすると，Qの数列としては10^N/P_max通りが考えられるので，これを全てのP_maxについて足し込む．

相変わらず引き算のmodが怖くてできなかったので，今度からは自信を持って引き算のmodをしていきたい．

D

解答率を見て，かなり難しそうなので諦めてしまった．

「NをPで割った余り」と「Nの桁和をP-1で割った余り」が等しいという性質を使う．←ここまでは理解した．

終わりに

結果は3完の291位．去年のボーダーは，りあんくんによると

去年のDDCC新卒枠ボーダーは446位くらいらしいです

— りあん (@rian_tkb) 2018年11月23日

らしいので，是非通過したいものだ．

そういえば一昨年も，りあんくんの「出たほうが良い」ツイートを見て1時間前に出ること決めたんだった． あのときは久しぶりのオンサイトで楽しかったなあー

Ubuntu17.10でAVR開発環境の構築

ATtiny13AでLチカさせてみます． 次のブログを参考にさせていただきました．

invalid-log.blogspot.com

こんな感じのやつを前に作業しました．

準備

つかうもの一覧

• ATtiny13A (DIP)
• AVRISP mk2 (ライタ)
• 3V電源
• Ubuntu17.10がインストールされたPC
• ブレットボートとかジャンパ線とか

環境構築(ハードウェア)

AVRISP mk2 のピン配置

ATtiny13A のピン配置

秋月電子のデータシート

いざ配線

PB4の先にLEDをつけておく．ブレッドボード後ろの方に3Vの三端子レギュレータがあります．

環境構築(ソフトウェア)

avrdudeのインストール

これを使ってマイコンに書き込みを行う．

# apt-get install avrdude

ライタをPCに接続して次のように実行してみる．(avrdudeの実行には権限が必要だろう．)

# avrdude -c avrisp2 -p t13

avrdude: AVR device initialized and ready to accept instructions

Reading | ################################################## | 100% 0.00s

avrdude: Device signature = 0x1e9007 (probably t13)

avrdude: safemode: Fuses OK (E:FF, H:FF, L:6A)

avrdude done.  Thank you.

うまく行けばライタが少し光って上のように表示されるはず．-cでライタを指定(今回はAVRISP mk2なのでavrisp2)，-pでマイコンの型番を指定(t13しかなかった)(指定しないと型番一覧が表示される)．

-vオプションをつけると，より詳細な状態が表示されるようだ．

コンパイラ・ライブラリのインストール

コンパイラとライブラリをインストールする

# apt-get install gcc-avr binutils-avr avr-libc

これらのドキュメントは次を参照されたい https://www.nongnu.org/avr-libc/user-manual/index.html

Lチカさせてみる

プログラムの作成

$ cat led.c

#include <avr/io.h>
#include <util/delay.h>

int main() {
    DDRB  = _BV(PB4);   // PB4だけ出力
    PORTB = ~_BV(PB4);  // PB4以外内部プルアップ 
    while(1) {
        PORTB ^= _BV(PB4);   // 点滅
        _delay_ms(1000);     // 1秒待つ
    }
    return 0;
}

マクロとかは次のサイトを参考にした． IOポート、Cのマクロ | 始めるAVR

また，レジスタとかの詳しい情報はこれがわかりやすい．

コンパイル・転送

コンパイル

$ avr-gcc -mmcu=attiny13 -O -DF_CPU=1000000UL led.c -o led.out

ATtiny13は初期状態で内部クロックが1MHzであるらしいので，それをコンパイラに伝える(delayとかに必要)．

そして転送する．

# avrdude -c avrisp2 -p t13 -U flash:w:led.out:e

これでATtiny13AのFlashメモリにプログラムが書き込まれたことになり，めでたくPB4に接続したLEDが点滅するはずです!

電源を入れ直しても点滅するよ．

動作周波数を変えてみる

今まで初期状態の1MHz(8MHzの8分周)内蔵オシレータを使っていたが，より省電力にするために128KHzにしてみる．

ヒューズlfuseの値を変えることで周波数を変えることができる．

# avrdude -e -c avrisp2 -p t13 -U lfuse:w:0x7B:m

遅くした後はライタの周波数が相対的に速くなってしまいうまく書き込めないので，avrdudeは-Bオプションをつけて適切な速度になるように調整する． 128KHzだと-B 100でうまく行った．大きい値にしすぎると転送に時間がかかってしまう．

ヒューズの値などの詳細は先の資料に詳しい．

おわりに

CLI前提で環境構築してみました．もっと強い環境もあると思うので，いろいろ調べていきたい．

AVRISP mk2 のピン配置

1. MISO (Master In Slave Out)
2. VCC (3Vとか5Vとか)
3. SCK (Serial Clock)
4. MOSI (Master Out Slave In)
5. RST (Reset)
6. GND (0V)

マイコン側の同じ感じの名前のピンとつなげれば良い．

スレーブ固定のSPI(Serial Peripheral Interface)接続に3本，Resetに1本，VCCとGNDにそれぞれ2本の計6ピンからなる．

SPI接続についてはウィキペディアを参照．

シリアル・ペリフェラル・インタフェース - Wikipedia

寿司打日記

寿司打が新しくなったので最近やってます． ここから上達していきたいです．

typingx0.net

高級

お勧め

CGAL Hello World してみる

Computational Geometry Algorithms Library (CGAL) 便利そうなので入門してみる．

CGAL 4.13 - Manual: Hello World

これをやっておかないとCGALの哲学がわからなそうな気がしたのでちゃんとメモ． このページを超ざっくり説明できたらと思う．

そのまえにCGALをインストールしよう．公式のダウンロードページの指示に従えば問題なくインストールできた．

ではHelloWorldに戻ろう．

1. 3つの点と1つの線分

points_and_segment.cpp

#include <iostream>
#include <CGAL/Simple_cartesian.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;
int main()
{
  Point_2 p(1,1), q(10,10);
  std::cout << "p = " << p << std::endl;
  std::cout << "q = " << q.x() << " " << q.y() << std::endl;
  std::cout << "sqdist(p,q) = " 
            << CGAL::squared_distance(p,q) << std::endl;
  
  Segment_2 s(p,q);
  Point_2 m(5, 9);
  
  std::cout << "m = " << m << std::endl;
  std::cout << "sqdist(Segment_2(p,q), m) = "
            << CGAL::squared_distance(s,m) << std::endl;
  std::cout << "p, q, and m ";
  switch (CGAL::orientation(p,q,m)){
  case CGAL::COLLINEAR: 
    std::cout << "are collinear\n";
    break;
  case CGAL::LEFT_TURN:
    std::cout << "make a left turn\n";
    break;
  case CGAL::RIGHT_TURN: 
    std::cout << "make a right turn\n";
    break;
  }
  std::cout << " midpoint(p,q) = " << CGAL::midpoint(p,q) << std::endl;
  return 0;
}

とりあえずコンパイルしてみる．

$ g++ points_and_segment.cpp -lCGAL
$ ./a.out
p = 1 1
q = 10 10
sqdist(p,q) = 162
m = 5 9
sqdist(Segment_2(p,q), m) = 8
p, q, and m make a left turn
 midpoint(p,q) = 5.5 5.5

このプログラムでは点の定義からその出力，2点の距離(sqrtは時間がかかるためCGALではよく二乗距離を使うようだ)，線分と点の距離，三点の位置関係，中点を求める様子を確認できる．

surprising.cpp

#include <iostream>
#include <CGAL/Simple_cartesian.h>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point_2;
int main()
{
  {
    Point_2 p(0, 0.3), q(1, 0.6), r(2, 0.9);
    std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");   
  }
  {
    Point_2 p(0, 1.0/3.0), q(1, 2.0/3.0), r(2, 1);
    std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");   
  }  
  {
    Point_2 p(0,0), q(1, 1), r(2, 2);
    std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");   
  }  
  return 0;
}

not collinear
not collinear
collinear

collinearは3点が同一直線状に乗っているか判定する関数である．いずれの結果も"collinear"になりそうだが，前2つは丸め誤差によって"not collinear"と判定されている．

exact.cpp

#include <iostream>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <sstream>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
int main()
{
  Point_2 p(0, 0.3), q, r(2, 0.9);
  {
    q  = Point_2(1, 0.6);
    std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");
  }
  
  {
    std::istringstream input("0 0.3   1 0.6   2 0.9");
    input >> p >> q >> r;
    std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");
  }
  
  {
    q = CGAL::midpoint(p,r);
    std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");   
  }
 
  return 0;
}

not collinear
collinear
collinear

今回の"点"は先の"点"と定義される"kernel"が異なるため別物である．これを用いれば正しい判定が行われるが，そのためには数値の扱いに注意しなければならない． もちろん計算速度などの兼ね合いでどのkernelを使うべきか選ぶべきである．たくさんあるCGALのパッケージは，それぞれサポートするkernelが明記されているからその都度確認されたい．

2. 凸包と点の列

点集合の凸法を例に，関数へのデータの入出力のやりかたを見ていく．

array_convex_hull_2.cpp

#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
int main()
{
  Point_2 points[5] = { Point_2(0,0), Point_2(10,0), Point_2(10,10), Point_2(6,5), Point_2(4,1) };
  Point_2 result[5];
  Point_2 *ptr = CGAL::convex_hull_2( points, points+5, result );
  std::cout <<  ptr - result << " points on the convex hull:" << std::endl;
  for(int i = 0; i < ptr - result; i++){
    std::cout << result[i] << std::endl;
  }
  return 0;
}

これをコンパイルするにはGMPへのリンクが必要なようだ．

$ g++11  main.cpp -lCGAL -lgmp
$ ./a.out
3 points on the convex hull:
0 0
10 0
10 10

配列を用いる場合は，convex_hull_2関数に入力のポインタと出力のポインタを渡す．そして最後の凸法の点の後のポインタが返ってくる．

vector_convex_hull_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef std::vector<Point_2> Points;
int main()
{
  Points points, result;
  points.push_back(Point_2(0,0));
  points.push_back(Point_2(10,0));
  points.push_back(Point_2(10,10));
  points.push_back(Point_2(6,5));
  points.push_back(Point_2(4,1));
  CGAL::convex_hull_2( points.begin(), points.end(), std::back_inserter(result) );
  std::cout << result.size() << " points on the convex hull" << std::endl;
  return 0;
}

3 points on the convex hull

STLのvectorを使った場合はこのようにやる．back_inserterとか使えるようになりたいぞ!

どっちを使っていくべきかはその人の趣味に委ねられているようだ．後者はメモリの確保が不要になっているね．

3. Kernels と Traits について

ここらへんから知りたい内容が始まった．

先の凸法で用いたconvex_hull_2のドキュメントをながめていると，別のバージョンのconvex_hull_2があることに気づく．

template<class InputIterator , class OutputIterator , class Traits >
OutputIterator 
convex_hull_2(InputIterator first,
              InputIterator beyond,
              OutputIterator result,
              const Traits & ch_traits)

Traitsという引数が1つ増えている． まだあまり理解していないが，内部で実行されるアルゴリズムに使う基本的な処理を指定できるっぽい．ここらへん使いこなせると相当便利そう．

There are two obvious questions: What can be used as argument for this template parameter? And why do we have template parameters at all? To answer the first question, any model of the CGAL concept Kernel provides what is required by the concept ConvexHullTraits_2. As for the second question, think about an application where we want to compute the convex hull of 3D points projected into the yz plane. Using the class Projection_traits_yz_3 this is a small modification of the previous example.

4. Concepts と Models について

なんかわからない... Conceptというのは要件のことで，Modelはその要件を満たすもの?

書かれている例を見るとなんとなく分かった気になる．

5 Further Reading

"The C++ Standard Library, A Tutorial and Reference" by Nicolai M. Josuttis from Addison-Wesley や "Generic Programming and the STL" by Matthew H. Austern が勧められていた． チュートリアルも続くようだが，現時点でこのHello Worldしかない．

おわりに

最後の方は超適当になってしまったが，最後の方ほど大事なので後で加筆したい．CGALってどのくらい使われているのだろう...

CGALでランダム点をドロネー三角形分割してParaViewで観てみる

期待計算量のドロネー三角形分割を実装しようと思ったけど難しそうなので，とりあえずCGALという情報幾何ライブラリに任せちゃうことにした．

CGALのインストール

https://www.cgal.org/download/linux.html 簡単．

一応Hello Worldを読んだ． monman53.hateblo.jp

ランダム点の生成

このページを参考にした．生成器を作ってそこから取る感じだった．

#include <CGAL/Simple_cartesian.h>
#include <CGAL/point_generators_2.h>
#include <vector>

using namespace CGAL;
using K = Simple_cartesian<double>;
using Point = K::Point_2;
using Creator = Creator_uniform_2<double,Point>;

int main() {
    // Create point set. Prepare a vector for 1000 points.
    std::vector<Point> points;
    points.reserve(1000);
    // Create 1000 points from [-1,1)x[-1,1)
    Random_points_in_square_2<Point, Creator> g(1.0);
    cpp11::copy_n(g, 1000, std::back_inserter(points));
    return 0;
}

ドロネー三角形分割

大変苦戦したが，なんとか書けた．ただ分割するだけではなく頂点にインデックスの情報を持たせたかったのですこし大変．

#include <CGAL/Simple_cartesian.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <vector>

using K         = CGAL::Simple_cartesian<double>;
using Vb        = CGAL::Triangulation_vertex_base_with_info_2<int, K>;
using Tds       = CGAL::Triangulation_data_structure_2<Vb>;
using Delaunay  = CGAL::Delaunay_triangulation_2<K, Tds>;
using Point     = Delaunay::Point;
using Creator   = CGAL::Creator_uniform_2<double,Point>;


int main() {
    // Create point set. Prepare a vector for 1000 points.
    std::vector<Point> points_;
    std::vector<std::pair<Point, int>> points;
    points.reserve(1000);
    // Create 1000 points from [-1,1)x[-1,1)
    CGAL::Random_points_in_square_2<Point, Creator> g(1.0);
    CGAL::cpp11::copy_n(g, 1000, std::back_inserter(points_));
    for(int i=0;i<1000;i++){
        points.push_back({points_[i], i});
    }

    // Delaunay triangulation
    Delaunay t;
    t.insert(points.begin(), points.end());

    // output
    int n_vertices = t.number_of_vertices();
    int n_faces    = t.number_of_faces();

    std::cout << "# vtk DataFile Version 3.0" << std::endl;
    std::cout << "title" << std::endl;
    std::cout << "ASCII" << std::endl;
    std::cout << "DATASET UNSTRUCTURED_GRID" << std::endl;

    std::cout << "POINTS " << n_vertices << " float" << std::endl;
    for(auto point : points_){
        std::cout << point << " 0" << std::endl;
    }

    std::cout << "CELLS " << n_vertices + n_faces << " " << n_vertices*2 + n_faces*4 << std::endl;
    for(int i=0;i<n_vertices;i++){
        std::cout << "1 " << i << std::endl;
    }
    for(auto it = t.finite_faces_begin();it != t.finite_faces_end();it++){
        std::cout << "3 " << it->vertex(0)->info() << " "
                          << it->vertex(1)->info() << " "
                          << it->vertex(2)->info() << std::endl;
    }

    std::cout << "CELL_TYPES " << n_vertices + n_faces << std::endl;
    for(int i=0;i<n_vertices;i++){
        std::cout << "1" << std::endl;
    }
    for(int i=0;i<n_faces;i++){
        std::cout << "5" << std::endl;
    }

    return 0;
}

ParaViewで見てみる

最近ParaViewを使ってるのでvtkフォーマットで結果を出力してみた．そのためにインデックスもたせたのもある． できていると信じたい...

終わりに

疲れましたが，次からは使えそうです．