Go言語で２つの線分の交差判定

tadanori

「アルゴリズム×数学」が基礎からしっかり身につく本のp.139の演習問題の２つの線分の交差判定を行うプログラムをGo言語で作成したのでまとめておきます。

その他のAtCoderに役立つ記事の一覧は以下にあります。

この記事の前提

この記事は、同じ問題をPythonで解いた解法をベースにしています。また、「線分が交差する」判定のアルゴリズムに関しては説明しません。そちらについては、下記の参考サイトの参考サイトを参考にしてください。

参考サイト　2つの線分の交差判定（python）

自分で書いた交差判定プログラムがACしない

２つの線分の交差判定に関しては、いろいろ情報があるのでそちらを元にサクッと作成したのですが、演習問題に対してACしないという問題にぶつかりました。

理由は簡単で

「２つの線分が同一直線上の場合、端で重なっている場合を演習問題では交差している見做している」

ことです。

参考サイトを見て、これに気づきました。考察が不足していますが、このあたりは数学的なセンスがないとなかなか気づかない気がします。

２つの線分が同一直線上の場合、端で重なっている場合を演習問題では交差している見做している例

ということで、参考サイトのPythonコードをGo言語に移植したのですが、それでもACしない。

これは、参考サイトでは、Pythonで以下のように書かれている部分が問題でした。

return tc1 * tc2 <= 0 and td1 * td2 <= 0

ここは慣れもあって結構すぐ気づきました。tc1とtc2の値の範囲を調べるとわかりますが、問題点は、単純なオーバーフローです。

$10^9$を掛け合わせた結果のtc1, tc2などをさらに掛け合わせるので当然64bitの整数範囲からオーバフローしてしまいます。

ここの部分でやりたいことは、tc1とtc2の符号が異なるかどうか確認することなので、if文にすることでオーバーフローを回避できます。

具体的には、以下のような感じです

	ab := false
	cd := false
	if tc1 >= 0 && tc2 <= 0 {
		ab = true
	}
	if tc1 <= 0 && tc2 >= 0 {
		ab = true
	}
	if td1 >= 0 && td2 <= 0 {
		cd = true
	}
	if td1 <= 0 && td2 >= 0 {
		cd = true
	}
	return ab && cd

交差判定を行う関数（同一直線上に存在、端が重なっている場合も交差とみなすもの）

演習問題でACできる交差判定の関数CrossJudgeです。a, b, c, dにPoint型のデータを入力して利用します。

下記のコードは判定関数部分だけでACできるmain関数はないので注意してください

type Point struct {
	x, y int
}

// Max
func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Min
func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// MinMaxCrossCheck 区間 p1,p2 と　p3,p4に重なりがあるか
func MinMaxCrossCheck(p1, p2, p3, p4 int) bool {
	min_ab, max_ab := Min(p1, p2), Max(p1, p2)
	min_cd, max_cd := Min(p3, p4), Max(p3, p4)

	if min_ab > max_cd || max_ab < min_cd {
		return false
	}
	return true
}

// CrossJudge 線分ABと線分CDが交差しているか判定（線分ABとCDの一部が一直線に重なっている場合も交差と判定）
func CrossJudge(a, b, c, d Point) bool {
	// xによる重なり判定
	if MinMaxCrossCheck(a.x, b.x, c.x, d.x) == false {
		return false
	}
	// yによる重なり判定
	if MinMaxCrossCheck(a.y, b.y, c.y, d.y) == false {
		return false
	}

	tc1 := (a.x-b.x)*(c.y-a.y) + (a.y-b.y)*(a.x-c.x)
	tc2 := (a.x-b.x)*(d.y-a.y) + (a.y-b.y)*(a.x-d.x)
	td1 := (c.x-d.x)*(a.y-c.y) + (c.y-d.y)*(c.x-a.x)
	td2 := (c.x-d.x)*(b.y-c.y) + (c.y-d.y)*(c.x-b.x)

	ab := false
	cd := false
	if tc1 >= 0 && tc2 <= 0 {
		ab = true
	}
	if tc1 <= 0 && tc2 >= 0 {
		ab = true
	}
	if td1 >= 0 && td2 <= 0 {
		cd = true
	}
	if td1 <= 0 && td2 >= 0 {
		cd = true
	}
	return ab && cd
}

交差判定を行う関数（一般的なもの）

ついでに一般的な交差判定のGo言語のプログラムを置いておきます。こちらのプログラム、チェックしていませんがおそらく大丈夫だと思います。

違いは、まったく重ならない場合のチェックがなくなって、if文の>=などが>に変わっている点です。

type Point struct {
	x, y int
}

// Max
func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Min
func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// CrossJudge 線分ABと線分CDが交差しているか判定
func CrossJudge(a, b, c, d Point) bool {
	tc1 := (a.x-b.x)*(c.y-a.y) + (a.y-b.y)*(a.x-c.x)
	tc2 := (a.x-b.x)*(d.y-a.y) + (a.y-b.y)*(a.x-d.x)
	td1 := (c.x-d.x)*(a.y-c.y) + (c.y-d.y)*(c.x-a.x)
	td2 := (c.x-d.x)*(b.y-c.y) + (c.y-d.y)*(c.x-b.x)

	ab := false
	cd := false
	if tc1 > 0 && tc2 < 0 {
		ab = true
	}
	if tc1 < 0 && tc2 > 0 {
		ab = true
	}
	if td1 > 0 && td2 < 0 {
		cd = true
	}
	if td1 < 0 && td2 > 0 {
		cd = true
	}
	return ab && cd
}