Anonymous user
K-d tree: Difference between revisions
m
→{{header|Scala}}: Tidying
m (→{{header|Scala}}: Tidying) |
|||
Line 1,385:
import Numeric._
// Task 1A. Build tree of KDNodes. Translated from Wikipedia.
def apply[T](points: Seq[Seq[T]], depth: Int = 0)(implicit num: Numeric[T]): Option[KDNode[T]] = {
val dim = points.headOption.map(_.size) getOrElse 0
Line 1,399 ⟶ 1,398:
}
// Task 1B.
case class KDNode[T](value: Seq[T], left: Option[KDNode[T]], right: Option[KDNode[T]], axis: Int)(implicit num: Numeric[T]) {
def nearest(to: Seq[T]): Nearest[T] = {
Line 1,421 ⟶ 1,419:
}
}
}▼
case class Nearest[T](value: Seq[T], to: Seq[T], visited: Set[KDNode[T]] = Set[KDNode[T]]())(implicit num: Numeric[T]) {▼
lazy val distsq = KDTree.distsq(value, to)▼
override def toString = f"Searched for=${to} found=${value} distance=${math.sqrt(num.toDouble(distsq))}%.4f visited=${visited.size}"▼
}
Line 1,428 ⟶ 1,432:
def compare[T](a: Seq[T], b: Seq[T])(implicit num: Numeric[T]): Int =
a.zip(b).find(c => num.compare(c._1, c._2) != 0).map(c => num.compare(c._1, c._2)).getOrElse(0)
▲ // Something to keep track of nodes visited as per task
▲ case class Nearest[T](value: Seq[T], to: Seq[T], visited: Set[KDNode[T]] = Set[KDNode[T]]())(implicit num: Numeric[T]) {
▲ lazy val distsq = KDTree.distsq(value, to)
▲ override def toString = f"Searched for=${to} found=${value} distance=${math.sqrt(num.toDouble(distsq))}%.4f visited=${visited.size}"
▲ }
}</lang>
Task test:
| |||