// Copyright (c) 2010, 2020 Kiel University and others.
// Copyright (c) 2014, 2015 Kiel University and others.
// Copyright (c) 2017, 2018 Kiel University and others.
// Copyright (c) 2018 Kiel University and others.
// Copyright (c) 2026 The elk-go Authors.
//
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License 2.0 which is available at
// https://www.eclipse.org/legal/epl-2.0.
//
// SPDX-License-Identifier: EPL-2.0

package p5edges

import (
	
	

	
	basegraph 
	
	
)

const splineStraightVerticalDifference = 0.2

// SplineEdgeRouter ports the ELK 0.8.1 spline segment dependency graph,
// ranking, layer spacing, and default sloppy control-point construction.
type SplineEdgeRouter struct{}

type splineSide uint8

const (
	splineLeft splineSide = iota
	splineRight
)

type splineDependency struct {
	source, target *splineSegment
	weight         int
}

type splineSegment struct {
	edge                  layered.LEdgeID
	leftPorts, rightPorts []layered.LPortID
	outgoing, incoming    []*splineDependency
	mark                  int
	inWeight, outWeight   int
	rank                  int
	straight              bool
	topY, bottomY         float64
	centerY               float64
	sourceY, targetY      float64
	normalSource          bool
	normalTarget          bool
	boundingX             float64
	boundingWidth         float64
	xDelta                float64
	westOfInitialLayer    bool
}

func (*SplineEdgeRouter) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) layered.ProcessorConfiguration {
	 := basegraph.Get(&.Graph().Properties, layered.GraphProperties)
	var  layered.ProcessorConfiguration
	.
		AddBefore(layered.PhaseNodeOrdering, layered.InvertedPortProcessor).
		AddAfter(layered.PhaseEdgeRouting, layered.FinalSplineBendpointsCalculator)
	if &layered.GraphPropertySelfLoops != 0 {
		.
			AddBefore(layered.PhaseCycleBreaking, layered.SelfLoopPreprocessor).
			AddBefore(layered.PhaseNodePlacement, layered.SelfLoopPortRestorer).
			AddBefore(layered.PhaseNodePlacement, layered.SelfLoopRouter).
			AddAfter(layered.PhaseEdgeRouting, layered.SelfLoopPostprocessor)
	}
	if &layered.GraphPropertyCenterLabels != 0 {
		.
			AddBefore(layered.PhaseLayering, layered.LabelDummyInserter).
			AddBefore(layered.PhaseNodePlacement, layered.LabelDummySwitcher).
			AddBefore(layered.PhaseNodePlacement, layered.LabelSideSelector).
			AddAfter(layered.PhaseEdgeRouting, layered.LabelDummyRemover)
	}
	if &layered.GraphPropertyNorthSouthPorts != 0 {
		.
			AddBefore(layered.PhaseNodeOrdering, layered.NorthSouthPortPreprocessor).
			AddBefore(layered.PhaseEdgeRouting, layered.NorthSouthPortPostprocessor)
	}
	if &layered.GraphPropertyEndLabels != 0 {
		.
			AddBefore(layered.PhaseNodePlacement, layered.LabelSideSelector).
			AddBefore(layered.PhaseNodePlacement, layered.EndLabelPreprocessor).
			AddAfter(layered.PhaseEdgeRouting, layered.EndLabelPostprocessor)
	}
	return 
}

