Swift で ２つの線分の交点を求める

本当はもう少しまともなのを書きたかったのですが、タイムアウトで間に合わなかったので、ありあわせのネタでお茶を濁します。

さて Swift で２点を交差する判定もしくは、その交差した点を求める必要が発生しました。やりたいことはこんな三角形の塊を作りたかったからです。

自分で一から考えるのはなんなので、元になるコードを探しましたが、あまり気に入ったコードは見つかりませんでした。その中で良さそうな C++ のコードをベースに Swift で清書しました。元ネタへのリンクは末尾に記載します。

外積には「×」オペレータを定義しました。誤差の判定に使っているエプシロン「ε」の扱いは微妙に思います。そして、以下がそのソースコードになります。

import Foundation
import CoreGraphics


infix operator ×


extension CGPoint {

	static func - (lhs: CGPoint, rhs: CGPoint) -> CGPoint {
		return CGPoint(x: lhs.x - rhs.x, y: lhs.y - rhs.y)
	}

	static func + (lhs: CGPoint, rhs: CGPoint) -> CGPoint {
		return CGPoint(x: lhs.x + rhs.x, y: lhs.y + rhs.y)
	}

	static func * (lhs: CGPoint, rhs: CGFloat) -> CGPoint {
		return CGPoint(x: lhs.x * rhs, y: lhs.y * rhs)
	}

	static func / (lhs: CGPoint, rhs: CGFloat) -> CGPoint {
		return CGPoint(x: lhs.x / rhs, y: lhs.y / rhs)
	}
	
	static func * (lhs: CGPoint, rhs: CGPoint) -> CGFloat { // dot product
		return lhs.x * rhs.x + lhs.y * rhs.y
	}

	static func × (lhs: CGPoint, rhs: CGPoint) -> CGFloat { // cross product
		return lhs.x * rhs.y - lhs.y * rhs.x
	}
	
	var length²: CGFloat {
		return (x * x) + (y * y)
	}

	var length: CGFloat {
		return sqrt(self.length²)
	}

	var normalized: CGPoint {
		let length = self.length
		return CGPoint(x: x/length, y: y/length)
	}

}


struct Line {
	var from: CGPoint
	var to: CGPoint
	
	init(from: CGPoint, to: CGPoint) {
		self.from = from
		self.to = to
	}
	
	var vector: CGPoint { return to - from }
	var length: CGFloat { return (to - from).length }

	static func intersection(_ line1: Line, _ line2: Line, _ segment: Bool) -> CGPoint? {
		let v = line2.from - line1.from
		let v1 = line1.to - line1.from
		let v2 = line2.to - line2.from
		let cp = v1 × v2
		if cp == 0 { return nil }

		let cp1 = v × v1 // cross product
		let cp2 = v × v2 // cross product
		
		let t1 = cp2 / cp
		let t2 = cp1 / cp
		let ε = CGFloat(0).nextUp
		if segment {
			if t1 + ε < 0 || t1 - ε > 1 || t2 + ε < 0 || t2 - ε > 1 { return nil }
		}
		return line1.from + v1 * t1
	}

	static func angle(_ line1: Line, _ line2: Line) -> CGFloat {
		let a = line1.to - line1.from
		let b = line2.to - line2.from
		return atan2(b.y - a.y, b.x - a.x)
	}

}

Line は線分を示します。そして、intersection() に二つの線分を与えて呼び出します。三番目のパラメータは直線か線分かを Bool で指定します。延長線上で交差していても実際に交点がある場合に、その交点を戻す場合は true を、そして実際に交点がなくても、延長線上で交差している場合はその座標が欲しい場合は false を戻します。

以下に簡単ですがサンプルコードになります。第３引数の違いが結果に反映されている事が確認できるかと思います。

let p1 = CGPoint(x: 0, y: -200)
let p2 = CGPoint(x: 0, y: -100)
let p3 = CGPoint(x: 100, y: 0)
let p4 = CGPoint(x: 300, y: 0)

let l1 = Line(from: p1, to: p2)
let l2 = Line(from: p3, to: p4)

Line.intersection(l1, l2, true) // nil
Line.intersection(l1, l2, false) // {x 0 y 0}

元ネタのコードはこちらです。
http://marupeke296.com/COL_2D_No10_SegmentAndSegment.html

そして、gist からも入手可能になっています。
https://gist.github.com/codelynx/80077dbbb07e7d989016188573eab880

［執筆時点での環境の表記］

Xcode Version 8.2.1 (8C1002)
Apple Swift version 3.0.2 (swiftlang-800.0.63 clang-800.0.42.1)