Go言語による2本の線分の交差判定の実装

Aru

この記事では、２つの線分が交差するかどうかを判定する交差判定をGo言語で実装したので、それを紹介します。このコードで、「アルゴリズム×数学」が基礎からしっかり身につく本のp.139の演習問題２つの線分の交差判定を行うプログラムをGo言語でAC（正解）することができます。

その他のAtCoderに役立つ記事の一覧

AtCoderで役立つ記事一覧（Python, Go言語）

Contents

この記事の前提
自分で書いた交差判定プログラムがACしない
交差判定を行う関数（同一直線上に存在、端が重なっている場合も交差とみなすもの）
交差判定を行う関数（一般的なもの）
まとめ

この記事の前提

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

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

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

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

理由は簡単で

「２つの線分が同一直線上の場合に、重なりがあると演習問題では交差しているとみなしている」

ことです。

そこで、参考サイトを見ながら交差判定を修正しました。

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

参考サイト通りにPythonコードをGo言語に移植したのですが、それでもACしませんでした。

原因は、以下の部分でした（Pythonコード）。

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

tc1とtc2の値の範囲を調べるとわかりますが、問題点は、単純なオーバーフローです（Pythonではオーバフローが発生しないので正しく判定できていたようです）。

ということでここをGo言語向けに修正しました。この部分での処理は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
}