直線の交差判定ライブラリを書いてみる

時間があったので続き。(本当にあったのかどうかは別として。)そもそも昨日のライブラリ、バグがあって、最初のコンストラクタの最後に、

  this.c = c;
  this.m = m;

を入れておかないとダメ。当たり前ですね...。

class Line {

  Frac x1;
  Frac y1;
  Frac x2;
  Frac y2;

  Frac grad; // gradient
  Frac cept; // intercept

  Line(int x1, int y1, int x2, int y2) {
    this(new Frac("" + x1, "1"), new Frac("" + y1, "1"), new Frac("" + x2, "1"), new Frac("" + y2, "1"));
  }

  Line(Frac x1, Frac y1, Frac x2, Frac y2) {

    this.x1 = x1;
    this.y1 = y1;
    this.x2 = x2;
    this.y2 = y2;

    if( x1.compareTo(x2) == 0 ) {
      // adhoc implementation
      grad = null;
      cept = x1;
    }

    else {
      // (y1 - y2) / (x1 - x2)
      grad = y1.sub(y2).div(x1.sub(x2));
      // y1 - x1 * grad
      cept = y1.sub(x1.mul(grad));
    }

  }

  boolean parallel(Line l) {
    if( grad == null || l.grad == null ) {
      return (grad == null && l.grad == null);
    }
    return (grad.compareTo(l.grad) == 0);
  }

  int numCross(Line l) {
    if( parallel(l) ) {
      return (cept.compareTo(l.cept) == 0 ? 2 : 0);
    }
    return 1;
  }

  boolean isCross(Line l) {
    return (numCross(l) > 0);
  }

  Point crossPoint(Line l) {

    int num = numCross(l);
    if( num == 0 ) { return null; }
    if( num == 2 ) { return new Point(x1, y1); } // any point

    if( grad == null ) {
      Frac x = cept;
      Frac y = l.cept.add(l.grad.mul(x));
      return new Point(x, y);
    }

    if( l.grad == null ) {
      Frac x = l.cept;
      Frac y = cept.add(grad.mul(x));
      return new Point(x, y);
    }

    Frac x = l.cept.sub(cept).div(grad.sub(l.grad));
    Frac y = cept.add(grad.mul(x));
    return new Point(x, y);

  }

}

class Segment extends Line {

  Segment(int x1, int y1, int x2, int y2) {
    super(x1, y1, x2, y2);
  }

  Segment(Frac x1, Frac y1, Frac x2, Frac y2) {
    super(x1, y1, x2, y2);
  }

  boolean isCross(Segment s) {
    return (crossPoint(s) != null);
  }

  Point crossPoint(Segment s) {
    int num = numCross(s);
    if( num == 0 ) { return null; }
    if( num == 2 ) {
      Point p;
      if( contain(p = new Point(s.x1, s.y1)) ) { return p; }
      if( contain(p = new Point(s.x2, s.y2)) ) { return p; }
      if( s.contain(p = new Point(x1, y1)) ) { return p; }
      if( s.contain(p = new Point(x2, y2)) ) { return p; }
      return null;
    }
    Point p = super.crossPoint(s);
    if( contain(p) ) { return p; }
    return null;
  }

  boolean contain(Point p) {
    if( x1.compareTo(x2) < 0 ) {
      if( x1.compareTo(p.x) > 0 || p.x.compareTo(x2) > 0 ) { return false; }
    }
    else {
      if( x2.compareTo(p.x) > 0 || p.x.compareTo(x1) > 0 ) { return false; }
    }
    if( y1.compareTo(y2) < 0 ) {
      if( y1.compareTo(p.y) > 0 || p.y.compareTo(y2) > 0 ) { return false; }
    }
    else {
      if( y2.compareTo(p.y) > 0 || p.y.compareTo(y1) > 0 ) { return false; }
    }
    return true;
  }

}

class Point {

  Frac x;
  Frac y;

  Point(Frac x, Frac y) {
    this.x = x;
    this.y = y;
  }

  public boolean equals(Object obj) {
    if( obj instanceof Point ) {
      return toString().equals(obj.toString());
    }
    return false;
  }

  public int hashCode() {
    return toString().hashCode();
  }

  public String toString() {
    return "(" + x + ", " + y + ")";
  }

}

Pointの比較にFracを文字列にして比較していますが、本当はFracにもequalsとhashCodeを実装するべきのような気もします。全然関係ない名前のsamePointみたいなメソッドを実装して、compareToで比較する予定でしたが、文字列が一意に決まることを悪用して実装してみました。大抵hashCodeの実装に不備が混入するので、equalsはなるべくoverrideしないようにしています。overload(綴りあってる？)しても意味ありません。

一応SRM394.1のlevel2でデバッグしたので、Lineの交差判定までは動いていると思います。その場の勢いで線分クラスを作ってみたけれど、こちらはデバッグしていない。そもそも線分の場合は交点が不要なケースが比較的良くあり、ccwとかいう領域分割のどこにいるかという方式を使うっぽいです。(同一直線上に乗る時の処理が面倒だったような気もしますが。)BigIntegerとか使って交点求めた上でそれが線分に乗るかどうか判定しているので重いため、線分の交点がいらないケースでは使い物にならないような気もします。

ちょっと前のSRMで線分ライブラリがあると幸せな問題があったので、そこでちゃんとしたライブラリを作る方がいいのかも知れないなぁと。