func (*SplineEdgeRouter) ( *layered.LGraphArena,  layered.LGraphID) error {
	 := .Graph()
	if len(.Layers) == 0 {
		.Size.X = 0
		return nil
	}
	 := basegraph.Get(&.Properties, layered.SplineRoutingModeOption)
	if  != layered.SplineRoutingSloppy &&  != layered.SplineRoutingConservative &&
		 != layered.SplineRoutingConservativeSoft {
		return fmt.Errorf("layered: spline routing mode %v is not implemented", )
	}

	 := basegraph.Get(&.Properties, layered.SpacingNodeNodeBetweenLayers)
	 := basegraph.Get(&.Properties, layered.SpacingEdgeNodeBetweenLayers)
	 := basegraph.Get(&.Properties, layered.SpacingEdgeEdgeBetweenLayers)
	 := basegraph.Get(&.Properties, layered.SplineSloppyLayerSpacingFactor)
	 := basegraph.Get(&.Properties, layered.Random)
	if  == nil {
		 = javacompat.NewRandom(1)
	}

	 := .Layers[0]
	 := allExternalWestOrEastPorts(, .Layer().Nodes)
	 := .Layers[len(.Layers)-1]
	 := allExternalWestOrEastPorts(, .Layer().Nodes)

	 := 0.0
	var  *layered.LayerID
	for  := 0;  <= len(.Layers); ++ {
		var  *layered.LayerID
		if  < len(.Layers) {
			 := .Layers[]
			 = &
		}
		 := collectSplineSegments(, , )
		createSplineDependencies(, )
		breakSplineCycles(, )
		numberSplineSegments()
		 := 0
		for ,  := range  {
			if !.straight {
				 = max(, .rank+1)
			}
		}

		 := 
		 := 0.0
		 :=  == nil ||  && * == 
		 :=  == nil ||  && * == 
		if  > 0 {
			 := 0.0
			if  != nil {
				 += 
			}
			 += float64(-1) * 
			if  != nil {
				 += 
				 = math.Max(, splineSloppySpacing(, *, , , ))
			}
			if  <  && ! && ! {
				 = ( - ) / 2
				 = 
			}
			 += 
		} else if ! && ! {
			 += 
		}
		if  != nil {
			placeNodesHorizontally(, *, )
		}
		for ,  := range  {
			.boundingX = 
			.boundingWidth =  - 
			.xDelta = 
			.westOfInitialLayer =  == nil
			writeSplineControls(, , , , )
		}
		 = 
		if  != nil {
			 += .Layer(*).Size.X
		}
		 = 
	}
	.Size.X = 
	return nil
}

func collectSplineSegments(
	 *layered.LGraphArena,
	,  *layered.LayerID,
) []*splineSegment {
	 := make(map[layered.LPortID]struct{})
	 := make(map[layered.LPortID]struct{})
	 := make([]layered.LEdgeID, 0)
	 := make(map[layered.LEdgeID]struct{})
	 := func( layered.LEdgeID) {
		if ,  := []; ! {
			[] = struct{}{}
			 = append(, )
		}
	}
	if  != nil {
		for ,  := range .Layer(*).Nodes {
			for ,  := range .NodePortsOnSide(, layered.EastSide) {
				[] = struct{}{}
				for ,  := range .Port().OutgoingEdges {
					if .EdgeIsSelfLoop() {
						continue
					}
					 := *.Edge().Target
					 := .Node(*.Port().Node)
					if  != nil && .Layer != nil && *.Layer == * {
						[] = struct{}{}
						()
					} else if .Layer != nil && *.Layer == * {
						[] = struct{}{}
						()
					}
				}
			}
		}
	}
	if  != nil {
		for ,  := range .Layer(*).Nodes {
			for ,  := range .NodePortsOnSide(, layered.WestSide) {
				[] = struct{}{}
				for ,  := range .Port().OutgoingEdges {
					if .EdgeIsSelfLoop() {
						continue
					}
					 := *.Edge().Target
					 := .Node(*.Port().Node)
					if  != nil && .Layer != nil && *.Layer == * {
						[] = struct{}{}
						()
					} else if .Layer != nil && *.Layer == * {
						[] = struct{}{}
						()
					}
				}
			}
		}
	}

	 := make([]*splineSegment, 0, len())
	for ,  := range  {
		 := .Edge()
		,  := *.Source, *.Target
		 := &splineSegment{edge: }
		if ,  := [];  {
			.leftPorts = append(.leftPorts, )
		} else {
			.rightPorts = append(.rightPorts, )
		}
		if ,  := [];  {
			.leftPorts = append(.leftPorts, )
		} else {
			.rightPorts = append(.rightPorts, )
		}
		,  := absolutePortAnchor(, ).Y, absolutePortAnchor(, ).Y
		.sourceY, .targetY = , 
		.normalSource = splineNormalNode(.Node(.EdgeSourceNode()).Type)
		.normalTarget = splineNormalNode(.Node(.EdgeTargetNode()).Type)
		.straight = math.Abs(-) < splineStraightVerticalDifference
		.centerY = ( + ) / 2
		if  <  {
			.topY = 0.1*.centerY + 0.9*
			.bottomY = 0.1*.centerY + 0.9*
		} else {
			.topY = 0.1*.centerY + 0.9*
			.bottomY = 0.1*.centerY + 0.9*
		}
		 = append(, )
	}
	return 
}

