2D
Swift

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

More than 1 year has passed since last update.

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

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

Screen Shot 2016-12-22 at 14.28.46.png

自分で一から考えるのはなんなので、元になるコードを探しましたが、あまり気に入ったコードは見つかりませんでした。その中で良さそうな 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 を戻します。

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

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)