两个直线/线段的交点

问题，求上图中线段AB 和线段CD的交点P的坐标

根据《算法艺术与信息学竞赛》，公式如下

原理：

利用叉积求得点P分线段DC的比，然后利用高中学习的定比分点坐标公式求得分点P的坐标

要注意的是

若判断是两条线段，需先判断能否相交，相交的时候才可调用该公式求相交点

判断结果如下图

golang代码如下

package main

import (
   "fmt"
   "math"
)

type Point struct {
   X     int32
   Y     int32
}
func (p Point) GetX() int32 {
   return p.X
}
func (p Point) GetY() int32 {
   return p.Y
}

const  eps = 1e-6    // 最小精度误差

func sgn(x float64) int {
   if x < -eps {
      return -1
   }
   return 1
}

func Cross(p1 *Point, p2 *Point, p3 *Point, p4 *Point) float64 {
   return (float64(p2.GetX())-float64(p1.GetX())) * (float64(p4.GetY())-float64(p3.GetY())) - (float64(p2.GetY())-float64(p1.GetY())) * (float64(p4.GetX())-float64(p3.GetX()))
}

func Area(p1 *Point, p2 *Point, p3 *Point) float64 {
   return Cross(p1, p2, p1, p3)
}

func fArea(p1 *Point, p2 *Point, p3 *Point) float64 {
   return math.Abs(Area(p1, p2, p3))
}

// 判断两条线段能否相交
func Meet(p1, p2, p3, p4 *Point) bool {
   return     math.Max(math.Min(float64(p1.GetX()), float64(p2.GetX())), math.Min(float64(p3.GetX()), float64(p4.GetX()))) <=
         math.Min(math.Max(float64(p1.GetX()), float64(p2.GetX())), math.Max(float64(p3.GetX()), float64(p4.GetX())))      &&
         math.Max(math.Min(float64(p1.GetY()), float64(p2.GetY())), math.Min(float64(p3.GetY()), float64(p4.GetY()))) <=
         math.Min(math.Max(float64(p1.GetY()), float64(p2.GetY())), math.Max(float64(p3.GetY()), float64(p4.GetY())))      &&
         (float64(sgn(Cross(p3, p2, p3, p4))) * Cross(p3, p4, p3, p1) >= 0)                                     &&
         (float64(sgn(Cross(p1, p4, p1, p2))) * Cross(p1, p2, p1, p3) >= 0)
}

// 计算两个直线的交叉点（若是判断两个线段，需先经过上面Meet()函数的检测，结果为true的才可调用本函数）
func Inter(p1 *Point, p2 *Point, p3 *Point, p4 *Point) Point {
   k := fArea(p1, p2, p3) / fArea(p1, p2, p4)
   return Point {
      X: int32( (float64(p3.GetX())+k*float64(p4.GetX())) / (1+k) ),
      Y: int32( (float64(p3.GetY())+k*float64(p4.GetY())) / (1+k) ),
   }
}

func main() {
   // 线段1
   p1 := &Point{X:300,Y:300}
   p2 := &Point{X:500,Y:500}
   // 线段2
   p3 := &Point{X:300,Y:500}
   p4 := &Point{X:500,Y:300}

   if Meet(p1, p2, p3, p4) {
      fmt.Printf("p1p2和p3p4相交 \n")
      p := Inter(p1, p2, p3, p4)
      fmt.Printf("相交点p=%v \n", p)
   } else {
      fmt.Printf("p1p2和p3p4不相交 \n")
   }

   // 线段3
   p5 := &Point{X:100,Y:100}
   p6 := &Point{X:100,Y:500}
   if Meet(p1, p2, p5, p6) {
      fmt.Printf("p1p2和p5p6相交 \n")
      p := Inter(p1, p2, p3, p4)
      fmt.Printf("相交点p=%v \n", p)
   } else {
      fmt.Printf("p1p2和p5p6不相交 \n")
   }
}