func createSplineDependencies( *layered.LGraphArena,  []*splineSegment) {
	for ,  := range  {
		for ,  := range [+1:] {
			if .topY > .bottomY || .topY > .bottomY {
				continue
			}
			,  := 0, 0
			for ,  := range .rightPorts {
				if splineBetween(absolutePortAnchor(, ).Y, .topY, .bottomY) {
					++
				}
			}
			for ,  := range .leftPorts {
				if splineBetween(absolutePortAnchor(, ).Y, .topY, .bottomY) {
					--
				}
			}
			for ,  := range .rightPorts {
				if splineBetween(absolutePortAnchor(, ).Y, .topY, .bottomY) {
					++
				}
			}
			for ,  := range .leftPorts {
				if splineBetween(absolutePortAnchor(, ).Y, .topY, .bottomY) {
					--
				}
			}
			if  <  {
				addSplineDependency(, , -)
			} else if  <  {
				addSplineDependency(, , -)
			} else {
				addSplineDependency(, , 0)
				addSplineDependency(, , 0)
			}
		}
	}
}

func splineBetween(, ,  float64) bool {
	return  >= math.Min(, ) &&  <= math.Max(, )
}

func addSplineDependency(,  *splineSegment,  int) {
	 := &splineDependency{source: , target: , weight: }
	.outgoing = append(.outgoing, )
	.incoming = append(.incoming, )
}

func breakSplineCycles( []*splineSegment,  *javacompat.Random) {
	,  := make([]*splineSegment, 0), make([]*splineSegment, 0)
	 := -1
	for ,  := range  {
		.mark = 
		--
		.inWeight, .outWeight = 0, 0
		for ,  := range .outgoing {
			.outWeight += .weight
		}
		for ,  := range .incoming {
			.inWeight += .weight
		}
		if .outWeight == 0 {
			 = append(, )
		} else if .inWeight == 0 {
			 = append(, )
		}
	}
	 := append([]*splineSegment(nil), ...)
	 := len()
	,  := +1, -1
	for len() > 0 {
		for len() > 0 {
			 := [0]
			 = [1:]
			if !removeSplineSegment(&, ) {
				continue
			}
			.mark = 
			--
			updateSplineNeighbors(, &, &)
		}
		for len() > 0 {
			 := [0]
			 = [1:]
			if !removeSplineSegment(&, ) {
				continue
			}
			.mark = 
			++
			updateSplineNeighbors(, &, &)
		}
		if len() == 0 {
			break
		}
		 := math.MinInt
		 := make([]*splineSegment, 0)
		for ,  := range  {
			 := .outWeight - .inWeight
			if  >=  {
				if  >  {
					 = [:0]
					 = 
				}
				 = append(, )
			}
		}
		 := [.NextIntN(int32(len()))]
		removeSplineSegment(&, )
		.mark = 
		++
		updateSplineNeighbors(, &, &)
	}
	 := len() + 1
	for ,  := range  {
		if .mark <  {
			.mark += 
		}
	}
	for ,  := range  {
		 := .outgoing[:0]
		for ,  := range .outgoing {
			if .mark <= .target.mark {
				 = append(, )
				continue
			}
			.target.incoming = removeSplineDependency(.target.incoming, )
			if .weight > 0 {
				 := .target
				.source = 
				.outgoing = append(.outgoing, )
				.target = 
				.incoming = append(.incoming, )
			}
		}
		.outgoing = 
	}
}

func removeSplineSegment( *[]*splineSegment,  *splineSegment) bool {
	for ,  := range * {
		if  ==  {
			* = append((*)[:], (*)[+1:]...)
			return true
		}
	}
	return false
}

func removeSplineDependency( []*splineDependency,  *splineDependency) []*splineDependency {
	for ,  := range  {
		if  ==  {
			return append([:], [+1:]...)
		}
	}
	return 
}

func updateSplineNeighbors( *splineSegment, ,  *[]*splineSegment) {
	for ,  := range .outgoing {
		if .target.mark < 0 && .weight > 0 {
			.target.inWeight -= .weight
			if .target.inWeight <= 0 && .target.outWeight > 0 {
				* = append(*, .target)
			}
		}
	}
	for ,  := range .incoming {
		if .source.mark < 0 && .weight > 0 {
			.source.outWeight -= .weight
			if .source.outWeight <= 0 && .source.inWeight > 0 {
				* = append(*, .source)
			}
		}
	}
}

