Intersection of 2 segments in 2 dimension. The method also finds an arbitrary intersection point if there is any.

segment_intersection.go

package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"strconv"
	"strings"
)

const (
	BIG = 1024 * 1024 * 10
	EPS = 0.00000001
)

func readLine(r *bufio.Reader) string {
	bytes, _, err := r.ReadLine()
	if err != nil {
		log.Fatalln("Failed to read line")
	}

	return string(bytes)
}

func readInts(r *bufio.Reader) []int {
	elems := strings.Fields(readLine(r))

	ret := make([]int, len(elems))
	for i, el := range elems {
		tmp, err := strconv.ParseInt(el, 10, 64)
		if err != nil {
			log.Fatalf("Failed to parse number %v", el)
		}
		ret[i] = int(tmp)
	}

	return ret
}

type Point struct {
	x, y float64
}

func (p *Point) Length() float64 {
	return math.Sqrt(p.x*p.x + p.y*p.y)
}

func (p *Point) Show() string {
	return fmt.Sprintf("(%v, %v)", p.x, p.y)
}

func (p *Point) Equal(p2 *Point) bool {
	return abs(p.x-p2.x)+abs(p.y-p2.y) < EPS
}

func Substract(p1, p2 *Point) *Point {
	return &Point{p1.x - p2.x, p1.y - p2.y}
}

func Cross2D(p1, p2 *Point) float64 {
	return p1.x*p2.y - p1.y*p2.x
}

type Segment struct {
	p1, p2 *Point
}

func (s *Segment) Show() string {
	return fmt.Sprintf("(%v %v) -> (%v, %v)", s.p1.x, s.p1.y, s.p2.x, s.p2.y)
}

func Normal(p *Point) *Point {
	return &Point{-p.y, p.x}
}

func Normalize(p *Point) *Point {
	l := p.Length()
	return &Point{p.x / l, p.y / l}
}

func DotProd(p1, p2 *Point) float64 {
	return p1.x*p2.x + p1.y*p2.y
}

func abs(x float64) float64 {
	if x < 0.0 {
		return -x
	}
	return x
}

func Add(p1, p2 *Point) *Point {
	return &Point{p1.x + p2.x, p1.y + p2.y}
}

func InvMat2by2(mat [][]float64) [][]float64 {
	// See: https://en.wikipedia.org/wiki/Invertible_matrix#Inversion_of_2_%C3%97_2_matrices
	det := mat[0][0]*mat[1][1] - mat[0][1]*mat[1][0]
	ret := [][]float64{
		{mat[1][1] / det, -mat[0][1] / det},
		{-mat[1][0] / det, mat[0][0] / det},
	}
	return ret
}

func Between(fr, to, this *Point) bool {
	if fr.Equal(this) || to.Equal(this) {
		return true
	}
	toFr := Substract(to, fr)     // Set the zero of the coordinate system to "fr" and calculate "to" in this system
	thisFr := Substract(this, fr) // Same for this one

	dp := DotProd(thisFr, Normal(toFr))
	if abs(dp) > EPS { // The fr-this line doesn't coincide with the fr-to line
		return false
	}

	if DotProd(thisFr, toFr) < -EPS { // to and this are on a different side of fr
		return false
	}

	return toFr.Length()-thisFr.Length() > -EPS // Since they are already on the same side "this" should be closer
}

func Intersect(s1, s2 *Segment) (*Point, bool) {
	vec1 := Substract(s1.p2, s1.p1)
	norm1 := Normalize(Normal(vec1))
	c1 := DotProd(s1.p1, norm1)
	// Basically norm1.x * x + norm1.y * y = c1 where x and y are variables is the normal equation of the line defined by segment s1

	vec2 := Substract(s2.p2, s2.p1)
	norm2 := Normalize(Normal(vec2))
	c2 := DotProd(s2.p1, norm2)

	// Now we try to solve the Ax = c equation where
	// A = {{norm1.x, norm1.y}, {norm2.x, norm2.y}} and c = {{c1}, {c2}}
	if abs(norm1.x*norm2.y-norm1.y*norm2.x) < EPS { // If det(A) == 0
		if abs(c1-c2) > EPS { // The 2 lines are parallel but not the same
			fmt.Println("The lines are parallel but not the same")
			return nil, false
		}

		// The 2 segments are associated with the same line
		// We transform the 2 endpoints into the coordinate system where s1.p1 is the origin
		fmt.Println("The 2 lines defined by the segments are the same")
		cands := []*Point{
			Substract(s2.p1, s1.p1),
			Substract(s2.p2, s1.p1),
		}
		for _, cand := range cands {
			if DotProd(cand, vec1) > -EPS && vec1.Length()-cand.Length() > -EPS {
				// Being here means that both cand and vec1 are on the same side of s1.p1 on the line
				// and cand is closer. We use -EPS because endpoints can also meet.
				return Add(s1.p1, cand), true
			}
		}
		return nil, false // Means that although the 2 segments are on the same line but they don't intersect.
	}

	// Here the 2 lines are not the same but they intersect so we need to solve Ax = c
	A := [][]float64{
		{norm1.x, norm1.y},
		{norm2.x, norm2.y},
	}

	iA := InvMat2by2(A)

	p := &Point{
		iA[0][0]*c1 + iA[0][1]*c2,
		iA[1][0]*c1 + iA[1][1]*c2,
	}
	if Between(s1.p1, s1.p2, p) && Between(s2.p1, s2.p2, p) {
		// If the intersection of the 2 lines is inside both segments.
		return p, true
	} else {
		return nil, false
	}
}

type Example struct {
	s1, s2 Segment
}

func main() {
	examples := []Example{
		Example{ // Intersecting lines, intersecting segments
			Segment{
				&Point{0.0, 0.0},
				&Point{1.0, 1.0},
			},
			Segment{
				&Point{0.0, 1.0},
				&Point{1.0, 0.0},
			},
		},
		Example{ // Intersecting lines, non-intersecting segments
			Segment{
				&Point{0.0, 0.0},
				&Point{1.0, 1.0},
			},
			Segment{
				&Point{2.0, 2.0},
				&Point{2.0, 0.0},
			},
		},
		Example{ // Parallel lines
			Segment{
				&Point{0.0, 0.0},
				&Point{1.0, 1.0},
			},
			Segment{
				&Point{0.0, 1.0},
				&Point{1.0, 2.0},
			},
		},
		Example{ // Same line, non-intersecting segments
			Segment{
				&Point{0.0, 0.0},
				&Point{1.0, 1.0},
			},
			Segment{
				&Point{2.0, 2.0},
				&Point{3.0, 3.0},
			},
		},
		Example{ // Same line intersecting segments
			Segment{
				&Point{0.0, 0.0},
				&Point{1.0, 1.0},
			},
			Segment{
				&Point{0.5, 0.5},
				&Point{1.5, 1.5},
			},
		},
		Example{ // Same line intersect at the end of segment
			Segment{
				&Point{0.0, 0.0},
				&Point{1.0, 1.0},
			},
			Segment{
				&Point{1.0, 1.0},
				&Point{1.5, 1.5},
			},
		},
	}

	for _, example := range examples {
		s1, s2 := &example.s1, &example.s2
		p, has := Intersect(s1, s2)

		if !has {
			fmt.Printf("The segments %v and %v have no intersection\n", s1.Show(), s2.Show())
		} else {
			fmt.Printf("The segments %#v and %#v intersect in the point %v\n", s1.Show(), s2.Show(), p.Show())
		}
	}
}