多角形衝突判定

Main.scala

object Main {
  implicit class Point[T <% Double](val self:(T,T)) {
    lazy val abs = math.sqrt(self._1 * self._1 + self._2 * self._2)
    def -[U <% Double](p:(U,U)) = (self._1 - p._1, self._2 - p._2)
    def cross[U <% Double](p:(U,U)) = self._1 * p._2 - self._2 * p._1
  }
  def crossProduct[T <% Double](polygon:List[(T,T)],points:List[(T,T)]) : List[List[Double]] =
    points.map { p => polygon zip(polygon.tail :+ polygon.head) map{ case(a,b) => (a - p) cross (b - p)}  }
  def isCrossVector(xs:List[Double]) : Boolean = xs.forall(_ > 0) || xs.forall(_ < 0)
  def isCross[T <% Double](poly1:List[(T,T)],poly2:List[(T,T)]) : Boolean =
    crossProduct(poly1,poly2).exists(isCrossVector) || crossProduct(poly2,poly1).exists(isCrossVector)
  def isInside[T <% Double](poly1:List[(T,T)],poly2:List[(T,T)]) : Boolean =
    crossProduct(poly1,poly2).forall(isCrossVector) != crossProduct(poly2,poly1).forall(isCrossVector)

  def input(str:String) : List[(Int,Int)] =
    str split(" ") map{ _.split(",") match { case Array(a,b) => (a.toInt, b.toInt)}} toList

  def main(args: Array[String]): Unit = {
    val tri1 = input {"-1,6 2,1 4,5"}
    val tri2 = input {"2,-1 4,3 6,-3"}

    (isCross(tri1,tri2), isInside(tri1,tri2)) match {
      case (true,true) => println("inside")
      case (true, _) => println("cross")
      case _ => println("outside")
    }
  }
}