func numberSplineSegments( []*splineSegment) {
	,  := make([]*splineSegment, 0), make([]*splineSegment, 0)
	for ,  := range  {
		.rank = 0
		.inWeight, .outWeight = len(.incoming), len(.outgoing)
		if .inWeight == 0 {
			 = append(, )
		}
		if .outWeight == 0 && len(.leftPorts) == 0 {
			 = append(, )
		}
	}
	 := -1
	for len() > 0 {
		 := [0]
		 = [1:]
		for ,  := range .outgoing {
			 := .target
			.rank = max(.rank, .rank+1)
			 = max(, .rank)
			.inWeight--
			if .inWeight == 0 {
				 = append(, )
			}
		}
	}
	if  < 0 {
		return
	}
	for ,  := range  {
		.rank = 
	}
	for len() > 0 {
		 := [0]
		 = [1:]
		for ,  := range .incoming {
			 := .source
			if len(.leftPorts) > 0 {
				continue
			}
			.rank = min(.rank, .rank-1)
			.outWeight--
			if .outWeight == 0 {
				 = append(, )
			}
		}
	}
}

func splineSloppySpacing(
	 *layered.LGraphArena,
	 layered.LayerID,
	, ,  float64,
) float64 {
	 := 0.0
	for ,  := range .Layer().Nodes {
		 := 0.0
		for ,  := range .NodeIncomingEdges() {
			 := .Edge()
			 = math.Max(, math.Abs(absolutePortAnchor(, *.Target).Y-absolutePortAnchor(, *.Source).Y))
		}
		 = math.Max(, )
	}
	return  * math.Min(1, /) * 
}

func writeSplineControls(
	 *layered.LGraphArena,
	 *splineSegment,
	 layered.SplineRoutingMode,
	,  float64,
) {
	 := .Edge(.edge)
	if .Source == nil || .Target == nil {
		return
	}
	 := .boundingX + .boundingWidth/2
	 := make(geometry.Chain, 0, 4)
	if .straight {
		 = append(, geometry.Point{X: , Y: .centerY})
	} else if  != layered.SplineRoutingSloppy ||
		.Port(*.Source).Side == layered.WestSide ||
		.Port(*.Target).Side == layered.EastSide {
		 := .boundingX
		if !.westOfInitialLayer {
			 += 
		}
		 += .xDelta + float64(.rank)*
		,  := .boundingX, .boundingX+.boundingWidth
		if .Port(*.Source).Side == layered.WestSide {
			 = .boundingX + .boundingWidth
		}
		if .Port(*.Target).Side == layered.EastSide {
			 = .boundingX
		}
		 = append(,
			geometry.Point{X: , Y: .sourceY},
			geometry.Point{X: , Y: .sourceY},
			geometry.Point{X: , Y: .targetY},
			geometry.Point{X: , Y: .targetY})
	} else {
		if !.normalSource {
			 = append(,
				geometry.Point{X: .boundingX, Y: .sourceY},
				geometry.Point{X: , Y: .sourceY})
		}
		if !.normalTarget {
			 = append(,
				geometry.Point{X: , Y: .targetY},
				geometry.Point{X: .boundingX + .boundingWidth, Y: .targetY})
		}
		if .normalSource && .normalTarget {
			// The degree-dependent ordinate is evaluated by the final processor,
			// after SelfLoopPostprocessor has reattached hidden loop edges.
			 = append(, geometry.Point{X: , Y: math.NaN()})
		}
	}
	.BendPoints = .BendPoints[:0]
	basegraph.Set(&.Properties, layered.SplineControlPointSegments, []geometry.Chain{})
	basegraph.Set(&.Properties, layered.SplineCompactionSegments,
		[]layered.SplineCompactionSegment{{
			BoundingBox: geometry.Rectangle{
				X:      .boundingX,
				Y:      math.Min(.sourceY, .targetY),
				Width:  .boundingWidth,
				Height: math.Abs(.sourceY - .targetY),
			},
			Straight:         .straight,
			Edge:             .edge,
			SourcePort:       *.Source,
			TargetPort:       *.Target,
			SourceY:          .sourceY,
			TargetY:          .targetY,
			NormalSource:     .normalSource,
			NormalTarget:     .normalTarget,
			WestOfFirstLayer: .westOfInitialLayer,
			XDelta:           .xDelta,
			Rank:             .rank,
		}})
}

