package routing

import (
	

	
	
)

// estimateRouteCost scores one candidate route against the routes that have
// already been selected. Crossing semantics belong to routing: intersections
// at the exact end of an axis-aligned segment are bends off a shared route,
// not route crossings.
func estimateRouteCost( layoutgraph.Edges,  *layoutgraph.Edge) float64 {
	 := .Length()
	 *= math.Pow(turnPenalty, float64(len(.Points)-2))

	var  int64
	for ,  := range  {
		if  ==  {
			continue
		}
		 += countNonSharedCrossings(, )
	}
	 += layoutgraph.CrossingCostWeight * float64()
	return 
}

func countNonSharedCrossings(,  *layoutgraph.Edge) int64 {
	var  int64
	for  := 0;  < len(.Points)-1; ++ {
		for  := 0;  < len(.Points)-1; ++ {
			if isNonSharedCrossing(, , , ) {
				++
			}
		}
	}
	return 
}

func isNonSharedCrossing(,  *layoutgraph.Edge, ,  int) bool {
	if !nonParallelIntersection(
		.Points[],
		.Points[+1],
		.Points[],
		.Points[+1],
	) {
		return false
	}

	// Skip intersections at the exact end of the segment to avoid counting
	// bends off shared edges.
	 := .Points[].X
	 := .Points[].Y
	if  == .Points[+1].X &&
		( == .Points[].X ||  == .Points[+1].X) {
		return false
	}
	if  == .Points[+1].Y &&
		( == .Points[].Y ||  == .Points[+1].Y) {
		return false
	}
	return true
}

func equalSigns(,  float64) bool {
	return  > 0 &&  > 0 ||  == 0 &&  == 0 ||  < 0 &&  < 0
}

// nonParallelIntersection reports whether segments ab and cd intersect at an
// angle. Collinear overlap is intentionally not a routing crossing.
func nonParallelIntersection(, , ,  *geo.Point) bool {
	 := orientation(, , )
	 := orientation(, , )
	if equalSigns(, ) {
		return false
	}

	 := orientation(, , )
	 := orientation(, , )
	return !equalSigns(, )
}