Dart - classの定義(graham scan algorithm(グラハム走査), 凸包)

Dart: Up and Running
(O'Reilly Media)
Kathy Walrath Seth Ladd (著)
[Kindle版]
このブログでの感想

開発環境

• OS X Mavericks - Apple (OS)
• Dart Editor (開発環境)
• Dartium | Dart/ Structured web apps (ブラウザ, Dart VM 用 (Chromium with the Dart VM))
• Safari (ブラウザ, JavaScript 用)
• Dart (プログラミング言語)

Real World Haskell―実戦で学ぶ関数型言語プログラミング(Bryan O'Sullivan (著)、 John Goerzen (著)、 Don Stewart (著)、山下 伸夫 (翻訳)、伊東 勝利 (翻訳)、株式会社タイムインターメディア (翻訳)、オライリージャパン)の3章(型を定義し、関数を単純化する)、3.13(ガードの条件節の評価)、練習問題 12.をDartで解いてみる。

その他参考書籍

• What is Dart? [Kindle版] (O'Reilly Media) Kathy Walrath Seth Ladd (著) このブログでの感想

練習問題 12.

コード

sample.dart

import 'dart:html';

void main(){
  run.onClick.listen((MouseEvent){
    pre.text = window.navigator.userAgent + '\n';
    try{
      var nums = input_nums.value.split(',')
          .map((String s) => num.parse(s.trim()));
      if(nums.length % 2 != 0){
        throw '点の集合になっていない。';
      }
      List<Point> points = [];
      while(nums.length != 0){
        var pairs = nums.take(2);
        points.add(new Point(pairs.first, pairs.last));
        nums = nums.skip(2);
      }
      pre.text += '2次元平面上の点: $points\n';
      var a = grahamScan(points);
      pre.text += 'Graham scan: $a\n';
      pre.text += 'Directions: ${getDirections(a)}\n';
    } catch (e){
      pre.text += '$e\n';
    }
  });
  clear.onClick.listen((MouseEvent event) => pre.text = '');
}

InputElement input_nums = querySelector('#input_nums');
ButtonElement run = querySelector('#run_dart');
ButtonElement clear = querySelector('#clear');
PreElement pre = querySelector('#pre0');

List<Point> grahamScan(List<Point> points){
  var kernel = findLowestPoint(points);
  var sorted_points = sortedPoints(kernel, points);
  return grahamScanRecursive(kernel, sorted_points);
}

List<Point> grahamScanRecursive(Point kernel, List<Point> points){
  if(points.length < 2){
    throw 'エラー: grahamScanRecursive';
  }
  if(points.length == 2){
    var p1 = points[0];
    var p2 = points[1];
    var d = new Direction(p1, p2, kernel).direction;
    return d == 'Left turn' ? [p1, p2] : [p2];
  }
  var p1 = points[0];
  var p2 = points[1];
  var p3 = points[2];
  var new_points = points.sublist(3);
  List<Point> result = [];
  if(p1 == p2){
    result.addAll([p1, p3]);
  } else if(p1 == p3){
    result.add(p1);
  } else if(p2 == p3){
    result.addAll([p1, p2]);
  } else if(new Direction(p1, p2, p3).direction == 'Left turn'){
    result.addAll([p2, p3]);
    result.addAll(new_points);
    List<Point> new_result = [p1];
    new_result.addAll(grahamScanRecursive(kernel, result));
    return new_result;
  } else {
    result.addAll([p1, p3]);
  }
  result.addAll(new_points);
  return grahamScanRecursive(kernel, result);
}

Point findLowestPoint(List<Point> points){
  var lowest = points.first;
  for(var p in points.sublist(1)){
    lowest = lowest.lowerPoint(p);
  }
  return lowest;
}

List<Point> sortedPoints(Point kernel, List<Point> points){
  var new_points = points.toList();
  new_points.sort((Point p1, Point p2) => p1.comparePoint(kernel, p2));
  return new_points;
}

List<Direction> getDirections(List<Point> points){
  if(points.length < 3){
    return [];
  }
  var result = [];
  result.add(new Direction(points[0], points[1], points[2]));
  result.addAll(getDirections(points.sublist(1)));
  return result;
}

class Point{
  num x;
  num y;
  Point(this.x, this.y);
  bool operator ==(Point p) => x == p.x && y == p.y;
  Point lowerPoint(Point p){
    var py = p.y;
    if(y < py){
      return this;
    }
    if(y > py){
      return p;
    }
    var px = p.x;
    if(x < px){
      return this;
    }
    return p;
  }
  int comparePoint(Point kernel, Point p){
    if(this == p){
      return 0;
    }
    var cow = (x - kernel.x) * (p.y - kernel.y) -
        (y - kernel.y) * (p.x - kernel.x);
    if(cow > 0){
      return -1;
    }
    if(cow < 0){
      return 1;
    }
    if(x < p.x){
      return -1;
    }
    return 1;
  }
  String toString() => '($x, $y)';
}

class Direction{
  String direction;
  Direction(Point a, Point b, Point c){
    var cow = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    direction = cow > 0 ?
        'Left turn' : cow == 0 ?
            'Collinear' : 'Right turn';
  }
  String toString(){
    return direction;
  }
}