func splineNormalNode( layered.NodeType) bool {
	return  == layered.NormalNode ||  == layered.BreakingPointNode
}

// FinalizeSplineBendpoints mirrors FinalSplineBendpointsCalculator after long
// edges have been joined. It assembles the per-between-layer NUB control
// polygons and raises every inner knot to cubic multiplicity, yielding the
// Bezier control-point chain emitted by elkjs.
func ( *layered.LGraphArena,  layered.LGraphID) {
	for  := range .Edges {
		 := layered.LEdgeID()
		 := .Edge()
		if .Source == nil || .Target == nil || .EdgeIsSelfLoop() {
			continue
		}
		if .NodeGraph(.EdgeSourceNode()) !=  {
			continue
		}
		,  := basegraph.TryGet(&.Properties, layered.SplineControlPointSegments)
		if ! || len() == 0 {
			continue
		}
		if ,  := basegraph.TryGet(
			&.Properties, layered.SplineCompactionSegments,
		);  && len() == len() {
			applyPostCompactionSplineRouting(
				, , , , )
		}
		resolveSloppySplineCenters(, , )
		 := geometry.Chain{absolutePortAnchor(, *.Source)}
		var  geometry.Point
		 := false
		for ,  := range  {
			if len() == 0 {
				continue
			}
			if  {
				 = append(, geometry.Point{
					X: (.X + [0].X) / 2,
					Y: (.Y + [0].Y) / 2,
				})
				 = false
			} else {
				 = true
			}
			 = [len()-1]
			 = append(, ...)
		}
		 = append(, absolutePortAnchor(, *.Target))
		if basegraph.Get(&.Graph().Properties, layered.SplineRoutingModeOption) == layered.SplineRoutingConservative {
			 = insertSplineStraighteningControls(
				, .Port(*.Source).Side, .Port(*.Target).Side)
		}
		.BendPoints = CubicNUBToBezier()
		basegraph.Unset(&.Properties, layered.SplineControlPointSegments)
		basegraph.Unset(&.Properties, layered.SplineCompactionSegments)
	}
}

// applyPostCompactionSplineRouting implements FinalSplineBendpointsCalculator's
// segmentAllowsSloppyRouting check. Horizontal compaction can pull an initial
// or final curved segment far enough from its incident node that ELK switches
// that segment from sloppy to conservative control points.
func applyPostCompactionSplineRouting(
	 *layered.LGraphArena,
	 layered.LGraphID,
	 layered.LEdgeID,
	 []geometry.Chain,
	 []layered.SplineCompactionSegment,
) {
	 := .Graph()
	if basegraph.Get(&.Properties, layered.PostCompactionStrategy) ==
		layered.GraphCompactionNone ||
		basegraph.Get(&.Properties, layered.SplineRoutingModeOption) !=
			layered.SplineRoutingSloppy {
		return
	}
	 := basegraph.Get(
		&.Properties, layered.SpacingEdgeNodeBetweenLayers)
	 := basegraph.Get(
		&.Properties, layered.SpacingEdgeEdgeBetweenLayers)

	for  := range  {
		 := &[]
		if .Straight || !(.NormalSource || .NormalTarget) {
			continue
		}
		// Inverted-port segments always use their dedicated four-control-point
		// route, independently of sloppy routing.
		if .Port(.SourcePort).Side == layered.WestSide ||
			.Port(.TargetPort).Side == layered.EastSide {
			continue
		}
		 := true
		if  == 0 {
			 := .Node(.EdgeSourceNode())
			if .Layer != nil {
				 := .Layer(*.Layer).Size.X - .Size.X/2
				 := .BoundingBox.X -
					(.Position.X + .Size.X)
				if  >  {
					 = false
				}
			}
		}
		if  == len()-1 {
			 := .Node(.EdgeTargetNode())
			if .Layer != nil {
				 := .Layer(*.Layer).Size.X - .Size.X/2
				 := .Position.X - .BoundingBox.MaxX()
				if  >  {
					 = false
				}
			}
		}
		if  {
			continue
		}

		 := .BoundingBox.X
		 := .BoundingBox.MaxX()
		 := 
		if !.WestOfFirstLayer {
			 += 
		}
		 += .XDelta + float64(.Rank)*
		[] = geometry.Chain{
			{X: , Y: .SourceY},
			{X: , Y: .SourceY},
			{X: , Y: .TargetY},
			{X: , Y: .TargetY},
		}
	}
}

