参考https://blog.csdn.net/qq_42391248/article/details/123892301
根据java版本写了个golang的版本
package main
import (
"fmt"
"math"
)
func main() {
p1 := new(Polygon)
p2 := new(Polygon)
vec1 := new(Vector2)
vec1.Vector2Init(0, 0)
p1.AddVertex(*vec1)
vec1.Vector2Init(100, 0)
p1.AddVertex(*vec1)
vec1.Vector2Init(100, 50)
p1.AddVertex(*vec1)
vec1.Vector2Init(75, 50)
p1.AddVertex(*vec1)
//
vec2 := new(Vector2)
vec2.Vector2Init(0, 0)
p2.AddVertex(*vec2)
vec2.Vector2Init(100, 0)
p2.AddVertex(*vec2)
vec2.Vector2Init(100, 50)
p2.AddVertex(*vec2)
vec2.Vector2Init(75, 50)
p2.AddVertex(*vec2)
// 传入两个多边形
m := new(Matcher)
m.MatcherInit(*p1, *p2)
// 计算两个多边形的匹配率
matchRate := m.Distance()
fmt.Println("相似度：", 1-matchRate)
}
type TurningFunction struct {
Range []float64 //图形的x轴--边长变化
Image []float64 //图形y轴--角度变化
RANGE_MAX float64
EPSILON float64
}
type Vector2 struct {
X float64
Y float64
}
type Polygon struct {
Vertices []Vector2
Edges []Vector2
Perimeter float64
EdgeCount int
VertexCount int
}
type AlignedTF struct {
SharedRangeEvents []float64
EPSILON float64
TurningFunctionA TurningFunction
TurningFunctionB TurningFunction
}
type Matcher struct {
TurningFunctionA TurningFunction
ReshapedTurningFunctionB []TurningFunction
}
func (tf *TurningFunction) TurningFunctionInit() {
tf.Range = make([]float64, 0)
tf.Image = make([]float64, 0)
}
func (tf *TurningFunction) TurningFunctionInitWithPy(poly Polygon) {
tf.Range = tf.CalculateNormalizedRange(poly)
tf.Image = tf.CalculateImage(poly)
}
func (tf *TurningFunction) TurningFunctionInitWithTF(tfs TurningFunction) {
tf.Range = tfs.Range
tf.Image = tfs.Image
}
//CalculateImage 计算角度变化
func (tf *TurningFunction) CalculateImage(poly Polygon) []float64 {
image := make([]float64, 0)
edges := poly.Edges
var angleAccumulator float64 = 0
image = append(image, angleAccumulator)
for i := 0; i < len(edges); i++ {
edgeA := edges[i]
edgeB := edges[(i+1)%len(edges)]
var angle float64
angle = edgeA.Dot(edgeB)
lenA := edgeA.GetLength()
lenB := edgeB.GetLength()
angle /= lenA * lenB
angle = math.Acos(angle)
angleAccumulator += edgeA.CrossDirection(edgeB) * angle
image = append(image, angleAccumulator)
}
return image
}
//ValueAt 二分查找
func (tf *TurningFunction) ValueAt(x float64) float64 {
tf.EPSILON = 1e-10
low := 0
high := len(tf.Range)
for low <= high {
mid := (low + high) / 2
if math.Abs(tf.Range[mid]-x) < tf.EPSILON {
return tf.Image[mid]
}
if tf.Range[mid] < x {
if mid+1 < len(tf.Range) {
if tf.Range[mid+1] > x {
return tf.Image[mid]
}
}
low = mid + 1
} else if tf.Range[mid] > x {
if mid-1 >= 0 {
if tf.Range[mid-1] < x {
return tf.Image[mid-1]
}
}
high = mid - 1
}
}
return -1
}
//CalculateNormalizedRange 计算边长变化
func (tf *TurningFunction) CalculateNormalizedRange(poly Polygon) []float64 {
var ranges = make([]float64, 0)
tf.RANGE_MAX = 1
polygonPerimeter := poly.Perimeter
edges := poly.Edges
var perimeterAccumulator float64 = 0
for i := 0; i < len(edges); i++ {
segmentPerimeter := edges[i].GetLength()
currentSegment := segmentPerimeter / polygonPerimeter
perimeterAccumulator += currentSegment * tf.RANGE_MAX
ranges = append(ranges, perimeterAccumulator)
}
return ranges
}
func (v2 *Vector2) Vector2Init(x, y float64) {
v2.X = x
v2.Y = y
}
func (v2 *Vector2) GetLength() float64 {
return math.Sqrt(v2.X*v2.X + v2.Y*v2.Y)
}
func (v2 *Vector2) CrossDirection(vec Vector2) float64 {
zCross := v2.X*vec.X - v2.Y*vec.Y
if zCross > 0 {
return 1.0
} else if zCross < 0 {
return -1.0
} else {
return 0.0
}
}
//Dot 向量代数函数
func (v2 Vector2) Dot(vec Vector2) float64 {
return v2.X*vec.X + v2.Y*vec.Y
}
func (v2 *Vector2) ToString() string {
return fmt.Sprintf("( %f, %f )", v2.X, v2.Y)
}
//初始化，类似构造函数
func (p *Polygon) PolygonInit() {
p.Vertices = make([]Vector2, 0)
p.Edges = make([]Vector2, 0)
}
func (p *Polygon) PolygonInitWithParam(vector2Lst []Vector2) {
p.Vertices = vector2Lst
p.Edges = make([]Vector2, 0)
for _, item := range vector2Lst {
p.Perimeter += item.GetLength()
}
}
///
/// 添加顶点
///
///
func (p *Polygon) AddVertex(vector2 Vector2) {
var lastVertex Vector2
p.Vertices = append(p.Vertices, vector2)
p.VertexCount++
if len(p.Vertices) == 1 {
return
} else {
lastVertex = p.Vertices[len(p.Vertices)-2]
}
vec := new(Vector2)
vec.Vector2Init(vector2.X-lastVertex.X, vector2.Y-lastVertex.Y)
p.AddEdge(*vec)
p.EdgeCount++
}
///
/// 添加边
func (p *Polygon) AddEdge(edge Vector2) {
p.Edges = append(p.Edges, edge)
p.Perimeter += edge.GetLength()
}
func (p *Polygon) ToString() string {
return fmt.Sprintf("边数：%d ,顶点数：%d ,周长：%f", p.EdgeCount, p.VertexCount, p.Perimeter)
}
func (atf *AlignedTF) AlignedTFInitWithParam(tfA, tfB TurningFunction) {
atf.EPSILON = 1e-10
atf.TurningFunctionA = tfA
atf.TurningFunctionB = tfB
rangeA := tfA.Range
rangeB := tfB.Range
atf.SharedRangeEvents = make([]float64, 0)
iterA := 0
iterB := 0
// assuming both ranges start at 0
atf.SharedRangeEvents = append(atf.SharedRangeEvents, rangeA[iterA])
iterA++
for iterA != len(rangeA) {
// *iterA == *iterB
if rangeB[iterB]-rangeA[iterA] > atf.EPSILON {
atf.SharedRangeEvents = append(atf.SharedRangeEvents, rangeA[iterA])
if iterA != len(rangeA) {
iterA++
continue
}
}
// *iterA > *iterB
if rangeA[iterA]-rangeB[iterB] > atf.EPSILON {
atf.SharedRangeEvents = append(atf.SharedRangeEvents, rangeB[iterB])
if iterB != len(rangeB) {
iterB++
continue
}
}
// *iterA < *iterB
if rangeA[iterA]-rangeB[iterB] < atf.EPSILON {
atf.SharedRangeEvents = append(atf.SharedRangeEvents, rangeA[iterA])
iterA++
iterB++
continue
}
}
for iterB != len(rangeB) {
atf.SharedRangeEvents = append(atf.SharedRangeEvents, rangeB[iterB])
}
}
func (atf *AlignedTF) Distance() float64 {
var dis float64 = 0
for i := 0; i < len(atf.SharedRangeEvents)-1; i++ {
currentX := atf.SharedRangeEvents[i]
imageA := atf.TurningFunctionA.ValueAt(currentX)
imageB := atf.TurningFunctionB.ValueAt(currentX)
nextX := atf.SharedRangeEvents[i+1]
dis += (nextX - currentX) * (imageB - imageA) * (imageB - imageA)
}
dis = math.Sqrt(dis)
return dis
}
func (m *Matcher) MatcherInit(polyA, polyB Polygon) {
tf := new(TurningFunction)
tf.TurningFunctionInitWithPy(polyA)
m.TurningFunctionA = *tf
m.ReshapedTurningFunctionB = m.GenerateReshapedFunction(polyB)
}
// 更改多边形的顶点顺序
// 将index作为首个顶点，构造多边形
func (m *Matcher) GenerateReshapedPolygon(poly Polygon, startIndex int) Polygon {
reshapedPoly := new(Polygon)
for vertex := startIndex; vertex < len(poly.Vertices); vertex++ {
reshapedPoly.AddVertex(poly.Vertices[vertex])
}
for vertex := 0; vertex < startIndex; vertex++ {
reshapedPoly.AddVertex(poly.Vertices[vertex])
}
return *reshapedPoly
}
// 计算多边形的所有tf
func (m *Matcher) GenerateReshapedFunction(poly Polygon) []TurningFunction {
numReshapedFuncs := poly.EdgeCount
reshapedFunc := make([]TurningFunction, 0)
for i := 0; i < numReshapedFuncs; i++ {
startIndex := i
reshapedPoly := m.GenerateReshapedPolygon(poly, startIndex)
tf := new(TurningFunction)
tf.TurningFunctionInitWithPy(reshapedPoly) //
reshapedFunc = append(reshapedFunc, *tf)
}
return reshapedFunc
}
func (m *Matcher) Distance() float64 {
var minDistance = float64(int(^uint(0) >> 1))
for i := 0; i < len(m.ReshapedTurningFunctionB); i++ {
atf := new(AlignedTF)
atf.AlignedTFInitWithParam(m.TurningFunctionA, m.ReshapedTurningFunctionB[i])
dis := atf.Distance()
if dis < minDistance {
minDistance = dis
}
}
return minDistance
}
暑期编程PK赛
得CSDN机械键盘等精美礼品！