func insertSplineStraighteningControls(
	 geometry.Chain,
	,  layered.PortSide,
) geometry.Chain {
	if len() < 2 {
		return 
	}
	,  := [0], [1]
	 := splineDirection()
	.X *= 5
	.Y *= 5
	 := .Sub()
	 := .Add(geometry.Point{
		X: splineAbsoluteMinimum(.X, .X),
		Y: splineAbsoluteMinimum(.Y, .Y),
	})
	 = append(, geometry.Point{})
	copy([2:], [1:])
	[1] = 

	 := len() - 1
	,  := [], [-1]
	 := splineDirection()
	.X *= 5
	.Y *= 5
	 := .Sub()
	 := .Add(geometry.Point{
		X: splineAbsoluteMinimum(.X, .X),
		Y: splineAbsoluteMinimum(.Y, .Y),
	})
	 = append(, geometry.Point{})
	copy([+1:], [:])
	[] = 
	return 
}

func splineDirection( layered.PortSide) geometry.Point {
	switch  {
	case layered.NorthSide:
		return geometry.Point{Y: -1}
	case layered.EastSide:
		return geometry.Point{X: 1}
	case layered.SouthSide:
		return geometry.Point{Y: 1}
	case layered.WestSide:
		return geometry.Point{X: -1}
	default:
		return geometry.Point{}
	}
}

func splineAbsoluteMinimum(,  float64) float64 {
	if math.Abs() < math.Abs() {
		return 
	}
	return 
}

func resolveSloppySplineCenters(
	 *layered.LGraphArena,
	 layered.LEdgeID,
	 []geometry.Chain,
) {
	 := false
	for ,  := range  {
		for ,  := range  {
			 =  || math.IsNaN(.Y)
		}
	}
	if ! {
		return
	}
	 := .Edge()
	,  := absolutePortAnchor(, *.Source), absolutePortAnchor(, *.Target)
	,  := 0, 0
	for ,  := range .Node(.EdgeTargetNode()).Ports {
		 += len(.Port().IncomingEdges)
	}
	for ,  := range .Node(.EdgeSourceNode()).Ports {
		 += len(.Port().OutgoingEdges)
	}
	 := 0
	if  >  {
		 = 1
	} else if  <  {
		 = -1
	}
	 := (.Y+.Y)/2 + (.Y-.Y)*(0.4*float64())
	for  := range  {
		for  := range [] {
			if math.IsNaN([][].Y) {
				[][].Y = 
			}
		}
	}
}

// CubicNUBToBezier converts a clamped uniform cubic B-spline control polygon
// to ELK's concatenated Bezier control-point representation.
func ( geometry.Chain) geometry.Chain {
	const  = 3
	 = .Clone()
	for len() < +1 {
		 = append(geometry.Chain{[0]}, ...)
	}
	 := len() - 
	 := make([]float64, 0, len()++1)
	for  := 0;  <= ; ++ {
		 = append(, 0)
	}
	for  := 1;  < ; ++ {
		 = append(, float64()/float64())
	}
	for  := 0;  <= ; ++ {
		 = append(, 1)
	}
	 := append([]float64(nil), [+1:len()--1]...)
	for  := 0;  < len(); {
		 := []
		 := 1
		for + < len() && math.Abs([+]-) < 1e-6 {
			++
		}
		for  := ;  < ; ++ {
			,  = insertSplineKnot(, , , )
		}
		 += 
	}
	return append(geometry.Chain(nil), [1:len()-1]...)
}

func insertSplineKnot(
	 geometry.Chain,
	 []float64,
	 int,
	 float64,
) (geometry.Chain, []float64) {
	 := len() - 1
	 := len() - 1
	 := 
	for +1 < len() &&  >= [+1]-1e-12 {
		++
	}
	if  >  {
		 = 
	}
	 := 0
	for ,  := range  {
		if math.Abs(-) < 1e-9 {
			++
		}
	}
	 := make([]float64, +2)
	copy([:+1], [:+1])
	[+1] = 
	copy([+2:], [+1:])
	 := make(geometry.Chain, +2)
	copy([:-+1], [:-+1])
	copy([-+1:], [-:])
	for  :=  -  + 1;  <= -; ++ {
		 := ( - []) / ([+] - [])
		[] = geometry.Point{
			X: (1-)*[-1].X + *[].X,
			Y: (1-)*[-1].Y + *[].Y,
		}
	}
	return , 
}