http://mathling.com/geometric/edge  library module

Variable: $precision as xs:integer

Variable: $EDGE-RESERVED as xs:string*

Variable: $ARC-RESERVED as xs:string*

Variable: $ELLIPSE-ARC-RESERVED as xs:string*

Variable: $QUAD-RESERVED as xs:string*

Variable: $CUBIC-RESERVED as xs:string*

Function: edge
declare function edge($from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $d as xs:double,
  $properties as map(xs:string,item()*)) as map(xs:string,item()*)

edge()
Make an edge

Params

• from as map(xs:string,item()*): starting point
• to as map(xs:string,item()*): ending point
• d as xs:double: weight of the edge (used by spanning graph as distance)
• properties as map(xs:string,item()*): additional edge properties

Returns

• map(xs:string,item()*)

declare function this:edge(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $d as xs:double,
  $properties as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  util:merge-into($properties,
    map {
      "kind": "edge",
      "u": $from,
      "v": $to,
      "d": $d
    }
  )
}

Function: edge
declare function edge($from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $d as xs:double) as map(xs:string,item()*)

edge()
Make an edge

Params

• from as map(xs:string,item()*): starting point
• to as map(xs:string,item()*): ending point
• d as xs:double: the weight of the edge

Returns

• map(xs:string,item()*)

declare function this:edge(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $d as xs:double
) as map(xs:string,item()*)
{
  map {
    "kind": "edge",
    "u": $from,
    "v": $to,
    "d": $d
  }
}

Function: edge
declare function edge($from as map(xs:string,item()*),
  $to as map(xs:string,item()*)) as map(xs:string,item()*)

edge()
Make an edge

Params

• from as map(xs:string,item()*): starting point
• to as map(xs:string,item()*): ending point

Returns

• map(xs:string,item()*)

declare function this:edge(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  this:edge($from, $to, 0)
}

Function: kind
declare function kind($edge as map(xs:string,item()*)) as xs:string

Params

• edge as map(xs:string,item()*)

Returns

• xs:string

declare function this:kind($edge as map(xs:string,item()*)) as xs:string
{
  $edge("kind")
}

Function: start
declare function start($edge as map(xs:string,item()*)) as map(xs:string,item()*)

start()
Accessor for starting point of edge

Params

• edge as map(xs:string,item()*): The edge

Returns

• map(xs:string,item()*)

declare function this:start($edge as map(xs:string,item()*)) as map(xs:string,item()*)
{
  switch (this:kind($edge))
  case "edge" return $edge("u")
  case "quad" return $edge("u")
  case "cubic" return $edge("u")
  case "arc" return (
    let $start := $edge("start")
    return
      if (exists($start)) then $start
      else (
        let $circle := $edge("circle")
        let $center := ellipse:center($circle)
        let $r := ellipse:radius($circle)
        let $from := util:radians($edge("from-angle"))
        return (
          point:point(
            point:px($center)+math:cos($from)*$r,
            point:py($center)+math:sin($from)*$r
          )
        )
      )
    )
  case "ellipse-arc" return $edge("start")
  default return errors:error("GEOM-BADREGION", ($edge, "start"))
}

Function: start
declare function start($edge as map(xs:string,item()*), $start as map(xs:string,item()*)) as map(xs:string,item()*)

start()
Settor for starting point of edge

Params

• edge as map(xs:string,item()*): The edge
• start as map(xs:string,item()*): Starting point of edge

Returns

• map(xs:string,item()*)

declare function this:start($edge as map(xs:string,item()*), $start as map(xs:string,item()*)) as map(xs:string,item()*)
{
  switch (this:kind($edge))
  case "edge" return $edge=>map:put("u", $start)
  case "quad" return $edge=>map:put("u", $start)
  case "cubic" return $edge=>map:put("u", $start)
  case "arc" return this:as-point-arc($edge)=>map:put("start", $start)
  case "ellipse-arc" return $edge=>map:put("start", $start)
  default return errors:error("GEOM-BADREGION", ($edge, "start"))
}

Function: end
declare function end($edge as map(xs:string,item()*)) as map(xs:string,item()*)

end()
Accessor for ending point of edge

Params

• edge as map(xs:string,item()*): The edge

Returns

• map(xs:string,item()*)

declare function this:end($edge as map(xs:string,item()*)) as map(xs:string,item()*)
{
  switch (this:kind($edge))
  case "edge" return $edge("v")
  case "quad" return $edge("v")
  case "cubic" return $edge("v")
  case "arc" return (
    let $end := $edge("end")
    return
      if (exists($end)) then $end
      else (
        let $circle := $edge("circle")
        let $center := ellipse:center($circle)
        let $r := ellipse:radius($circle)
        let $to := util:radians($edge("to-angle"))
        return 
          point:point(
            point:px($center)+math:cos($to)*$r,
            point:py($center)+math:sin($to)*$r
          )
      )
  )
  case "ellipse-arc" return $edge("end")
  default return errors:error("GEOM-BADREGION", ($edge, "end"))
}

Function: weight
declare function weight($edge as map(xs:string,item()*)) as xs:double

weight()
Accessor for the weight of an edge

Params

• edge as map(xs:string,item()*): The edge

Returns

• xs:double

declare function this:weight($edge as map(xs:string,item()*)) as xs:double
{
  if (this:kind($edge) = ("edge","cubic","quad"))
  then ($edge("d"),0)[1]
  else 0
}

Function: arc
declare function arc($center as map(xs:string,item()*),
  $radius as xs:double,
  $start as map(xs:string,item()*),
  $end as map(xs:string,item()*),
  $flipped as xs:boolean,
  $large as xs:boolean) as map(xs:string,item()*)

arc()
Construct an arc (e.g. hyperbolic edge)
Note: calculations on $start and $end need to be correct:
use hyperbolic:arc-through() to get them right; this is really an
internal contructor function. Ad hoc construction of arc should use
arc-by-angle().

Params

• center as map(xs:string,item()*): center of curvature
• radius as xs:double: radius of circle
• start as map(xs:string,item()*): starting point
• end as map(xs:string,item()*): ending point
• flipped as xs:boolean: indicates sweep
• large as xs:boolean: indicated large arc

Returns

• map(xs:string,item()*)

declare function this:arc(
  $center as map(xs:string,item()*),
  $radius as xs:double,
  $start as map(xs:string,item()*),
  $end as map(xs:string,item()*),
  $flipped as xs:boolean,
  $large as xs:boolean
) as map(xs:string,item()*)
{
  map {
    "kind": "arc",
    "circle": ellipse:circle($center, $radius),
    "start": $start,
    "end": $end,
    "flipped": $flipped,
    "large": $large
  }
}

Function: arc
declare function arc($center as map(xs:string,item()*),
  $radius as xs:double,
  $start as map(xs:string,item()*),
  $end as map(xs:string,item()*),
  $flipped as xs:boolean) as map(xs:string,item()*)*

Params

• center as map(xs:string,item()*)
• radius as xs:double
• start as map(xs:string,item()*)
• end as map(xs:string,item()*)
• flipped as xs:boolean

Returns

• map(xs:string,item()*)*

declare function this:arc(
  $center as map(xs:string,item()*),
  $radius as xs:double,
  $start as map(xs:string,item()*),
  $end as map(xs:string,item()*),
  $flipped as xs:boolean
) as map(xs:string,item()*)*
{
  this:arc($center, $radius, $start, $end, $flipped, false())
}

Function: arc
declare function arc($center as map(xs:string,item()*),
  $radius as xs:double,
  $start as map(xs:string,item()*),
  $end as map(xs:string,item()*)) as map(xs:string,item()*)

Params

• center as map(xs:string,item()*)
• radius as xs:double
• start as map(xs:string,item()*)
• end as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:arc(
  $center as map(xs:string,item()*),
  $radius as xs:double,
  $start as map(xs:string,item()*),
  $end as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  this:arc($center, $radius, $start, $end, false(), false())
}

Function: arc-by-angle
declare function arc-by-angle($center as map(xs:string,item()*),
  $radius as xs:double,
  $θ as xs:double,
  $θ2 as xs:double,
  $flipped as xs:boolean,
  $large as xs:boolean) as map(xs:string,item()*)

arc-by-angle()
Construct an arc

Params

• center as map(xs:string,item()*): center of curvature
• radius as xs:double: radius of circle
• θ as xs:double: starting angle (degrees)2: ending angle (degrees)
• θ2 as xs:double: ending angle (degrees)
• flipped as xs:boolean: indicates sweep
• large as xs:boolean: indicates large arc

Returns

• map(xs:string,item()*)

declare function this:arc-by-angle(
  $center as map(xs:string,item()*),
  $radius as xs:double,
  $θ as xs:double,
  $θ2 as xs:double,
  $flipped as xs:boolean,
  $large as xs:boolean
) as map(xs:string,item()*)
{
  map {
    "kind": "arc",
    "circle": ellipse:circle($center, $radius),
    "from-angle": $θ,
    "to-angle": $θ2,
    "flipped": $flipped,
    "large": $large
  }
}

Function: arc-by-angle
declare function arc-by-angle($center as map(xs:string,item()*),
  $radius as xs:double,
  $θ as xs:double,
  $θ2 as xs:double,
  $flipped as xs:boolean) as map(xs:string,item()*)

Params

• center as map(xs:string,item()*)
• radius as xs:double
• θ as xs:double
• θ2 as xs:double
• flipped as xs:boolean

Returns

• map(xs:string,item()*)

declare function this:arc-by-angle(
  $center as map(xs:string,item()*),
  $radius as xs:double,
  $θ as xs:double,
  $θ2 as xs:double,
  $flipped as xs:boolean
) as map(xs:string,item()*)
{
  this:arc-by-angle($center, $radius, $θ, $θ2, $flipped, false())
}

Function: arc-by-angle
declare function arc-by-angle($center as map(xs:string,item()*),
  $radius as xs:double,
  $θ as xs:double,
  $θ2 as xs:double) as map(xs:string,item()*)

Params

• center as map(xs:string,item()*)
• radius as xs:double
• θ as xs:double
• θ2 as xs:double

Returns

• map(xs:string,item()*)

declare function this:arc-by-angle(
  $center as map(xs:string,item()*),
  $radius as xs:double,
  $θ as xs:double,
  $θ2 as xs:double
) as map(xs:string,item()*)
{
  this:arc-by-angle($center, $radius, $θ, $θ2, false(), false())
}

Function: arc-circle
declare function arc-circle($arc as map(xs:string,item()*)) as map(xs:string,item()*)

arc-circle()
Center and radius of curvature for this arc
$arc: The arc

Params

• arc as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:arc-circle($arc as map(xs:string,item()*)) as map(xs:string,item()*)
{
  $arc("circle")
}

Function: arc-center
declare function arc-center($arc as map(xs:string,item()*)) as map(xs:string,item()*)

arc-center()
Center of this arc
$arc: The arc

Params

• arc as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:arc-center($arc as map(xs:string,item()*)) as map(xs:string,item()*)
{
  if (this:kind($arc)="ellipse-arc")
  then $arc("ellipse")=>ellipse:center()
  else $arc("circle")=>ellipse:center()
}

Function: arc-radius
declare function arc-radius($arc as map(xs:string,item()*)) as xs:double

arc-radius()
Radius of curvature of this arc
$arc: The arc

Params

• arc as map(xs:string,item()*)

Returns

• xs:double

declare function this:arc-radius($arc as map(xs:string,item()*)) as xs:double
{
  $arc("circle")=>ellipse:radius()
}

Function: arc-angles
declare function arc-angles($arc as map(xs:string,item()*)) as xs:double*

arc-angles()
Starting and ending angles for the arc (degrees), for arc-by-angle arcs
$arc: The arc

Params

• arc as map(xs:string,item()*)

Returns

• xs:double*

declare function this:arc-angles($arc as map(xs:string,item()*)) as xs:double*
{
  ($arc("from-angle"),$arc("to-angle"))
}

Function: arc-ends
declare function arc-ends($arc as map(xs:string,item()*)) as map(xs:string,item()*)*

arc-ends()
Starting and ending points for the arc, for arc-by-point arcs
$arc: The arc

Params

• arc as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:arc-ends($arc as map(xs:string,item()*)) as map(xs:string,item()*)*
{
  ($arc("start"),$arc("end"))
}

Function: arc-flipped
declare function arc-flipped($arc as map(xs:string,item()*)) as xs:boolean

arc-flipped()
Sweep for the arc
$arc: The arc

Params

• arc as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:arc-flipped($arc as map(xs:string,item()*)) as xs:boolean
{
  (: Default is false :)
  if ($arc("flipped")) then true() else false()
}

Function: arc-large
declare function arc-large($arc as map(xs:string,item()*)) as xs:boolean

Params

• arc as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:arc-large($arc as map(xs:string,item()*)) as xs:boolean
{
  (: Default is false :)
  if ($arc("large")) then true() else false()
}

Function: as-angle-arc
declare function as-angle-arc($arc as map(xs:string,item()*)) as map(xs:string,item()*)

as-angle-arc()
Shift arc edge from the end-point representation to the angle representation.

Params

• arc as map(xs:string,item()*): input arc

Returns

• map(xs:string,item()*)

declare function this:as-angle-arc($arc as map(xs:string,item()*)) as map(xs:string,item()*)
{
  let $points := $arc=>this:arc-ends()
  return (
    if (exists($points)) then (
      let $circle := $arc=>this:arc-circle()
      let $center := ellipse:center($circle)
      let $α := this:angle($center, $points[1])
      let $ω := this:angle($center, $points[2])
      return
        util:merge-into(
          this:property-map($arc),
          this:arc-by-angle(
            $center,
            ellipse:radius($circle),
            $α,
            if ($ω - $α > 360) then 360 - $ω else $ω,
            $arc=>this:arc-flipped(),
            $arc=>this:arc-large()
          )
        )
    ) else (
      $arc
    )
  )
}

Function: as-point-arc
declare function as-point-arc($arc as map(xs:string,item()*)) as map(xs:string,item()*)

as-point-arc()
Shift arc edge from the angle representation to the end-point representation.

Params

• arc as map(xs:string,item()*): input arc

Returns

• map(xs:string,item()*)

declare function this:as-point-arc(
  $arc as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  let $points := $arc=>this:arc-ends()
  return (
    if (exists($points)) then (
      $arc
    ) else (
      let $circle := $arc=>this:arc-circle()
      return (
        util:merge-into(
          this:property-map($arc),
          this:arc(
            ellipse:center($circle),
            ellipse:radius($circle),
            $arc=>this:start(),
            $arc=>this:end(),
            $arc=>this:arc-flipped(),
            $arc=>this:arc-large()
          )
        )
      )
    )
  )
}

Function: ellipse-arc
declare function ellipse-arc($center as map(xs:string,item()*),
  $a as xs:double,
  $b as xs:double,
  $rotation as xs:double,
  $start as map(xs:string,item()*),
  $end as map(xs:string,item()*),
  $flipped as xs:boolean,
  $large as xs:boolean)

Params

• center as map(xs:string,item()*)
• a as xs:double
• b as xs:double
• rotation as xs:double
• start as map(xs:string,item()*)
• end as map(xs:string,item()*)
• flipped as xs:boolean
• large as xs:boolean

declare function this:ellipse-arc(
  $center as map(xs:string,item()*),
  $a as xs:double,
  $b as xs:double,
  $rotation as xs:double,
  $start as map(xs:string,item()*),
  $end as map(xs:string,item()*),
  $flipped as xs:boolean,
  $large as xs:boolean
)
{
  map {
    "kind": "ellipse-arc",
    "ellipse": ellipse:ellipse($center, $a, $b, $rotation),
    "start": $start,
    "end": $end,
    "flipped": $flipped,
    "large": $large
  }
}

Function: arc-ellipse
declare function arc-ellipse($ellipse-arc as map(xs:string,item()*)) as map(xs:string,item()*)

Params

• ellipse-arc as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:arc-ellipse($ellipse-arc as map(xs:string,item()*)) as map(xs:string,item()*)
{
  $ellipse-arc("ellipse")
}

Function: quad
declare function quad($from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control as map(xs:string,item()*),
  $d as xs:double,
  $properties as map(xs:string,item()*)) as map(xs:string,item()*)

quad()
Construct a quadratic edge.

Params

• from as map(xs:string,item()*): starting point
• to as map(xs:string,item()*): ending point
• control as map(xs:string,item()*): control point
• d as xs:double: edge weight
• properties as map(xs:string,item()*): additional properties

Returns

• map(xs:string,item()*)

declare function this:quad(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control as map(xs:string,item()*),
  $d as xs:double,
  $properties as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  util:merge-into($properties,
    map {
      "kind": "quad",
      "u": $from,
      "v": $to,
      "c1": $control,
      "d": $d
    }
  )
}

Function: quad
declare function quad($from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control as map(xs:string,item()*),
  $d as xs:double) as map(xs:string,item()*)

Params

• from as map(xs:string,item()*)
• to as map(xs:string,item()*)
• control as map(xs:string,item()*)
• d as xs:double

Returns

• map(xs:string,item()*)

declare function this:quad(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control as map(xs:string,item()*),
  $d as xs:double
) as map(xs:string,item()*)
{
  map {
    "kind": "quad",
    "u": $from,
    "v": $to,
    "c1": $control,
    "d": $d
  }
}

Function: quad
declare function quad($from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control as map(xs:string,item()*)) as map(xs:string,item()*)

Params

• from as map(xs:string,item()*)
• to as map(xs:string,item()*)
• control as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:quad(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  this:quad($from, $to, $control, 0)
}

Function: controls
declare function controls($edge as map(xs:string,item()*)) as map(xs:string,item()*)*

controls()
Get control points from a quadratic or cubic edge.

Params

• edge as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:controls(
  $edge as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  switch(this:kind($edge))
  case "quad" return $edge("c1")
  case "cubic" return ($edge("c1"),$edge("c2"))
  default return errors:error("GEOM-BADREGION", ($edge, "controls"))
}

Function: cubic
declare function cubic($from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control1 as map(xs:string,item()*),
  $control2 as map(xs:string,item()*),
  $d as xs:double,
  $properties as map(xs:string,item()*)) as map(xs:string,item()*)

cubic()
Construct a cubic edge.

Params

• from as map(xs:string,item()*): starting point
• to as map(xs:string,item()*): ending point
• control1 as map(xs:string,item()*): first control point
• control2 as map(xs:string,item()*): second control point
• d as xs:double: edge weight
• properties as map(xs:string,item()*): additional properties

Returns

• map(xs:string,item()*)

declare function this:cubic(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control1 as map(xs:string,item()*),
  $control2 as map(xs:string,item()*),
  $d as xs:double,
  $properties as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  util:merge-into($properties,
    map {
      "kind": "cubic",
      "u": $from,
      "v": $to,
      "c1": $control1,
      "c2": $control2,
      "d": $d
    }
  )
}

Function: cubic
declare function cubic($from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control1 as map(xs:string,item()*),
  $control2 as map(xs:string,item()*),
  $d as xs:double) as map(xs:string,item()*)

Params

• from as map(xs:string,item()*)
• to as map(xs:string,item()*)
• control1 as map(xs:string,item()*)
• control2 as map(xs:string,item()*)
• d as xs:double

Returns

• map(xs:string,item()*)

declare function this:cubic(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control1 as map(xs:string,item()*),
  $control2 as map(xs:string,item()*),
  $d as xs:double
) as map(xs:string,item()*)
{
  map {
    "kind": "cubic",
    "u": $from,
    "v": $to,
    "c1": $control1,
    "c2": $control2,
    "d": $d
  }
}

Function: cubic
declare function cubic($from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control1 as map(xs:string,item()*),
  $control2 as map(xs:string,item()*)) as map(xs:string,item()*)

Params

• from as map(xs:string,item()*)
• to as map(xs:string,item()*)
• control1 as map(xs:string,item()*)
• control2 as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:cubic(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*),
  $control1 as map(xs:string,item()*),
  $control2 as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  this:cubic($from, $to, $control1, $control2, 0)
}

Function: points
declare function points($region as map(xs:string,item()*)) as map(xs:string,item()*)*

points()
Get 2D points from the region

Params

• region as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:points($region as map(xs:string,item()*)) as map(xs:string,item()*)*
{
  this:vertices($region)!point:as-dimension(.,2)
}

Function: vertices
declare function vertices($region as map(xs:string,item()*)) as map(xs:string,item()*)*

vertices()
Get all the region's points.

Params

• region as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:vertices($region as map(xs:string,item()*)) as map(xs:string,item()*)*
{
  switch(this:kind($region))
  case "edge" return ($region=>this:start(), $region=>this:end())
  case "arc" return ($region=>this:start(), $region=>this:end())
  case "quad" return ($region=>this:start(), $region=>this:end())
  case "cubic" return ($region=>this:start(), $region=>this:end())
  default return errors:error("GEOM-BADREGION", ($region, "vertices"))
}

Function: to-edges
declare function to-edges($points as map(xs:string,item()*)*) as map(xs:string,item()*)*

to-edges()
Convert a sequence of points into a sequence of edges.

Params

• points as map(xs:string,item()*)*: the sequence of points

Returns

• map(xs:string,item()*)*

declare function this:to-edges($points as map(xs:string,item()*)*) as map(xs:string,item()*)*
{
  for $pt at $i in tail($points)
  return this:edge($points[$i], $pt)
}

Function: to-edges
declare function to-edges($points as item()*, $properties as map(xs:string,item()*)) as map(xs:string,item()*)*

to-edges()
Convert a sequence of points into a sequence of edges.

Params

• points as item()*: the sequence of points
• properties as map(xs:string,item()*): edge properties

Returns

• map(xs:string,item()*)*

declare function this:to-edges($points as item()*, $properties as map(xs:string,item()*)) as map(xs:string,item()*)*
{
  let $d := ($properties("d"),0)[1] (: Special case for d :)
  for $pt at $i in tail($points)
  return this:edge($points[$i], $pt, $d, $properties)
}

Function: skip
declare function skip($from as map(xs:string,item()*),
  $to as map(xs:string,item()*)) as map(xs:string,item()*)

skip()
Make a skip edge (pure goto)

Params

• from as map(xs:string,item()*): starting point
• to as map(xs:string,item()*): ending point

Returns

• map(xs:string,item()*)

declare function this:skip(
  $from as map(xs:string,item()*),
  $to as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  this:edge($from, $to)=>map:put("variety", "goto")
}

Function: property-map
declare function property-map($region as map(xs:string,item()*)) as map(xs:string,item()*)

property-map()
Return the annotation properties of the edge as a map. Check whether this
is actually an edge.

Params

• region as map(xs:string,item()*): the region

Returns

• map(xs:string,item()*)

declare function this:property-map(
  $region as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  switch(this:kind($region))
  case "edge" return util:exclude($region,$this:EDGE-RESERVED)
  case "arc" return util:exclude($region,$this:ARC-RESERVED)
  case "quad" return util:exclude($region, $this:QUAD-RESERVED)
  case "cubic" return util:exclude($region, $this:CUBIC-RESERVED)
  case "ellipse-arc" return util:exclude($region, $this:ELLIPSE-ARC-RESERVED)
  default return map {}
}

Function: properties
declare function properties($region as map(xs:string,item()*)) as xs:string*

properties()
Return the names of the annotation properties of the edge.
Check whether this is actually an edge

Params

• region as map(xs:string,item()*): the region

Returns

• xs:string*

declare function this:properties(
  $region as map(xs:string,item()*)
) as xs:string*
{
  switch(this:kind($region))
  case "edge" return ($region=>map:keys())[not(. = $this:EDGE-RESERVED)]
  case "arc" return ($region=>map:keys())[not(. = $this:ARC-RESERVED)]
  case "quad" return ($region=>map:keys())[not(. = $this:QUAD-RESERVED)]
  case "cubic" return ($region=>map:keys())[not(. = $this:CUBIC-RESERVED)]
  case "ellipse-arc" return ($region=>map:keys())[not(. = $this:ELLIPSE-ARC-RESERVED)]
  default return ()
}

Function: with-properties
declare function with-properties($region as map(xs:string,item()*),
  $properties as map(xs:string,item()*)) as map(xs:string,item()*)

with-properties()
Annotate the edge with some new properties and return the new edge.
Will not touch any of the core properties. Will override existing properties
with the same keys but leave properties with different keys in place.
Raises an error if this is not actually an edge.

Params

• region as map(xs:string,item()*): the region
• properties as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:with-properties(
  $region as map(xs:string,item()*),
  $properties as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  switch(this:kind($region))
  case "edge" return util:merge-into($region, util:exclude($properties,$this:EDGE-RESERVED))
  case "arc" return util:merge-into($region, util:exclude($properties,$this:ARC-RESERVED))
  case "quad" return util:merge-into($region, util:exclude($properties, $this:QUAD-RESERVED))
  case "cubic" return util:merge-into($region, util:exclude($properties, $this:CUBIC-RESERVED))
  case "ellipse-arc" return util:merge-into($region, util:exclude($properties,$this:ELLIPSE-ARC-RESERVED))
  default return errors:error("GEOM-BADREGION", ($region, "with-properties"))
}

Function: snap
declare function snap($edges as map(xs:string,item()*)*) as map(xs:string,item()*)*

snap()
Snap the coordinates of the points, returning the edges with snapped
(i.e. integer) points coordinates.

Params

• edges as map(xs:string,item()*)* the edges

Returns

• map(xs:string,item()*)*

declare function this:snap(
  $edges as map(xs:string,item()*)*
) as map(xs:string,item()*)*
{
  for $edge in $edges return switch(this:kind($edge))
  case "edge" return
    this:edge(
      point:snap(this:start($edge)),
      point:snap(this:end($edge)),
      this:weight($edge),
      $edge
    )
  case "quad" return
    this:quad(
      point:snap(this:start($edge)),
      point:snap(this:end($edge)),
      point:snap(this:controls($edge)[1]),
      this:weight($edge),
      $edge
    )
  case "cubic" return
    let $controls := this:controls($edge)
    return
      this:cubic(
        point:snap(this:start($edge)),
        point:snap(this:end($edge)),
        point:snap($controls[1]),
        point:snap($controls[2]),
        this:weight($edge),
        $edge
      )
  case "arc" return
    let $circle := $edge=>this:arc-circle()
    let $points := $edge=>this:arc-ends()
    let $angles := $edge=>this:arc-angles()
    return
      if (empty($points)) then (
        util:assert(exists($angles),"Arc must have points or angles"),
        $edge=>
          map:put("circle", ellipse:snap($circle))
      ) else (
        $edge=>
           map:put("circle", ellipse:snap($circle))=>
           map:put("start", point:snap($points[1]))=>
           map:put("end", point:snap($points[2]))
      )
  case "ellipse-arc" return
    let $ellipse := $edge=>this:arc-ellipse()
    let $points := $edge=>this:arc-ends()
    return
      $edge=>
         map:put("ellipse", ellipse:snap($ellipse))=>
         map:put("start", point:snap($points[1]))=>
         map:put("end", point:snap($points[2]))
  default return $edge
}

Function: decimal
declare function decimal($edges as map(xs:string,item()*)*,
  $digits as xs:integer) as map(xs:string,item()*)*

decimal()
Perform decimal rounding on all the point coordinates (see util:decimal).

Params

• edges as map(xs:string,item()*)*: the edges to round
• digits as xs:integer: how many digits after the decimal point to keep

Returns

• map(xs:string,item()*)*

declare function this:decimal(
  $edges as map(xs:string,item()*)*,
  $digits as xs:integer
) as map(xs:string,item()*)*
{
  for $edge in $edges return switch(this:kind($edge))
  case "edge" return
    this:edge(
      point:decimal(this:start($edge), $digits),
      point:decimal(this:end($edge), $digits),
      this:weight($edge),
      $edge
    )
  case "quad" return
    this:quad(
      point:decimal(this:start($edge), $digits),
      point:decimal(this:end($edge), $digits),
      point:decimal(this:controls($edge)[1], $digits),
      this:weight($edge),
      $edge
    )
  case "cubic" return
    let $controls := this:controls($edge)
    return
      this:cubic(
        point:decimal(this:start($edge), $digits),
        point:decimal(this:end($edge), $digits),
        point:decimal($controls[1], $digits),
        point:decimal($controls[2], $digits),
        this:weight($edge),
        $edge
      )
  case "arc" return
    let $circle := $edge=>this:arc-circle()
    let $points := $edge=>this:arc-ends()
    let $angles := $edge=>this:arc-angles()
    return
      if (empty($points)) then (
        util:assert(exists($angles),"Arc must have points or angles"),
        $edge=>
          map:put("circle", ellipse:decimal($circle, $digits))
      ) else (
        $edge=>
           map:put("circle", ellipse:decimal($circle, $digits))=>
           map:put("start", point:decimal($points[1], $digits))=>
           map:put("end", point:decimal($points[2], $digits))
      )
  case "ellipse-arc" return
    let $ellipse := $edge=>this:arc-ellipse()
    let $points := $edge=>this:arc-ends()
    return
      $edge=>
         map:put("ellipse", ellipse:decimal($ellipse, $digits))=>
         map:put("start", point:decimal($points[1], $digits))=>
         map:put("end", point:decimal($points[2], $digits))
  default return $edge
}

Function: quote
declare function quote($edges as map(xs:string,item()*)*) as xs:string

quote()
Return a string value for the edges, suitable for debugging.

Params

• edges as map(xs:string,item()*)*: the edge sequence to quote

Returns

• xs:string

declare function this:quote(
  $edges as map(xs:string,item()*)*
) as xs:string
{
  string-join(
    for $edge in $edges return switch(this:kind($edge))
    case "edge" return
      point:quote($edge("u"))||":"||point:quote($edge("v"))
    case "quad" return
      point:quote($edge("u"))||":"||point:quote($edge("v"))||"<"||point:quote($edge("c1"))||">"
    case "cubic" return
      point:quote($edge("u"))||":"||point:quote($edge("v"))||"<"||point:quote($edge("c1"))||";"||point:quote($edge("c2"))||">"
    case "arc" return
      "("||
        ellipse:quote($edge("circle"))||
        "<"||
          point:quote($edge("start"))||
          $edge("from-angle")||":"||
          point:quote($edge("end"))||
          $edge("to-angle")||
        ">"||
        (if ($edge("large")) then "+l1" else "+l0")||
        (if ($edge("flipped")) then "+f1" else "+f0")||
      ")"
    case "ellipse-arc" return
      "("||
        ellipse:quote($edge("ellipse"))||
        "<"||
          point:quote($edge("start"))||
          point:quote($edge("end"))||
        ">"||
        (if ($edge("large")) then "+l1" else "+l0")||
        (if ($edge("flipped")) then "+f1" else "+f0")||
      ")"
    default return errors:quote($edge)
    ,
    " "
  )
}

Function: same
declare function same($this as map(xs:string,item()*),
  $other as map(xs:string,item()*)) as xs:boolean

same()
Equality comparison for edges, ignoring annotation properties.
Return true() if they have equal coordinates.

Params

• this as map(xs:string,item()*): one edge
• other as map(xs:string,item()*): the edge to compare it to

Returns

• xs:boolean

declare function this:same(
  $this as map(xs:string,item()*),
  $other as map(xs:string,item()*)
) as xs:boolean
{
  let $this-kind := this:kind($this)
  let $other-kind := this:kind($other)
  return
  (
    ($this-kind=$other-kind) and (
    switch($this-kind)
    case "arc" return
      (this:arc-large($this) = this:arc-large($other)) and
      (this:arc-flipped($this) = this:arc-flipped($other)) and
      ellipse:same($this("circle"),$other("circle")) and
      (
        if (empty($this("start"))) then empty($other("start"))
        else if (empty($other("start"))) then false()
        else point:same($this("start"), $other("start"))
      ) and
      (
        if (empty($this("end"))) then empty($other("end"))
        else if (empty($other("end"))) then false()
        else point:same($this("end"), $other("end"))
      ) and (
        if (empty($this("from-angle"))) then empty($other("from-angle"))
        else if (empty($other("from-angle"))) then false()
        else $this("from-angle")=$other("from-angle")
      ) and (
        if (empty($this("to-angle"))) then empty($other("to-angle"))
        else if (empty($other("to-angle"))) then false()
        else $this("to-angle")=$other("to-angle")
      )
    case "edge" return
      point:same($this("u"),$other("u")) and
      point:same($this("v"),$other("v"))
    case "quad" return
      point:same($this("u"),$other("u")) and
      point:same($this("v"),$other("v")) and
      point:same($this("c1"),$other("c1"))
    case "cubic" return
      point:same($this("u"),$other("u")) and
      point:same($this("v"),$other("v")) and
      point:same($this("c1"),$other("c1")) and
      point:same($this("c2"),$other("c2"))
    case "ellipse-arc" return
      (this:arc-large($this) = this:arc-large($other)) and
      (this:arc-flipped($this) = this:arc-flipped($other)) and
      ellipse:same($this("ellipse"),$other("ellipse")) and
      point:same($this("start"), $other("start")) and 
      point:same($this("end"), $other("end"))
    default return deep-equal($this,$other)
    )
  )
}

Function: mutate
declare function mutate($regions as map(xs:string,item()*)*,
  $mutate as function(map(xs:string,item()*)) as map(xs:string,item()*)) as map(xs:string,item()*)*

mutate()
Run a function over a sequence of edges to produce a new sequence of
edges. The function maps points to points.

Params

• regions as map(xs:string,item()*)*: input sequence of edges
• mutate as function(map(xs:string,item()*))asmap(xs:string,item()*): function that takes a point as an argument and returns a new point

Returns

• map(xs:string,item()*)*

declare function this:mutate(
  $regions as map(xs:string,item()*)*,
  $mutate as function(map(xs:string,item()*)) as map(xs:string,item()*) (: point to point :)
) as map(xs:string,item()*)*
{
  for $edge in $regions 
  return (
    switch (this:kind($edge))
    case "edge" return (
      this:edge(
        $mutate($edge=>this:start()),
        $mutate($edge=>this:end()),
        $edge=>this:weight(),
        $edge
      )
    )
    case "cubic" return (
      let $controls := ($edge=>this:controls())!$mutate(.)
      return
        this:cubic(
          $mutate($edge=>this:start()),
          $mutate($edge=>this:end()),
          $controls[1],
          $controls[2],
          $edge=>this:weight(),
          $edge
        )
    )
    case "quad" return (
      let $control := $mutate(this:controls($edge)[1])
      return
        this:quad(
          $mutate($edge=>this:start()),
          $mutate($edge=>this:end()),
          $control,
          $edge=>this:weight(),
          $edge
        )
    )
    case "arc" return (
      let $points := $edge=>this:arc-ends()
      let $angles := $edge=>this:arc-angles()
      return (
        if (exists($points)) then (
          this:arc(
            $mutate($edge=>this:arc-center()),
            $edge=>this:arc-radius(),
            $mutate($edge=>this:start()),
            $mutate($edge=>this:end()),
            $edge=>this:arc-flipped(),
            $edge=>this:arc-large()
          )
        ) else (
          this:arc-by-angle(
            $mutate($edge=>this:arc-center()),
            $edge=>this:arc-radius(),
            $angles[1],
            $angles[2],
            $edge=>this:arc-flipped(),
            $edge=>this:arc-large()
          )
        )
      )=>this:with-properties($edge)
    )
    default return $edge
  )
}

Function: reverse
declare function reverse($edge as map(xs:string,item()*)) as map(xs:string,item()*)

reverse()
Reverse the direction of the edge.

Params

• edge as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:reverse($edge as map(xs:string,item()*)) as map(xs:string,item()*)
{
  switch(this:kind($edge))
  case "edge" return
    this:edge(
      this:end($edge),
      this:start($edge),
      this:weight($edge),
      $edge
    )
  case "quad" return
    this:quad(
      this:end($edge),
      this:start($edge),
      this:controls($edge)[1],
      this:weight($edge),
      $edge
    )
  case "cubic" return
    this:cubic(
      this:end($edge),
      this:start($edge),
      this:controls($edge)[2],
      this:controls($edge)[1],
      this:weight($edge),
      $edge
    )
  case "arc" return (
    let $circle := $edge=>this:arc-circle()
    let $points := $edge=>this:arc-ends()
    let $angles := $edge=>this:arc-angles()
    return (
      if (exists($points)) then (
        this:arc(
          $circle=>ellipse:center(),
          $circle=>ellipse:radius(),
          $points[2],
          $points[1],
          not($edge=>this:arc-flipped()),
          $edge=>this:arc-large()
        )
      ) else (
        this:arc-by-angle(
          $circle=>ellipse:center(),
          $circle=>ellipse:radius(),
          $angles[2],
          $angles[1],
          not($edge=>this:arc-flipped()),
          $edge=>this:arc-large()
        )
      )
    )
  )
  default return $edge
}

Function: angle
declare function angle($edge as map(xs:string,item()*)) as xs:double

angle()
Bearing of the edge between start and end points.

Params

• edge as map(xs:string,item()*): the edge

Returns

• xs:double

declare function this:angle($edge as map(xs:string,item()*)) as xs:double
{
  this:angle(this:start($edge), this:end($edge))
}

Function: angle
declare function angle($last as map(xs:string,item()*)?, $curr as map(xs:string,item()*)) as xs:double

angle()
Compute the angle (azimuth) from one point to the next, in degrees
Return 0 if points are the same

Params

• last as map(xs:string,item()*)?: previous point; use (0,0) if no previous
• curr as map(xs:string,item()*): current point

Returns

• xs:double

declare function this:angle($last as map(xs:string,item()*)?, $curr as map(xs:string,item()*)) as xs:double
{
  let $this := $curr=>point:as-dimension(2)
  let $prev := point:as-dimension(($last,$point:ORIGIN)[1],2)
  return
    if (point:same($prev,$this) or (point:distance($prev,$this) < $config:ε)) then 0
    else if (point:px($this)=point:px($prev)) then (
      if (point:py($prev) > point:py($this))
      then 270 (: remapped -90 :)
      else 90
    ) else (
      util:remap-degrees(util:degrees(
        (math:pi() div 2) - math:atan2(point:px($this) - point:px($prev), point:py($this) - point:py($prev))
      ))
    )
}

Function: inclination
declare function inclination($edge as map(xs:string,item()*)) as xs:double

inclination()
Inclination of the edge between start and end points.

Params

• edge as map(xs:string,item()*): the edge

Returns

• xs:double

declare function this:inclination($edge as map(xs:string,item()*)) as xs:double
{
  this:inclination(this:start($edge), this:end($edge))
}

Function: inclination
declare function inclination($last as map(xs:string,item()*)?, $curr as map(xs:string,item()*)) as xs:double

inclination()
Compute the inclination angle from one point in the next, in degrees
Return 90 if the points are the same

Params

• last as map(xs:string,item()*)?: previous point; use (0,0,0) if no previous
• curr as map(xs:string,item()*): current point

Returns

• xs:double

declare function this:inclination($last as map(xs:string,item()*)?, $curr as map(xs:string,item()*)) as xs:double
{
  let $curr := $curr=>point:as-dimension(3)
  let $prev := (($last,$point:ORIGIN3D)[1])=>point:as-dimension(3)
  let $d := point:distance($prev,$curr)
  return
    if (point:same($prev,$curr) or ($d < $config:ε)) then 90
    else (
      util:remap-degrees(util:degrees(
        math:acos( (point:pz($curr) - point:pz($prev)) div $d )
      ))
    )
}

Function: linear-point
declare function linear-point($edge as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)

linear-point()
Compute the point on the edge the given fraction from the start

Params

• edge as map(xs:string,item()*): the edge
• t as xs:double: fraction of distance from start to end (t) [0,1]

Returns

• map(xs:string,item()*)

declare function this:linear-point($edge as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)
{
  let $from := $edge=>this:start()
  let $to := $edge=>this:end()
  return (
    point:map2(function ($a as xs:double, $b as xs:double) as xs:double {$a + ($b - $a)*$t}, $from, $to)
  )
}

Function: quad-point
declare function quad-point($quadratic as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)

quad-point()
Compute the point on the quad edge the given fraction from the start
Midpoint of quad edge is quad-point(0.5)
B(t)=(1-t)²P0 + 2(1-t)tP1 + t²P2, 0 <= t <= 1

Params

• quadratic as map(xs:string,item()*): the edge
• t as xs:double: fraction of distance from start to end (t) [0,1]

Returns

• map(xs:string,item()*)

declare function this:quad-point($quadratic as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)
{
  let $from := $quadratic=>this:start()
  let $to := $quadratic=>this:end()
  let $controls := $quadratic=>this:controls()
  return (
    point:map3(
      function ($a as xs:double, $b as xs:double, $c as xs:double) as xs:double {
        (1 - $t)*(1 - $t)*$a +
        2*(1 - $t)*$t*$c + 
        $t * $t * $b
      },
      $from, $to, $controls[1]
    )
  )
}

Function: cubic-point
declare function cubic-point($cubic as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)

cubic-point()
Compute the point on the cubic edge the given fraction from the start
Midpoint of cubic edge is cubic-point(0.5)
B(t)=(1-t)³P0 + 3(1-t)²tP1 + 3(1-t)t²P2 + t³P3, 0 <= t <= 1

Params

• cubic as map(xs:string,item()*): the edge
• t as xs:double: fraction of distance from start to end (t) [0,1]

Returns

• map(xs:string,item()*)

declare function this:cubic-point($cubic as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)
{
  let $from := $cubic=>this:start()
  let $to := $cubic=>this:end()
  let $controls := $cubic=>this:controls()
  return (
    point:map4(
      function ($a as xs:double, $b as xs:double, $c as xs:double, $d as xs:double) as xs:double {
        (1 - $t)*(1 - $t)*(1 - $t)*$a +
        3*(1 - $t)*(1 - $t)*$t*$c +
        3*(1 - $t)*$t*$t*$d +
        $t*$t*$t*$b
      },
      $from, $to, $controls[1], $controls[2]
    )
  )
}

Function: arc-point
declare function arc-point($arc as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)

arc-point()
Compute the point on the arc edge the given fraction from the start
Midpoint of arc edge is arc-point(0.5)
Will normalize arc properly.

Params

• arc as map(xs:string,item()*): the edge
• t as xs:double: fraction of distance from start to end (t) [0,1]

Returns

• map(xs:string,item()*)

declare function this:arc-point($arc as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)
{
  let $arc := this:normalize-arc($arc)
  let $center := $arc=>this:arc-center()
  let $radius := $arc=>this:arc-radius()
  let $angles := $arc=>this:arc-angles()
  let $from-angle := $angles[1]
  let $to-angle := $angles[2]
  let $da := $to-angle - $from-angle
  return point:destination($center, $from-angle + $t*$da, $radius)
}

Function: length
declare function length($edge as map(xs:string,item()*)) as xs:double

length()
Travel distance along edge.
Cubic is an approximation.

Params

• edge as map(xs:string,item()*)

Returns

• xs:double

declare function this:length($edge as map(xs:string,item()*)) as xs:double
{
  switch (this:kind($edge))
  case "arc" return this:arc-length($edge)
  case "quad" return this:quad-length($edge)
  case "cubic" return this:cubic-length($edge) (: approximation by 10 slices :)
  case "edge" return this:linear-length($edge)
  default return errors:error("GEOM-BADREGION", ($edge, "length"))
}

Function: linear-length
declare function linear-length($edge as map(xs:string,item()*)) as xs:double

linear-length()
Crow-flies distance between end points of an edge. Same a travel distance
along the edge if it is a linear edge.

Params

• edge as map(xs:string,item()*): the edge

Returns

• xs:double

declare function this:linear-length($edge as map(xs:string,item()*)) as xs:double
{
  point:distance($edge=>this:start(), $edge=>this:end())
}

Function: quad-length
declare function quad-length($quad as map(xs:string,item()*)) as xs:double

quad-length()
Length of travel along a quadratic edge.

Params

• quad as map(xs:string,item()*): the quadratic edge Derivation, see: https://members.loria.fr/SHornus/quadratic-arc-length.html B(t) = (1-t)²P0 + 2(1-t)tP1 + t²P2 Reformulate to: P(t) = At² + 2Bt + C where A = P0 - P1 + P2 - P1 B = P1 - P0 C = P0 let F = P2 - P1, so A = F - B length = (|F|(A · F) - |B|(A · B)) / |A|² + (|B|²/|A| - (A · B)²/|A|³) X (log(|A||F| + A · F) - log(|A||B| + A · B))

Returns

• xs:double

declare function this:quad-length($quad as map(xs:string,item()*)) as xs:double
{
  let $P0 := this:start($quad)
  let $P1 := this:controls($quad)[1]
  let $P2 := this:end($quad)
  let $F := point:sub($P2, $P1)
  let $B := point:sub($P1, $P0)
  let $A := point:sub($F, $B)
  let $nA := point:magnitude($A)
  let $nB := point:magnitude($B)
  let $nF := point:magnitude($F)
  let $A.B := point:dot($A, $B)
  let $A.F := point:dot($A, $F)
  return (
    (: Possible error cases
     : nA=0 => F=B => start, c0, end are colinear => a straight edge
     :
     : nA*nF + A.F = 0 => nA*nF = -A.F => log(nA*nF + A.F) = -INF
     : nA*nF= √(Σai*ai)√(Σfi*fi) A.F=Σ(ai*fi)
     : A = F - B => nA*nF = √(Σ(fi-bi)*(fi-bi))√(Σfi*fi) A.F=Σ((fi-bi)*fi) => det(B,F) = 0 =>
     :   B and F are colinear => a straight edge again
     :
     : nA*nB + A.B = 0 => log(nA*nA + A.B) = -INF => nA*nB = -A.B => nA*nA*nB*nB = A.B*A.B => 
     :    (nB*nB / nA) - (A.B*A.B)/(nA*nA*nA) = 0 => treat 0*-INF as 0
     :)
    if ($nA*$nA = 0) then (
      point:distance($P0, $P2)
    ) else if ($nA*$nB + $A.B = 0) then (
      ($nF * $A.F - $nB * $A.B) div ($nA*$nA)
    ) else if ($nA * $nF + $A.F <= 0) then (
      point:distance($P0, $P2)
    ) else if ($nA * $nB + $A.B <= 0) then (
      point:distance($P0, $P2)
    ) else (
      (
        ($nF * $A.F - $nB * $A.B) div ($nA*$nA)
      ) +
      (
        (($nB*$nB div $nA) - ($A.B*$A.B) div ($nA*$nA*$nA)) *
        (math:log($nA*$nF + $A.F) - math:log($nA*$nB + $A.B))
      )
    )
  )
}

Function: cubic-length
declare function cubic-length($cubic as map(xs:string,item()*),
  $n as xs:integer) as xs:double

cubic-length()
Travel length along a cubic edge. There is no general closed form,
so this is approximated by interpolating the edge with line segments.

Params

• cubic as map(xs:string,item()*): the cubic edge
• n as xs:integer: number of interpolations to use

Returns

• xs:double

declare function this:cubic-length(
  $cubic as map(xs:string,item()*),
  $n as xs:integer
) as xs:double
{
  let $ts := util:linspace($n, 0, 1)
  let $pts := for $t in $ts return this:cubic-point($cubic, $t)
  return
    sum(
      for $pt at $i in tail($pts) return point:distance($pts[$i], $pt)
    )
}

Function: cubic-length
declare function cubic-length($cubic as map(xs:string,item()*)) as xs:double

cubic-length()
Travel length along a cubic edge. There is no general closed form,
so this is approximated by interpolating the edge with 10 line segments.

Params

• cubic as map(xs:string,item()*): the cubic edge

Returns

• xs:double

declare function this:cubic-length($cubic as map(xs:string,item()*)) as xs:double
{
  this:cubic-length($cubic, 10)
}

Function: arc-length
declare function arc-length($arc as map(xs:string,item()*)) as xs:double

arc-length()
Travel distance along arc

Params

• arc as map(xs:string,item()*)

Returns

• xs:double

declare function this:arc-length($arc as map(xs:string,item()*)) as xs:double
{
  let $r := $arc=>this:arc-radius()
  let $α := this:arc-extent($arc)
  return 2 * math:pi() * $r * $α div 360
}

Function: arc-extent
declare function arc-extent($arc as map(xs:string,item()*)) as xs:double

arc-extent()
Degrees swept out by an arc edge.

Params

• arc as map(xs:string,item()*): the arc edge

Returns

• xs:double

declare function this:arc-extent($arc as map(xs:string,item()*)) as xs:double
{
  let $center := $arc=>this:arc-center()
  let $points := $arc=>this:arc-ends()
  let $angles := $arc=>this:arc-angles()
  return (
    if (exists($points)) then (
      util:remap-degrees(abs(this:angle($center, $points[2]) - this:angle($center, $points[1])))
    ) else (
      util:remap-degrees(abs($angles[2] - $angles[1]))
    )
  )
}

Function: slice
declare function slice($edge as map(xs:string,item()*),
  $t as xs:double) as map(xs:string,item()*)*

slice()
Create two edges at the given fraction of the source edge. Cubic edges
will be sliced into two cubic edges, quadratric edges will be slices into
two quadratic edges, etc.

If t is at end, get same edge back.

Params

• edge as map(xs:string,item()*): the edge to cut
• t as xs:double: fraction of edge [0,1]

Returns

• map(xs:string,item()*)*

declare function this:slice(
  $edge as map(xs:string,item()*),
  $t as xs:double
) as map(xs:string,item()*)*
{
  switch (this:kind($edge))
  case "edge" return this:slice-linear($edge, $t)
  case "arc" return this:slice-arc($edge, $t)
  case "quad" return this:slice-quad($edge, $t)
  case "cubic" return this:slice-cubic($edge, $t)
  default return errors:error("GEOM-BADREGION", ($edge, "slice"))
}

Function: slice
declare function slice($edge as map(xs:string,item()*),
  $start-t as xs:double,
  $end-t as xs:double) as map(xs:string,item()*)*

slice()
Slice the edge between two cut points. Will end up with three edges in
general: [start, p(start-t)], [p(start-t), p(end-t)], [p(end-t), end]
start-t <= end-t

If start-t=end-t this is same as slice(edge, start-t)
If start-t or end-t is at an end will get one less edge

Cubics are cut into cubics, quads into quads, straight edges into straight
edges

Params

• edge as map(xs:string,item()*): the edge to cut
• start-t as xs:double: fraction of edge [0,1]
• end-t as xs:double: fraction of edge[0,1]

Returns

• map(xs:string,item()*)*

declare function this:slice(
  $edge as map(xs:string,item()*),
  $start-t as xs:double,
  $end-t as xs:double
) as map(xs:string,item()*)*
{
  if ($start-t > $end-t) then errors:error("GEOM-BADT", ($start-t, $end-t)) else (),
  if ($start-t = $end-t) then this:slice($edge, $start-t)
  else if ($start-t = 1) then $edge (: start-t=end-t=1 :)
  else if ($start-t = 0) then this:slice($edge, $end-t)
  else (
    (: 
     : end-t needs to be adjusted for the second slice:
     : Effective end-t should be fraction of length(slice) not of length(edge)
     : e * l - l1 = x * l2; l1 = s * l, l2 = l - l1 = l - s * l
     : x = (el - sl) / (s - sl) = (e - s) / (1 - s)
     :)
    let $slice := this:slice($edge, $start-t)
    let $eff-end-t := ($end-t - $start-t) div (1 - $start-t)
    return ($slice[1], this:slice($slice[2], $eff-end-t))
  )
}

Function: chop
declare function chop($edge as map(xs:string,item()*),
  $ts as xs:double*) as map(xs:string,item()*)*

chop()
Slice the edge by chopping it at the given cut points.

Cubics are cut into cubics, quads into quads, straight edges into straight
edges

Params

• edge as map(xs:string,item()*): the edge to cut
• ts as xs:double*: fraction of edge [0,1]

Returns

• map(xs:string,item()*)*

declare function this:chop(
  $edge as map(xs:string,item()*),
  $ts as xs:double*
) as map(xs:string,item()*)*
{
  let $ts := distinct-values(for $t in $ts order by $t ascending return $t)
  
  let $eff-ts :=
    (: Adjust ts:
     : Need to adjust t2
     : Effective t2 should be fraction of length(slice)
     : e * l - l1 = x * l2; l1 = s * l, l2 = l - l1 = l - s * l
     : x = (el - sl) / (s - sl) = (e - s) / (1 - s)
     : However, the t1 is itself an adjustment
     : So t4 needs to be adjusted to t3 which is adjusted to t2
     : which is adjusted to t1 and so on. But we need to adjust 
     : them all for each go round:
     : [  t1  t2  t3 ]
     : [  t1][  t2'  t3']
     : [  t1][  t2'][  t3'']
     :)
    fold-left(2 to count($ts) - 1, $ts,
      function ($new-ts as xs:double*, $it as xs:integer) as xs:double* {
        $new-ts[position() < $it - 1],
        fold-left($new-ts[position() >= $it], $new-ts[position() = $it - 1],
          function ($new-ts as xs:double*, $t2 as xs:double) as xs:double* {
            $new-ts,
            let $t1 := $new-ts[last()]
            return ($t2 - $t1) div (1 - $t1)
          }
        )
      }
    )
  let $split1 := this:slice($edge, head($eff-ts))
  let $splits := (
    fold-left(tail($eff-ts), array{$split1},
      function ($splits as array(*)*, $t as xs:double) as array(*)* {
        $splits,
        array {
          if (empty($splits[last()]) or array:size($splits[last()]) < 2) then ()
          else this:slice($splits[last()](2), $t)
        }
      }
    )
  )
  return (
    for $split in $splits return $split?*
  )
}

Function: slice-linear
declare function slice-linear($edge as map(xs:string,item()*),
  $t as xs:double) as map(xs:string,item()*)*

slice-linear()
Create two straight edges at the given fraction of the source edge.

If t is at end, get same edge back.

Params

• edge as map(xs:string,item()*)
• t as xs:doublehis: the straight edge to cut: fraction of edge [0,1]

Returns

• map(xs:string,item()*)*

declare function this:slice-linear(
  $edge as map(xs:string,item()*),
  $t as xs:double
) as map(xs:string,item()*)*
{
  if ($t = (0,1)) then $edge else
  let $p1 := this:start($edge)
  let $p2 := this:end($edge)
  let $pt := this:linear-point($edge, $t)
  return (
    this:edge($p1, $pt),
    this:edge($pt, $p2)
  )
}

Function: slice-quad
declare function slice-quad($quad as map(xs:string,item()*),
  $t as xs:double) as map(xs:string,item()*)*

slice-quad()
Create two quadratic edges at the given fraction of the source quadratic.

If t is at end, get same edge back.

Params

• quad as map(xs:string,item()*): the quad edge to cut
• t as xs:double: fraction of edge [0,1]

Returns

• map(xs:string,item()*)*

declare function this:slice-quad(
  $quad as map(xs:string,item()*),
  $t as xs:double
) as map(xs:string,item()*)*
{
  if ($t = (0,1)) then $quad else
  let $p1 := this:start($quad)
  let $p2 := this:controls($quad)[1]
  let $p3 := this:end($quad)

  let $p12 := point:add($p1, point:sub($p2, $p1)=>point:times($t))
  let $p23 := point:add($p2, point:sub($p3, $p2)=>point:times($t))

  let $p123 := point:add($p12, point:sub($p23, $p12)=>point:times($t))
                
  return (
    (: Avoid creating quads that are really lines :)
    if (point:same($p1, $p2, $config:ε) or point:same($p2, $p3, $config:ε))
    then this:slice-linear(this:edge($p1, $p3), $t)
    else (
      if (point:same($p1, $p12, $config:ε) or point:same($p12, $p123, $config:ε)) then (
        this:edge($p1, $p123)
      ) else (
        this:quad($p1, $p123, $p12)
      ),
      if (point:same($p123, $p23, $config:ε) or point:same($p23, $p3, $config:ε)) then (
        this:edge($p123, $p3)
      ) else (
        this:quad($p123, $p3, $p23)
      )
    )
  )
}

Function: slice-cubic
declare function slice-cubic($cubic as map(xs:string,item()*),
  $t as xs:double) as map(xs:string,item()*)*

slice-cubic()
Create two cubic edges at the given fraction of the source cubic.

If t is at end, get same edge back.

Params

• cubic as map(xs:string,item()*): the cubic edge to cut
• t as xs:double: fraction of edge [0,1]

Returns

• map(xs:string,item()*)*

declare function this:slice-cubic(
  $cubic as map(xs:string,item()*),
  $t as xs:double
) as map(xs:string,item()*)*
{
  if ($t = (0,1)) then $cubic else
  let $p1 := this:start($cubic)
  let $p2 := this:controls($cubic)[1]
  let $p3 := this:controls($cubic)[2]
  let $p4 := this:end($cubic)

  let $p12 := point:add($p1, point:sub($p2, $p1)=>point:times($t))
  let $p23 := point:add($p2, point:sub($p3, $p2)=>point:times($t))
  let $p34 := point:add($p3, point:sub($p4, $p3)=>point:times($t))

  let $p123 := point:add($p12, point:sub($p23, $p12)=>point:times($t))
  let $p234 := point:add($p23, point:sub($p34, $p23)=>point:times($t))

  let $p1234 := point:add($p123, point:sub($p234, $p123)=>point:times($t))

  return (
    if (point:same($p1, $p2, $config:ε) or point:same($p2, $p3, $config:ε))
    then this:slice-quad(this:quad($p1, $p3, $p4), $t)
    else if (point:same($p4, $p3, $config:ε))
    then this:slice-quad(this:quad($p1, $p2, $p4), $t)
    else (
      (: Avoid creating "cubics" that are really quads or lines :)
      if (point:same($p12, $p123, $config:ε)) then (
        if (point:same($p1, $p12, $config:ε) or point:same($p123, $p1234, $config:ε)) then (
          (: Really a line: make a straight edge :)
          this:edge($p1, $p1234)
        ) else (
          (: Really a quad: make a quad edge :)
          this:quad($p1, $p1234, $p12)
        )
      ) else (
        this:cubic($p1, $p1234, $p12, $p123)
      ),
      if (point:same($p234, $p34, $config:ε)) then (
        if (point:same($p1234, $p234, $config:ε) or point:same($p34, $p4, $config:ε)) then (
          (: Really a line: make a straight edge :)
          this:edge($p1234, $p4)
        ) else (
          (: Really a quad: make a quad edge :)
          this:quad($p1234, $p4, $p234)
        )
      ) else (
        this:cubic($p1234, $p4, $p234, $p34)
      )
    )
  )
}

Function: slice-arc
declare function slice-arc($arc as map(xs:string,item()*),
  $t as xs:double) as map(xs:string,item()*)*

slice-arc()
Create two arc edges at the given fraction of the source arc.
If t is at end, get same edge back.
Normalizes the arc

Params

• arc as map(xs:string,item()*): the arc edge to cut
• t as xs:double: fraction of edge [0,1]

Returns

• map(xs:string,item()*)*

declare function this:slice-arc(
  $arc as map(xs:string,item()*),
  $t as xs:double
) as map(xs:string,item()*)*
{
  if ($t = (0,1)) then $arc else
  let $arc := this:normalize-arc($arc)
  let $center := $arc=>this:arc-center()
  let $radius := $arc=>this:arc-radius()
  let $angles := $arc=>this:arc-angles()
  let $from-angle := $angles[1]
  let $to-angle := $angles[2]
  let $da := $to-angle - $from-angle
  let $at := $from-angle + $t*$da
  let $larges :=
    if ($arc=>this:arc-large()) then (
      util:remap-degrees($at - $from-angle) > 180,
      util:remap-degrees($to-angle - $at) > 180
    ) else (
      false(), false()
    )
  let $a1 := this:arc-by-angle($center, $radius, util:remap-degrees($from-angle), util:remap-degrees($at), false(), $larges[1])
  let $a2 := this:arc-by-angle($center, $radius, util:remap-degrees($at), util:remap-degrees($to-angle), false(), $larges[2])
  return (
    if (point:same(this:start($arc), this:end($arc), $config:ε) and not(this:arc-large($arc))) then (
      this:slice-linear(this:edge(this:start($arc), this:end($arc)), $t)
    ) else (
      if (not($larges[1]) and point:same(this:start($a1), this:end($a1), $config:ε)) then (
        this:edge(this:start($a1), this:end($a1))
      ) else (
        $a1
      ),
      if (not($larges[2]) and point:same(this:start($a2), this:end($a2), $config:ε)) then (
        this:edge(this:start($a2), this:end($a2))
      ) else (
        $a2
      )
    )
  )
}

Function: midpoint
declare function midpoint($a as map(xs:string,item()*), $b as map(xs:string,item()*)) as map(xs:string,item()*)

midpoint()
Return midpoint between two points

Params

• a as map(xs:string,item()*): one point
• b as map(xs:string,item()*): the other

Returns

• map(xs:string,item()*)

declare function this:midpoint($a as map(xs:string,item()*), $b as map(xs:string,item()*)) as map(xs:string,item()*)
{
  point:midpoint($a, $b)
}

Function: midpoint
declare function midpoint($edge as map(xs:string,item()*)) as map(xs:string,item()*)

midpoint()
Center of the edge
Note: if you use on an arc, the arc must be normalized (edge:normalize-arc)

Params

• edge as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:midpoint($edge as map(xs:string,item()*)) as map(xs:string,item()*)
{
  switch (this:kind($edge))
  case "edge" return point:midpoint(this:start($edge), this:end($edge))
  case "quad" return this:quad-point($edge, 0.5)
  case "cubic" return this:cubic-point($edge, 0.5)
  case "arc" return this:arc-point($edge, 0.5)
  default return errors:error("GEOM-BADREGION", ($edge, "midpoint"))
}

Function: arc-midpoint
declare function arc-midpoint($center as map(xs:string,item()*),
  $a as map(xs:string,item()*),
  $b as map(xs:string,item()*)) as map(xs:string,item()*)

arc-midpoint()
Center of an arc. Note: arcs are treated as 2D, so output is 2D point;
we only look at x and y coordinates in the calculations.

Params

• center as map(xs:string,item()*): center of the circle defining the arc
• a as map(xs:string,item()*): start of arc
• b as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:arc-midpoint(
  $center as map(xs:string,item()*),
  $a as map(xs:string,item()*),
  $b as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  let $r := point:distance($center, $a)
  let $lm := this:midpoint($a, $b)
  let $v := point:sub($lm, $center)
  let $lenv := math:sqrt(point:px($v)*point:px($v) + point:py($v)*point:py($v))
  return
    if (point:sorientation($a, $b, $center) > 0) then (
      point:sub(
        $center,
        point:point($r*point:px($v) div $lenv, $r*point:py($v) div $lenv)
      )
    ) else (
      point:add(
        $center,
        point:point($r*point:px($v) div $lenv, $r*point:py($v) div $lenv)
      )
   )
}

Function: edge-point
declare function edge-point($edge as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)

edge-point()
Compute the point on the edge the given fraction from the start

Params

• edge as map(xs:string,item()*): the edge
• t as xs:double: fraction of distance from start to end (t) [0,1]

Returns

• map(xs:string,item()*)

declare function this:edge-point($edge as map(xs:string,item()*), $t as xs:double) as map(xs:string,item()*)
{
  switch (this:kind($edge))
  case "edge" return this:linear-point($edge, $t)
  case "arc" return this:arc-point($edge, $t)
  case "quad" return this:quad-point($edge, $t)
  case "cubic" return this:cubic-point($edge, $t)
  default return errors:error("GEOM-BADREGION", ($edge, "edge-point"))
}

Function: point-distance
declare function point-distance($edge as map(xs:string,item()*),
  $pt as map(xs:string,item()*)) as xs:double

point-distance()
Shortest distance from point to linear edge

Params

• edge as map(xs:string,item()*)
• pt as map(xs:string,item()*)

Returns

• xs:double

declare function this:point-distance(
  $edge as map(xs:string,item()*),
  $pt as map(xs:string,item()*)
) as xs:double
{
  if (point:same(this:start($edge), this:end($edge))) then (
    point:distance($pt, this:start($edge))
  ) else (
    let $v := this:start($edge)
    let $w := this:end($edge)
    let $l := this:linear-length($edge)
    let $lsquared := $l*$l
    let $w_sub_v := point:sub($w, $v)
    let $t := max((0, min((1, point:dot(point:sub($pt, $v), $w_sub_v) div $lsquared))))
    return (
      point:distance($pt,
        point:point(
          point:px($v) + $t * point:px($w_sub_v),
          point:py($v) + $t * point:py($w_sub_v)
        )
      )
    )
  )
}

Function: closest-point
declare function closest-point($edge as map(xs:string,item()*),
  $pt as map(xs:string,item()*)) as map(xs:string,item()*)

closest-point()
Point closest to the target point on the (linear) edge

Params

• edge as map(xs:string,item()*)
• pt as map(xs:string,item()*)

Returns

• map(xs:string,item()*)

declare function this:closest-point(
  $edge as map(xs:string,item()*),
  $pt as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  let $start := this:start($edge)
  let $end := this:end($edge)
  return (
    if (point:px($start)=point:px($end))
    then point:point(point:px($start), point:py($pt))
    else if (point:py($start)=point:py($end))
    then point:point(point:px($pt), point:py($start))
    else (
      let $m1 := (point:py($end) - point:py($start)) div (point:px($end) - point:px($start))
      let $m2 := -1 div $m1
      let $x := ($m1*point:px($start) - $m2*point:px($pt) + point:py($pt) - point:py($start)) div ($m1 - $m2)
      let $y := $m2*($x - point:px($pt)) + point:py($pt)
      return (
        point:point($x, $y)
      )
    )
  )
}

Function: on-segment-colinear
declare function on-segment-colinear($edge as map(xs:string,item()*),
  $p as map(xs:string,item()*),
  $tolerance as xs:double) as xs:boolean

on-segment-colinear()
Given edge and colinear point, check whether point is on that edge

Params

• edge as map(xs:string,item()*)
• p as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:on-segment-colinear(
  $edge as map(xs:string,item()*),
  $p as map(xs:string,item()*),
  $tolerance as xs:double
) as xs:boolean
{
  util:twixt(point:px($p),
    min(this:vertices($edge)!point:px(.)) - $tolerance,
    max(this:vertices($edge)!point:px(.)) + $tolerance
  )
  and
  util:twixt(point:py($p),
    min(this:vertices($edge)!point:py(.)) - $tolerance,
    max(this:vertices($edge)!point:py(.)) + $tolerance
  )
}

Function: on-segment-colinear
declare function on-segment-colinear($edge as map(xs:string,item()*),
  $p as map(xs:string,item()*)) as xs:boolean

Params

• edge as map(xs:string,item()*)
• p as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:on-segment-colinear(
  $edge as map(xs:string,item()*),
  $p as map(xs:string,item()*)
) as xs:boolean
{
  this:on-segment-colinear($edge, $p, $config:tolerance)
}

Function: on-segment
declare function on-segment($edge as map(xs:string,item()*),
  $p as map(xs:string,item()*)) as xs:boolean

on-segment()
Given edge and arbitary point, check whether point is on that edge

Params

• edge as map(xs:string,item()*)
• p as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:on-segment(
  $edge as map(xs:string,item()*),
  $p as map(xs:string,item()*)
) as xs:boolean
{
  this:on-segment($edge, $p, $config:tolerance)
}

Function: on-segment
declare function on-segment($edge as map(xs:string,item()*),
  $p as map(xs:string,item()*),
  $tolerance as xs:double) as xs:boolean

Params

• edge as map(xs:string,item()*)
• p as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:on-segment(
  $edge as map(xs:string,item()*),
  $p as map(xs:string,item()*),
  $tolerance as xs:double
) as xs:boolean
{
  (
    (point:sorientation(this:start($edge), this:end($edge), $p)=0) or
    (this:point-distance($edge, $p) < $tolerance)
  )
  and (
    util:twixt(point:px($p),
      min(this:vertices($edge)!point:px(.)) - $tolerance,
      max(this:vertices($edge)!point:px(.)) + $tolerance
    )
  )
  and (
    util:twixt(point:py($p),
      min(this:vertices($edge)!point:py(.)) - $tolerance,
      max(this:vertices($edge)!point:py(.)) + $tolerance
    )
  )
}

Function: linear-t
declare function linear-t($edge as map(xs:string,item()*),
  $point as map(xs:string,item()*)) as xs:double*

linear-t()
Compute the t value of the point wrt the linear edge.

Params

• edge as map(xs:string,item()*)
• point as map(xs:string,item()*)

Returns

• xs:double*

declare function this:linear-t(
  $edge as map(xs:string,item()*),
  $point as map(xs:string,item()*)
) as xs:double*
{
  if (this:on-segment-colinear($edge, $point)) then (
    point:distance(this:start($edge), $point) div this:length($edge)
  )
  else () 
}

Function: on-quad
declare function on-quad($quad as map(xs:string,item()*), $point as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean

on-quad()
True if the point is on the quadractic edge.

B(t)=(1-t)²P0 + 2(1-t)tP1 + t²P2, 0 <= t <= 1
B(t)=(P0 - 2P1 + P2)t² + (2P1 - 2P0)t + P0
If Q is on quad then solve (P0 - 2P1 + P2)t² + (2P1 - 2P0)t + P0 - Q = 0
i.e. (-b ± √((b² - 4ac))/2a where a=(P0 - 2P1 + P2), b=(2P1 - 2P0), c = (P0 - Q)
If t in range then you're good

We're using equality within ε here, because floating point equality is
problematic. Alternatively: you could compute minimum distance and
make sure it is within tolerance.

Params

• quad as map(xs:string,item()*)
• point as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:on-quad($quad as map(xs:string,item()*), $point as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean
{
  exists(this:quad-t($quad, $point, $tolerance))
}

Function: on-quad
declare function on-quad($quad as map(xs:string,item()*), $point as map(xs:string,item()*)) as xs:boolean

Params

• quad as map(xs:string,item()*)
• point as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:on-quad($quad as map(xs:string,item()*), $point as map(xs:string,item()*)) as xs:boolean
{
  this:on-quad($quad, $point, $config:tolerance)
}

Function: quad-t
declare function quad-t($quad as map(xs:string,item()*), $point as map(xs:string,item()*), $tolerance as xs:double) as xs:double*

quad-t()
Compute the t value of the point wrt the quadractic edge.

B(t)=(1-t)²P0 + 2(1-t)tP1 + t²P2, 0 <= t <= 1
B(t)=(P0 - 2P1 + P2)t² + (2P1 - 2P0)t + P0
If Q is on quad then solve (P0 - 2P1 + P2)t² + (2P1 - 2P0)t + P0 - Q = 0
i.e. (-b ± √((b² - 4ac))/2a where a=(P0 - 2P1 + P2), b=(2P1 - 2P0), c = (P0 - Q)
If t in range then you're good

We're using equality within ε here, because floating point equality is
problematic. Alternatively: you could compute minimum distance and
make sure it is within tolerance.

Params

• quad as map(xs:string,item()*)
• point as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:double*

declare function this:quad-t($quad as map(xs:string,item()*), $point as map(xs:string,item()*), $tolerance as xs:double) as xs:double*
{
  if (point:same($point, this:start($quad), $tolerance)) then 0.0
  else if (point:same($point, this:end($quad), $tolerance)) then 1.0
  else (
    let $P0 := this:start($quad)
    let $P1 := this:controls($quad)[1]
    let $P2 := this:end($quad)
    let $ax := point:px($P0) - 2*point:px($P1) + point:px($P2)
    let $bx := 2*point:px($P1) - 2*point:px($P0)
    let $cx := point:px($P0) - point:px($point)
    let $x-all-zero := every $x in ($ax, $bx, $cx) satisfies abs($x) < $config:ε
    let $ay := point:py($P0) - 2*point:py($P1) + point:py($P2)
    let $by := 2*point:py($P1) - 2*point:py($P0)
    let $cy := point:py($P0) - point:py($point)
    let $y-all-zero := every $y in ($ay, $by, $cy) satisfies abs($y) < $config:ε
    return (
      if ($x-all-zero and $y-all-zero) then (
        (: 
         : Quad is really a point
         : If this works it was caught above
         :)
      ) else if ($x-all-zero) then (
        (: 
         : Quad is really a straight line with all x's the same
         : If this works point x must be same, then use ty
         :)
        if (abs(point:px($point) - point:px($P0)) < $tolerance) then (
          let $ty := roots:quadratic-real-roots($ay, $by, $cy)[util:twixt(., -$config:ε, 1 + $config:ε)]
          for $t in $ty return util:clamp($t, 0.0, 1.0)
         ) else (
         )
      ) else if ($y-all-zero) then (
        (: 
         : Quad is really a straight line with all y's the same
         : If this works point y must be same, then use tx
         :)
        if (abs(point:py($point) - point:py($P0)) < $tolerance) then (
          let $tx := roots:quadratic-real-roots($ax, $bx, $cx)[util:twixt(., -$config:ε, 1 + $config:ε)]
          for $t in $tx return util:clamp($t, 0.0, 1.0)
         ) else (
         )
      ) else (
        (: 
         : Normal case: match tx with ty
         :)
        let $tx := roots:quadratic-real-roots($ax, $bx, $cx)[util:twixt(., -$config:ε, 1 + $config:ε)]
        let $ty := roots:quadratic-real-roots($ay, $by, $cy)[util:twixt(., -$config:ε, 1 + $config:ε)]
        let $ts := $tx[some $t in $ty satisfies abs(. - $t) < $config:ε]
        for $t in $ts return util:clamp($t, 0.0, 1.0)
      )
    )
  )
}

Function: quad-t
declare function quad-t($quad as map(xs:string,item()*), $point as map(xs:string,item()*)) as xs:double*

Params

• quad as map(xs:string,item()*)
• point as map(xs:string,item()*)

Returns

• xs:double*

declare function this:quad-t($quad as map(xs:string,item()*), $point as map(xs:string,item()*)) as xs:double*
{
  this:quad-t($quad, $point, $config:tolerance)
}

Function: on-cubic
declare function on-cubic($cubic as map(xs:string,item()*), $point as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean

on-cubic()
True if the point is on the cubic edge.
B(t)=(1-t)³P0 + 3(1-t)²tP1 + 3(1-t)t²P2 + t³P3, 0 <= t <= 1
B(t)=(P3 - 3P2 + P1 - P0)t³ + (3P2 - 6P1)t² + (3P1)t + P0
If Q is on cubic then solve
(P3 - 3P2 + P1 - P0)t³ + (3P2 - 6P1)t² + (3P1)t + P0 - Q = 0
i.e. cubic roots

If t in range then you're good

We're using equality within ε here, because floating point equality is
problematic. Alternatively: you could compute minimum distance and
make sure it is within tolerance.

Params

• cubic as map(xs:string,item()*)
• point as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:on-cubic($cubic as map(xs:string,item()*), $point as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean
{
  exists(this:cubic-t($cubic, $point, $tolerance))
}

Function: on-cubic
declare function on-cubic($cubic as map(xs:string,item()*), $point as map(xs:string,item()*)) as xs:boolean

Params

• cubic as map(xs:string,item()*)
• point as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:on-cubic($cubic as map(xs:string,item()*), $point as map(xs:string,item()*)) as xs:boolean
{
  this:on-cubic($cubic, $point, $config:tolerance)
}

Function: cubic-t
declare function cubic-t($cubic as map(xs:string,item()*), $point as map(xs:string,item()*), $tolerance as xs:double) as xs:double*

cubic-t()
Compute the t value of the point wrt the cubic edge.
B(t)=(1-t)³P0 + 3(1-t)²tP1 + 3(1-t)t²P2 + t³P3, 0 <= t <= 1
B(t)=(-P0 + 3P1 - 3P2 + P3)t³ + (3P0 - 6P1 + 3P2)t² + (-3P0 + 3P1)t + P0
If Q is on cubic then solve
(-P0 + 3P1 - 3P2 + P3)t³ + (3P0 - 6P1 + 3P2)t² + (-3P0 + 3P1)t + (P0 - Q)
i.e. cubic roots

If t in range then you're good

We're using equality within ε here, because floating point equality is
problematic. Alternatively: you could compute minimum distance and
make sure it is within tolerance.

Params

• cubic as map(xs:string,item()*)
• point as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:double*

declare function this:cubic-t($cubic as map(xs:string,item()*), $point as map(xs:string,item()*), $tolerance as xs:double) as xs:double*
{
  if (point:same($point, this:start($cubic), $tolerance)) then 0.0
  else if (point:same($point, this:end($cubic), $tolerance)) then 1.0
  else (
    let $P0 := this:start($cubic)
    let $P1 := this:controls($cubic)[1]
    let $P2 := this:controls($cubic)[2]
    let $P3 := this:end($cubic)
    let $ax := -point:px($P0) + 3*point:px($P1) - 3*point:px($P2) + point:px($P3)
    let $bx := 3*point:px($P0) - 6*point:px($P1) + 3*point:px($P2)
    let $cx := -3*point:px($P0) + 3*point:px($P1)
    let $dx := point:px($P0) - point:px($point)
    let $x-all-zero := every $x in ($ax, $bx, $cx, $dx) satisfies abs($x) < $config:ε
    let $ay := -point:py($P0) + 3*point:py($P1) - 3*point:py($P2) + point:py($P3)
    let $by := 3*point:py($P0) - 6*point:py($P1) + 3*point:py($P2)
    let $cy := -3*point:py($P0) + 3*point:py($P1)
    let $dy := point:py($P0) - point:py($point)
    let $y-all-zero := every $y in ($ay, $by, $cy, $dy) satisfies abs($y) < $config:ε
    return (
      if ($x-all-zero and $y-all-zero) then (
        (: 
         : Cubic is really a point
         : If this works it was caught above
         :)
      ) else if ($x-all-zero) then (
        (: 
         : Cubic is really a straight line with all x's the same
         : If this works point x must be same, then use ty
         :)
        if (abs(point:px($point) - point:px($P0)) < $tolerance) then (
          let $ty := roots:cubic-real-roots($ay, $by, $cy, $dy)[util:twixt(., -$config:ε, 1 + $config:ε)]
          for $t in $ty return util:clamp($t, 0.0, 1.0)
         ) else (
         )
      ) else if ($y-all-zero) then (
        (: 
         : Cubic is really a straight line with all y's the same
         : If this works point y must be same, then use tx
         :)
        if (abs(point:py($point) - point:py($P0)) < $tolerance) then (
          let $tx := roots:cubic-real-roots($ax, $bx, $cx, $dx)[util:twixt(., -$config:ε, 1 + $config:ε)]
          for $t in $tx return util:clamp($t, 0.0, 1.0)
         ) else (
         )
      ) else (
        (: 
         : Normal case: match tx with ty
         :)
        let $tx := roots:cubic-real-roots($ax, $bx, $cx, $dx)[util:twixt(., -$config:ε, 1 + $config:ε)]
        let $ty := roots:cubic-real-roots($ay, $by, $cy, $dy)[util:twixt(., -$config:ε, 1 + $config:ε)]
        let $ts := $tx[some $t in $ty satisfies abs(. - $t) < $config:ε]
        for $t in $ts return util:clamp($t, 0.0, 1.0)
      )
    )
  )
}

Function: cubic-t
declare function cubic-t($cubic as map(xs:string,item()*), $point as map(xs:string,item()*)) as xs:double*

Params

• cubic as map(xs:string,item()*)
• point as map(xs:string,item()*)

Returns

• xs:double*

declare function this:cubic-t($cubic as map(xs:string,item()*), $point as map(xs:string,item()*)) as xs:double*
{
  this:cubic-t($cubic, $point, $config:tolerance)
}

Function: on-arc
declare function on-arc($arc as map(xs:string,item()*),
  $point as map(xs:string,item()*),
  $tolerance as xs:double) as xs:boolean

on-arc()
Is the point on the arc (within ε)?
Note: will normalize the arc

Params

• arc as map(xs:string,item()*)
• point as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:on-arc(
  $arc as map(xs:string,item()*),
  $point as map(xs:string,item()*),
  $tolerance as xs:double
) as xs:boolean
{
  let $arc := this:normalize-arc($arc)
  let $center := $arc=>this:arc-center()
  let $radius := $arc=>this:arc-radius()
  let $angles := $arc=>this:arc-angles()
  let $from-angle := $angles[1]
  let $to-angle := $angles[2]
  return (
    abs(point:distance($center, $point) - $radius) < $tolerance and
    (
      util:twixt(this:angle($center, $point), $from-angle, $to-angle) or
      util:twixt(this:angle($center, $point)+360, $from-angle, $to-angle) 
    )
  )
}

Function: on-arc
declare function on-arc($arc as map(xs:string,item()*),
  $point as map(xs:string,item()*)) as xs:boolean

Params

• arc as map(xs:string,item()*)
• point as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:on-arc(
  $arc as map(xs:string,item()*),
  $point as map(xs:string,item()*)
) as xs:boolean
{
  this:on-arc($arc, $point, $config:tolerance)
}

Function: normalize-arc
declare function normalize-arc($arc as map(xs:string,item()*)) as map(xs:string,item()*)

normalize-arc()
A lot of arc operations need us to know the actual arc center and
starting/ending angles. For large and flipped arcs that's get
problematic. Rather than repeat that code everywhere, encapsulate
it here. The normalized arc will always run in sweep order and may or
may not be large.

Params

• arc as map(xs:string,item()*): source arc

Returns

• map(xs:string,item()*)

declare function this:normalize-arc(
  $arc as map(xs:string,item()*)
) as map(xs:string,item()*)
{
  let $arc := this:as-angle-arc($arc)
  let $flipped := $arc=>this:arc-flipped()
  let $large := $arc=>this:arc-large()
  let $angles := ($arc=>this:arc-angles())!util:remap-degrees(.)
  let $delta := $angles[2] - $angles[1]
  let $swap :=
    ($large and
      ($delta < -180 or ($delta > 0 and $delta < 180))
    ) or
    (not($large) and
      (($delta < 0 and abs($delta) < 180) or ($delta > 180))
    )
  let $adjust-from :=
    ($large and $delta > 0 and $delta < 180) or
    (not($large) and $delta > 180)
  let $adjust-to :=
    ($large and $delta < 0 and abs($delta) <= 180) or
    (not($large) and $delta <= -180)
  let $adjusted-from :=
    if ($adjust-from) then $angles[1] + 360 else $angles[1]
  let $adjusted-to :=
    if ($adjust-to) then $angles[2] + 360 else $angles[2]
  let $from-angle :=
    if ($swap) then $adjusted-to else $adjusted-from
  let $to-angle := 
    if ($swap) then $adjusted-from else $adjusted-to
  let $center := $arc=>this:arc-center()
  let $radius := $arc=>this:arc-radius()
  let $from := point:destination($center, $from-angle, $radius)
  let $to := point:destination($center, $to-angle, $radius)
  let $flipped-center :=
    if ($swap) then (
      if ($flipped) then $center else affine:reflect($center, $from, $to)
    ) else (
      if ($flipped) then affine:reflect($center, $from, $to) else $center
    )
  return (
    util:assert($from-angle <= $to-angle, "Normalized angles wonky"),
    util:assert((abs($to-angle - $from-angle) > 180) = $large, "Large flag wonky"),
    this:arc-by-angle(
      $flipped-center,
      $radius,
      $from-angle,
      $to-angle,
      false(),
      $large
    )
  )
}

Function: arc-t
declare function arc-t($arc as map(xs:string,item()*),
  $point as map(xs:string,item()*)) as xs:double*

arc-t()
Compute the t value of the point wrt the arc edge.
Will normalize the arc

Params

• arc as map(xs:string,item()*)
• point as map(xs:string,item()*)

Returns

• xs:double*

declare function this:arc-t(
  $arc as map(xs:string,item()*),
  $point as map(xs:string,item()*)
) as xs:double*
{
  if (point:same($point, this:start($arc))) then 0.0
  else if (point:same($point, this:end($arc))) then 1.0
  else (
    let $arc := this:normalize-arc($arc)
    let $center := $arc=>this:arc-center()
    let $radius := $arc=>this:arc-radius()
    let $angles := $arc=>this:arc-angles()
    let $from-angle := $angles[1]
    let $to-angle := $angles[2]
    let $point-angle := this:angle($center, $point)
    return (
      if (abs(point:distance($center, $point) - $radius) < $config:ε and
          (
            util:twixt($point-angle, $from-angle, $to-angle) or
            util:twixt($point-angle + 360, $from-angle, $to-angle)
          )
      ) then (
        ($point-angle - $from-angle) div ($to-angle - $from-angle)
      ) else ()
    )
  )
}

Function: edge-t
declare function edge-t($edge as map(xs:string,item()*),
  $point as map(xs:string,item()*)) as xs:double*

Params

• edge as map(xs:string,item()*)
• point as map(xs:string,item()*)

Returns

• xs:double*

declare function this:edge-t(
  $edge as map(xs:string,item()*),
  $point as map(xs:string,item()*)
) as xs:double*
{
  switch (this:kind($edge))
  case "quad" return this:quad-t($edge, $point)
  case "cubic" return this:cubic-t($edge, $point)
  case "edge" return this:linear-t($edge, $point)
  case "arc" return this:arc-t($edge, $point)
  default return errors:error("GEOM-NOTIMPLEMENTED", ("edge-t", this:kind($edge)))
}

Function: bounding-box
declare function bounding-box($regions as map(xs:string,item()*)*) as map(xs:string,item()*)

bounding-box()
Minimum box surrounding the region. Some approximation for non-linear
edges.

Params

• regions as map(xs:string,item()*)*

Returns

• map(xs:string,item()*)

declare function this:bounding-box($regions as map(xs:string,item()*)*) as map(xs:string,item()*)
{
  let $boxes := (
    for $region in $regions return switch (this:kind($region))
    case "edge" return 
      let $pts := this:points($region)
      return
        box:box(
          min($pts!point:px(.)), min($pts!point:py(.)),
          max($pts!point:px(.)), max($pts!point:py(.))
        )
    case "quad" return ( 
      (: P0 = start, P1 = control, P2 = end :)
      (: B(t) = (1-t)²·P0 + 2(1-t)t·P1 + t²·P2 :)
      (: B'(t) = a(1-t) + b where a = 2(B-A), b=2(C-B) :)
      (: A=P0 B=P1 C=P2 :)
      (: B'(t) = 0 where t = -a/(b-a) :)
      let $P0 := this:start($region)
      let $P1 := this:controls($region)[1]
      let $P2 := this:end($region)
      let $T := 
        point:map3(
          function ($p0 as xs:double, $p1 as xs:double, $p2 as xs:double) as xs:double {
            let $A := $p0
            let $B := $p1
            let $C := $p2
            let $a := 2*($B - $A)
            let $b := 2*($C - $B)
            return
              if ($a = $b) then xs:double("INF")
              else -$a div ($b - $a)
          },
          $P0, $P1, $P2
        )
      let $pts := (
        $P0, $P2, 
        if (util:twixt(point:px($T), 0, 1))
        then $region=>this:quad-point(point:px($T))
        else (),
        if (util:twixt(point:py($T), 0, 1))
        then $region=>this:quad-point(point:py($T))
        else ()
      )
      return
        box:box(
          min($pts!point:px(.)), min($pts!point:py(.)),
          max($pts!point:px(.)), max($pts!point:py(.))
        )
    )
    case "cubic" return (
      (: Cubic P1 to P4 with controls P2, P3 :)
      (: B(t) = (1-t)³·P1 + 3(1-t)²t·P2 + 3(1-t)t²·P3 + t³·P4 :)
      (: B'(t) = (1-t)²·A + 2(1-t)t·B + t²·C :)
      (: A=3(P2-P1), B=3(P3-P2), C=3(P4-P3) :)
      (: B'(t) = at² + bt + c = 0 => t = (-b ± √(b² - 4ac))/2a :)
      (: a = A - 2B + C = 3(-P1 + 3P2 - 3P3 + P4) :) 
      (: b = 2(B - A) = 6(P1 - 2P2 + P3) :) 
      (: c = A = 3(P2 - P1) :)
      let $P1 := this:start($region)
      let $P2 := this:controls($region)[1]
      let $P3 := this:controls($region)[2]
      let $P4 := this:end($region)
      let $ts := (
        let $p1 := point:px($P1)
        let $p2 := point:px($P2)
        let $p3 := point:px($P3)
        let $p4 := point:px($P4)
        let $a := 3*(-$p1 + 3*$p2 - 3*$p3 + $p4)
        let $b := 6*($p1 - 2*$p2 + $p3)
        let $c := 3*($p2 - $p1)
        return roots:quadratic-real-roots($a, $b, $c),
        let $p1 := point:py($P1)
        let $p2 := point:py($P2)
        let $p3 := point:py($P3)
        let $p4 := point:py($P4)
        let $a := 3*(-$p1 + 3*$p2 - 3*$p3 + $p4)
        let $b := 6*($p1 - 2*$p2 + $p3)
        let $c := 3*($p2 - $p1)
        return roots:quadratic-real-roots($a, $b, $c)
      )
      let $pts := (
        $P1, $P4,
        for $t in $ts return (
          if (util:twixt($t, 0, 1))
          then $region=>this:cubic-point($t)
          else ()
        )
      )
      return
        box:box(
          min($pts!point:px(.)), min($pts!point:py(.)),
          max($pts!point:px(.)), max($pts!point:py(.))
        )
    )
    case "arc" return (
      let $arc := this:normalize-arc($region)
      let $center := $arc=>this:arc-center()
      let $radius := $arc=>this:arc-radius()
      let $angles := $arc=>this:arc-angles()
      let $from-angle := $angles[1]
      let $to-angle := $angles[2]
      let $from := $arc=>this:start()
      let $to := $arc=>this:end()
      (: If the arc is less than 180° we can do better than the whole
       : circle's bounding box by computing the intersection of the
       : tangent lines and finding the point from that to center at r
       : Tangent line to p has slope angle(center,p)+90
       : Equation y = mx + b => p[y] = mp[x] + b => b = p[y] - mp[x]
       : Intersection of a1x + b1y + c1 = 0, a2x + b2y + c2 = 0
       : is ((b1c2 - b2c1)/(a1b2 - a2b1), (c1a2 - c2a1)/(a1b2 - a2b1))
       : a1=m b1=-1 c1=p[y]-mp[x]
       : a2=n b2=-1 c2=q[y]-mq[x]
       :)
      return (
        if ($from-angle = $to-angle) then (
          box:box($from, $from)
        ) else if ($to-angle - $from-angle < 180) then (
          let $m := util:radians($from-angle - 90)
          let $a1 := $m
          let $b1 := -1
          let $c1 := point:py($from) - $m*point:px($from)
          let $n := util:radians($to-angle - 90)
          let $a2 := $n
          let $b2 := -1
          let $c2 := point:py($to) - $n*point:px($to)
          let $intersection := (
            util:assert($a1*$b2 - $a2*$b1 != 0, "Non intersecting lines"),
            point:point(
              ($b1*$c2 - $b2*$c1) div ($a1*$b2 - $a2*$b1),
              ($c1*$a2 - $c2*$a1) div ($a1*$b2 - $a2*$b1)
            )
          )
          let $pts := (
            $from, $to,
            point:destination($center, this:angle($center, $intersection), $radius)
          )
          return
            box:box(
              min($pts!point:px(.)), min($pts!point:py(.)),
              max($pts!point:px(.)), max($pts!point:py(.))
            )
        ) else (
          ellipse:bounding-box(this:arc-circle($arc))
        )
      )
    )
    default return errors:error("GEOM-BADREGION", ($region, "bounding-box"))
  )
  return (
    if (empty($boxes)) then box:box(0,0,0,0)
    else if (empty(tail($boxes))) then $boxes
    else (
      let $pts := $boxes!this:points(.)
      return
        box:box(
          min($pts!point:px(.)), min($pts!point:py(.)),
          max($pts!point:px(.)), max($pts!point:py(.))
        )
    )
  )
}

Function: line-intersection
declare function line-intersection($this as map(xs:string,item()*),
  $that as map(xs:string,item()*)) as map(xs:string,item()*)?

line-intersection()
Point of intersection, if any between lines defined as extension of
two edges.
Assumes linear edges: so wrong for other kinds of edges

Params

• this as map(xs:string,item()*)
• that as map(xs:string,item()*)

Returns

• map(xs:string,item()*)?

declare function this:line-intersection(
  $this as map(xs:string,item()*),
  $that as map(xs:string,item()*)
) as map(xs:string,item()*)?
{
  (: edge: ((x1,y1), (x2,y2)) => line Ax + By = C
   : A = y2 - y1
   : B = x1 - x2
   : C = Ax1 + By1
   : det = A1 * B2 - A2 * B1
   : => ( (B2 * C1 - B1 * C2) / det, (A1 * C2 - A2 * C1) / det
   :)

  (: A = y2 - y1 ; Ax = A(this), Ay = A(that) :)
  let $A := (
    point:py(this:end($this)) - point:py(this:start($this)),
    point:py(this:end($that)) - point:py(this:start($that))
  )
  (: B = x1 - x2 ; Bx = B(this), By = B(that) :)
  let $B := (
    point:px(this:start($this)) - point:px(this:end($this)),
    point:px(this:start($that)) - point:px(this:end($that))
  )
  (: C = Ax1 + By1 ; Cx = C(this), Cy = C(that) :)
  let $C := (
    v:px($A) * point:px(this:start($this)) + v:px($B) * point:py(this:start($this)),
    v:py($A) * point:px(this:start($that)) + v:py($B) * point:py(this:start($that))
  )
  let $det := v:determinant($A, $B)
  return (
    if ($det = (0,-0)) then () else (
      point:point(
        -v:determinant($B, $C) div $det,
         v:determinant($A, $C) div $det
      )
    )
  )
}

Function: intersection
declare function intersection($this as map(xs:string,item()*),
  $that as map(xs:string,item()*)) as map(xs:string,item()*)*

intersection()
Point of intersection, if any between two edges

Params

• this as map(xs:string,item()*)
• that as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:intersection(
  $this as map(xs:string,item()*),
  $that as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  switch (this:kind($this))
  case "edge" return this:linear-intersection($this, $that)
  case "quad" return this:quad-intersection($this, $that)
  case "cubic" return this:cubic-intersection($this, $that)
  case "arc" return this:arc-intersection($this, $that)
  default return errors:error("GEOM-BADREGION", ($this, "intersection"))
}

Function: linear-intersection
declare function linear-intersection($edge as map(xs:string,item()*),
  $other as map(xs:string,item()*)) as map(xs:string,item()*)*

linear-intersection()
Point of intersection, if any between linear edge and some other edge

Params

• edge as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:linear-intersection(
  $edge as map(xs:string,item()*),
  $other as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  if (this:kind($edge) != "edge") then errors:error("GEOM-BADREGION", ($edge, "linear-intersection"))
  else ( switch(this:kind($other))
    case "edge" return (
      let $p := this:line-intersection($edge, $other)
      return (
        if (empty($p)) then ()
        else if (this:on-segment-colinear($edge, $p) and this:on-segment-colinear($other, $p))
        then $p
        else ()
      )
    )
    case "quad" return this:quad-intersection($other, $edge)
    case "cubic" return this:cubic-intersection($other, $edge)
    case "arc" return this:arc-intersection($other, $edge)
    default return errors:error("GEOM-BADREGION", ($edge, "linear-intersection"))
  )
}

Function: quad-edge-intersection-ts
declare function quad-edge-intersection-ts($quad as map(xs:string,item()*),
  $other as map(xs:string,item()*),
  $tolerance as xs:double) as xs:double*

Params

• quad as map(xs:string,item()*)
• other as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:double*

declare function this:quad-edge-intersection-ts(
  $quad as map(xs:string,item()*),
  $other as map(xs:string,item()*),
  $tolerance as xs:double
) as xs:double*
{
  if (this:kind($quad) != "quad") then errors:error("GEOM-BADREGION", ($quad, "quad-edge-intersection-ts"))
  else if (this:kind($other) != "edge") then errors:error("GEOM-BADREGION", ($quad, "quad-edge-intersection-ts"))
  else (
    (: https://pomax.github.io/bezierinfo/ :)
    let $angle := this:angle($other)
    let $rotated-edge :=
      this:mutate($other,
        function ($p as map(xs:string,item()*)) as map(xs:string,item()*) {affine:rotate($p, $angle, this:start($other))}
      )
    let $translation := point:py(this:start($rotated-edge))
    let $translated-edge :=
      this:mutate($rotated-edge,
        function ($p as map(xs:string,item()*)) as map(xs:string,item()*) {affine:translate($p, 0, -$translation)}
      )
    let $translated-quad :=
      this:mutate($quad,
        function ($p as map(xs:string,item()*)) as map(xs:string,item()*) {affine:rotate($p, $angle, this:start($other))=>affine:translate(0,-$translation)}
      )
    let $P0 := this:start($translated-quad)
    let $P1 := this:controls($translated-quad)[1]
    let $P2 := this:end($translated-quad)
    let $ts := (
      let $p0 := point:px($P0)
      let $p1 := point:px($P1)
      let $p2 := point:px($P2)
      let $a := $p0 - 2*$p1 + $p2
      let $b := 2*$p1 - 2*$p0
      let $c := $p0
      return roots:quadratic-real-roots($a, $b, $c)
      ,
      let $p0 := point:py($P0)
      let $p1 := point:py($P1)
      let $p2 := point:py($P2)
      let $a := $p0 - 2*$p1 + $p2
      let $b := 2*$p1 - 2*$p0
      let $c := $p0
      return roots:quadratic-real-roots($a, $b, $c)
    )
    return (
      distinct-values(
        for $t in $ts
        where (
          util:twixt($t, 0, 1) and (
            let $qp := this:quad-point($translated-quad, $t)
            return
              abs(point:py($qp)) < $tolerance and
              util:twixt(point:px($qp), point:px(this:start($translated-edge)), point:px(this:end($translated-edge)))
          )
        )
        return $t
      )
    )
  )
}

Function: quad-edge-intersection-ts
declare function quad-edge-intersection-ts($quad as map(xs:string,item()*),
  $other as map(xs:string,item()*)) as xs:double*

Params

• quad as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• xs:double*

declare function this:quad-edge-intersection-ts(
  $quad as map(xs:string,item()*),
  $other as map(xs:string,item()*)
) as xs:double*
{
  this:quad-edge-intersection-ts($quad, $other, $config:tolerance)
}

Function: quad-intersection
declare function quad-intersection($quad as map(xs:string,item()*),
  $other as map(xs:string,item()*)) as map(xs:string,item()*)*

quad-intersection()
Point of intersection, if any between quad edge and some other edge

Params

• quad as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:quad-intersection(
  $quad as map(xs:string,item()*),
  $other as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  if (this:kind($quad) != "quad") then errors:error("GEOM-BADREGION", ($quad, "quad-intersection"))
  else ( switch(this:kind($other))
    case "edge" return (
      let $good-ts := this:quad-edge-intersection-ts($quad, $other)
      for $t in $good-ts return this:quad-point($quad, $t)
    )
    case "quad" return (
      if (box:intersects-box(this:bounding-box($quad), this:bounding-box($other))) then (
        if (this:quad-length($quad) < $config:ε and
            this:quad-length($other) < $config:ε)
        then (
          this:midpoint($quad)
        ) else (
          let $pts :=
            let $quadsubs := this:slice-quad($quad, 0.5)
            let $othersubs := this:slice-quad($other, 0.5)
            for $subquad in $quadsubs
            for $subother in $othersubs
            return this:intersection($subquad, $subother)
          let $dpts := for $p in $pts return point:decimal($p, $this:precision)
          for $i in 1 to count($dpts)
          where every $j in 1 to $i - 1 satisfies (
            not(point:same($dpts[$i], $dpts[$j]))
          )
          return $pts[$i]
        )
      ) else (
      )
    )
    case "cubic" return this:cubic-intersection($other, $quad)
    default return errors:error("GEOM-BADREGION", ($other, "quad-intersection"))
  )
}

Function: cubic-intersection
declare function cubic-intersection($cubic as map(xs:string,item()*),
  $other as map(xs:string,item()*)) as map(xs:string,item()*)*

cubic-intersection()
Point of intersection, if any between cubic edge and some other edge

Params

• cubic as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:cubic-intersection(
  $cubic as map(xs:string,item()*),
  $other as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  if (this:kind($cubic) != "cubic") then errors:error("GEOM-BADREGION", ($cubic, "cubic-intersection"))
  else ( switch(this:kind($other))
    case "edge" return (
      if (box:intersects-box(this:bounding-box($cubic), this:bounding-box($other))) then (
        if (this:linear-length($other) < $config:ε and
            this:cubic-length($cubic, 4) < $config:ε)
        then this:midpoint($cubic)
        else (
          let $pts := 
            let $cubicsubs := this:slice-cubic($cubic, 0.5)
            let $othersubs := this:slice-linear($other, 0.5)
            for $subcubic in $cubicsubs
            for $subother in $othersubs
            return this:intersection($subcubic, $subother)
          let $dpts := for $p in $pts return point:decimal($p, $this:precision)
          for $i in 1 to count($dpts)
          where every $j in 1 to $i - 1 satisfies (
            not(point:same($dpts[$i], $dpts[$j]))
          )
          return $pts[$i]
        )
      ) else (
      )
    )
    case "quad" return (
      if (box:intersects-box(this:bounding-box($cubic), this:bounding-box($other))) then (
        if (this:quad-length($other) < $config:ε and
            this:cubic-length($cubic, 4) < $config:ε)
        then this:midpoint($cubic)
        else (
          let $pts :=
            let $cubicsubs := this:slice-cubic($cubic, 0.5)
            let $othersubs := this:slice-quad($other, 0.5)
            for $subcubic in $cubicsubs
            for $subother in $othersubs
            return this:intersection($subcubic, $subother)
          let $dpts := for $p in $pts return point:decimal($p, $this:precision)
          for $i in 1 to count($dpts)
          where every $j in 1 to $i - 1 satisfies (
            not(point:same($dpts[$i], $dpts[$j]))
          )
          return $pts[$i]
        )
      ) else (
      )
    )
    case "cubic" return (
      if (box:intersects-box(this:bounding-box($cubic), this:bounding-box($other))) then (
        if (this:cubic-length($cubic, 4) < $config:ε and
            this:cubic-length($other, 4) < $config:ε)
        then this:midpoint($cubic)
        else (
          let $pts :=
            let $cubicsubs := this:slice-cubic($cubic, 0.5)
            let $othersubs := this:slice-cubic($other, 0.5)
            for $subcubic in $cubicsubs
            for $subother in $othersubs
            return this:intersection($subcubic, $subother)
          let $dpts := for $p in $pts return point:decimal($p, $this:precision)
          for $i in 1 to count($dpts)
          where every $j in 1 to $i - 1 satisfies (
            not(point:same($dpts[$i], $dpts[$j]))
          )
          return $pts[$i]
        )
      ) else (
      )
    )
    default return errors:error("GEOM-BADREGION", ($other, "cubic-intersection"))
  )
}

Function: arc-intersection
declare function arc-intersection($arc as map(xs:string,item()*),
  $other as map(xs:string,item()*)) as map(xs:string,item()*)*

Params

• arc as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:arc-intersection(
  $arc as map(xs:string,item()*),
  $other as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  if (this:kind($arc) != "arc") then errors:error("GEOM-BADREGION", ($arc, "arc-intersection"))
  else ( switch(this:kind($other))
    case "edge" return (
      let $arc := this:normalize-arc($arc)
      (: https://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle :)
      (: line y=mx + c; m = (y2-y1)/(x2-x1), c=y1 :)
      let $r := this:arc-radius($arc)
      let $p := point:px(this:arc-center($arc))
      let $q := point:py(this:arc-center($arc)) 
      let $x1 := point:px(this:start($other))
      let $y1 := point:py(this:start($other))
      let $x2 := point:px(this:end($other))
      let $y2 := point:py(this:end($other))
      let $pts := (
         if (abs($x1 - $x2) < $config:ε) then ( (: vertical line :)
           let $k := $x1
           let $A := 1
           let $B := -2*$q
           let $C := $p*$p + $q*$q - $r*$r - 2*$k*$p + $k*$k
           where $B*$B >= 4*$A*$C
           return (
             for $y in roots:quadratic-real-roots($A, $B, $C)
             return point:point($k, $y)
           )
         ) else (
           let $m := ($y2 - $y1) div ($x2 - $x1)
           let $c := $y1 - $m*$x1
           let $A := $m*$m + 1
           let $B := 2*($m*$c - $m*$q - $p)
           let $C := $q*$q - $r*$r + $p*$p - 2*$c*$q + $c*$c
           where $B*$B >= 4*$A*$C
           return (
             for $x in roots:quadratic-real-roots($A, $B, $C)
             return point:point($x, $m*$x + $c)
           )
         )
      )
      return (
        for $pt in $pts 
        where this:on-segment-colinear($other, $pt) and this:on-arc($arc, $pt)
        return $pt
      )
    )
    case "quad" return (
        errors:error("GEOM-NOTIMPLEMENTED", ("arc-intersection", this:kind($other)))
    )
    case "cubic" return (
        errors:error("GEOM-NOTIMPLEMENTED", ("arc-intersection", this:kind($other)))
    )
    case "arc" return (
        errors:error("GEOM-NOTIMPLEMENTED", ("arc-intersection", this:kind($other)))
    ) 
    default return errors:error("GEOM-BADREGION", ($other, "arc-intersection"))
  )
}

Function: edge-intersects-edge
declare function edge-intersects-edge($edge as map(xs:string,item()*),
  $other as map(xs:string,item()*)) as xs:boolean

linear edge to linear edge intersection

Params

• edge as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:edge-intersects-edge(
  $edge as map(xs:string,item()*),
  $other as map(xs:string,item()*)
) as xs:boolean
{
  this:edge-intersects-edge($edge, $other, $config:tolerance)
}

Function: edge-intersects-edge
declare function edge-intersects-edge($edge as map(xs:string,item()*),
  $other as map(xs:string,item()*),
  $tolerance as xs:double) as xs:boolean

Params

• edge as map(xs:string,item()*)
• other as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:edge-intersects-edge(
  $edge as map(xs:string,item()*),
  $other as map(xs:string,item()*),
  $tolerance as xs:double
) as xs:boolean
{
  (: See https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ :)
  let $o1 := point:sorientation(this:start($edge), this:end($edge), this:start($other))
  let $o2 := point:sorientation(this:start($edge), this:end($edge), this:end($other))
  let $o3 := point:sorientation(this:start($other), this:end($other), this:start($edge))
  let $o4 := point:sorientation(this:start($other), this:end($other), this:end($edge))
  return (
    ($o1 != $o2 and $o3 != $o4) or
    (: $other.start colinear with and on segment $edge :)
    ($o1=0 and this:on-segment-colinear($edge, this:start($other), $tolerance)) or
    (: $other.end colinear with and on segment $edge :)
    ($o2=0 and this:on-segment-colinear($edge, this:end($other), $tolerance)) or
    (: $edge.start colinear with and on segment $other :)
    ($o3=0 and this:on-segment-colinear($other, this:start($edge), $tolerance)) or
    (: $edge.end colinear with and on segment $other :)
    ($o4=0 and this:on-segment-colinear($other, this:end($edge), $tolerance))
  )
}

Function: linear-intersects
declare function linear-intersects($edge as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean

linear-intersects()
Edge (straight) intersects some other region kind

Params

• edge as map(xs:string,item()*)
• other as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:linear-intersects($edge as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean
{
  switch (this:kind($other))
  case "point" return this:on-segment($edge, $other, $tolerance)
  case "edge" return this:edge-intersects-edge($edge, $other, $tolerance) 
  case "quad" return this:quad-intersects($other, $edge, $tolerance)
  case "cubic" return this:cubic-intersects($other, $edge, $tolerance)
  case "arc" return this:arc-intersects($other, $edge, $tolerance)
  default return errors:error("GEOM-BADREGION", ($other, "linear-intersects"))
}

Function: linear-intersects
declare function linear-intersects($edge as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean

Params

• edge as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:linear-intersects($edge as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean
{
  this:linear-intersects($edge, $other, $config:tolerance)
}

Function: quad-intersects
declare function quad-intersects($quad as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean

quad-intersects()
Quad edge intersects some other region kind

Params

• quad as map(xs:string,item()*)
• other as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:quad-intersects($quad as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean
{
  switch (this:kind($other))
  case "point" return this:on-quad($quad, $other, $tolerance)
  case "edge" return exists(this:quad-edge-intersection-ts($quad, $other, $tolerance))
  case "quad" return (
    if (box:intersects-box(this:bounding-box($quad), this:bounding-box($other), $tolerance)) then (
      if (this:quad-length($quad) < $config:ε and
          this:quad-length($other) < $config:ε)
      then true()
      else (
        let $quadsubs := this:slice-quad($quad, 0.5)
        let $othersubs := this:slice-quad($other, 0.5)
        return (
          some $subquad in $quadsubs
          satisfies (
            some $subother in $othersubs
            satisfies this:edge-intersects($subquad, $subother, $tolerance)
          )
        )
      )
    ) else (
      false()
    )
  )
  case "cubic" return this:cubic-intersects($other, $quad, $tolerance)
  case "arc" return this:arc-intersects($other, $quad, $tolerance)
  default return errors:error("GEOM-BADREGION", ($other, "quad-intersects"))
}

Function: quad-intersects
declare function quad-intersects($quad as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean

Params

• quad as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:quad-intersects($quad as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean
{
  this:quad-intersects($quad, $other, $config:tolerance)
}

Function: cubic-intersects
declare function cubic-intersects($cubic as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean

cubic-intersects()
Cubic edge intersects some other region kind

Params

• cubic as map(xs:string,item()*)
• other as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:cubic-intersects($cubic as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean
{
  switch (this:kind($other))
  case "point" return (
    this:on-cubic($cubic, $other, $tolerance)
  )
  case "edge" return (
    if (box:intersects-box(this:bounding-box($cubic), this:bounding-box($other), $tolerance)) then (
      if (this:linear-length($other) < $tolerance and
          this:cubic-length($cubic, 4) < $tolerance)
      then true()
      else (
        let $cubicsubs := this:slice-cubic($cubic, 0.5)
        let $othersubs := this:slice-linear($other, 0.5)
        return (
          some $subcubic in $cubicsubs
          satisfies (
            some $subother in $othersubs
            satisfies this:edge-intersects($subcubic, $subother, $tolerance)
          )
        )
      )
    ) else (
      false()
    )
  )
  case "quad" return (
    if (box:intersects-box(this:bounding-box($cubic), this:bounding-box($other), $tolerance)) then (
      if (this:quad-length($other) < $tolerance and
          this:cubic-length($cubic, 4) < $tolerance)
      then true()
      else (
        let $cubicsubs := this:slice-cubic($cubic, 0.5)
        let $othersubs := this:slice-quad($other, 0.5)
        return (
          some $subcubic in $cubicsubs
          satisfies (
            some $subother in $othersubs
            satisfies this:edge-intersects($subcubic, $subother, $tolerance)
          )
        )
      )
    ) else (
      false()
    )
  )
  case "cubic" return (
    if (box:intersects-box(this:bounding-box($cubic), this:bounding-box($other), $tolerance)) then (
      if (this:cubic-length($cubic, 4) < $tolerance and
          this:cubic-length($other, 4) < $tolerance)
      then true()
      else (
        let $cubicsubs := this:slice-cubic($cubic, 0.5)
        let $othersubs := this:slice-cubic($other, 0.5)
        return (
          some $subcubic in $cubicsubs
          satisfies (
            some $subother in $othersubs
            satisfies this:edge-intersects($subcubic, $subother, $tolerance)
          )
        )
      )
    ) else (
      false()
    )
  )
  case "arc" return this:arc-intersects($other, $cubic, $tolerance)
  default return errors:error("GEOM-BADREGION", ($other, "cubic-intersects"))
}

Function: cubic-intersects
declare function cubic-intersects($cubic as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean

Params

• cubic as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:cubic-intersects($cubic as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean
{
  this:cubic-intersects($cubic, $other, $config:tolerance)
}

Function: arc-intersects
declare function arc-intersects($arc as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean

arc-intersects()
Arc edge intersects some other region kind

Params

• arc as map(xs:string,item()*)
• other as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:arc-intersects($arc as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean
{
  if (point:same(this:start($arc), this:end($arc), $tolerance)) then (
    if (this:arc-large($arc)) then (
      this:edge-intersects(this:arc-circle(this:normalize-arc($arc)), $other, $tolerance)
    ) else (
      this:edge-intersects(this:start($arc), $other, $tolerance)
    )
  ) else switch (this:kind($other))
  case "point" return this:on-arc($arc, $other, $tolerance)
  case "edge" return
    let $arc := this:normalize-arc($arc)
    (: https://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle :)
    (: line y=mx + x; m = (y2-y1)/(x2-x1), c=y1 :)
    let $r := this:arc-radius($arc)
    let $p := point:px(this:arc-center($arc))
    let $q := point:py(this:arc-center($arc)) 
    let $x1 := point:px(this:start($other))
    let $y1 := point:py(this:start($other))
    let $x2 := point:px(this:end($other))
    let $y2 := point:py(this:end($other))
    let $pts := 
       if (abs($x1 - $x2) < $config:ε) then ( (: vertical line :)
         let $k := $x1
         let $A := 1
         let $B := -2*$q
         let $C := $p*$p + $q*$q - $r*$r - 2*$k*$p + $k*$k
         where $B*$B >= 4*$A*$C
         return (
           for $y in roots:quadratic-real-roots($A, $B, $C)
           return point:point($k, $y)
         )
       ) else (
         let $m := ($y2 - $y1) div ($x2 - $x1)
         let $c := $y1 - $m*$x1
         let $A := $m*$m + 1
         let $B := 2*($m*$c - $m*$q - $p)
         let $C := $q*$q - $r*$r + $p*$p - 2*$c*$q + $c*$c
         where $B*$B >= 4*$A*$C
         return (
           for $x in roots:quadratic-real-roots($A, $B, $C)
           return point:point($x, $m*$x + $c)
         )
       )
    return (
      some $pt in $pts 
      satisfies this:on-segment-colinear($other, $pt, $tolerance) and
                this:on-arc($arc, $pt, $tolerance)
    )
  case "quad" return (
    if (box:intersects-box(this:bounding-box($arc), this:bounding-box($other), $tolerance)) then (
      if (this:arc-length($arc) < $tolerance and
          this:quad-length($other) < $tolerance)
      then (
        true()
      ) else (
        let $arcsubs := this:slice-arc($arc, 0.5)
        let $othersubs := this:slice-quad($other, 0.5)
        return (
          some $subarc in $arcsubs
          satisfies (
            some $subother in $othersubs
            satisfies this:edge-intersects($subarc, $subother, $tolerance)
          )
        )
      )
    ) else (
      false()
    )
  )
  case "cubic" return (
    if (box:intersects-box(this:bounding-box($arc), this:bounding-box($other), $tolerance)) then (
      if (this:arc-length($arc) < $tolerance and
          this:cubic-length($other, 4) < $tolerance)
      then true()
      else (
        let $arcsubs := this:slice-arc($arc, 0.5)
        let $othersubs := this:slice-cubic($other, 0.5)
        return (
          some $subarc in $arcsubs
          satisfies (
            some $subother in $othersubs
            satisfies this:edge-intersects($subarc, $subother, $tolerance)
          )
        )
      )
    ) else (
      false()
    )
  )
  case "arc" return
    let $arc := this:normalize-arc($arc)
    return (
      ellipse:ellipse-intersects-ellipse(this:arc-circle($arc), this:arc-circle($other), $tolerance) and
      (
        (: https://stackoverflow.com/questions/3349125/circle-circle-intersection-points :)
        let $d := point:distance(this:arc-center($arc), this:arc-center($other))
        return if ($d <= $tolerance) then (
          some $pt in (this:start($other), this:end($other))
          satisfies this:on-arc($arc, $pt, $tolerance)
        ) else (
          let $r1 := this:arc-radius($arc)
          let $p1 := this:arc-center($arc)
          let $x1 := point:px($p1)
          let $y1 := point:py($p1)
          let $r2 := this:arc-radius($other)
          let $p2 := this:arc-center($other)
          let $x2 := point:px($p2)
          let $y2 := point:py($p2)
          let $l := ($r1*$r1 - $r2*$r2 + $d*$d) div (2*$d)
          let $h := math:sqrt($r1*$r1 - $l*$l)
          let $dp := $p2=>point:sub($p1)
          let $dx := $x2 - $x1
          let $dy := $y2 - $y1
          let $mid := $p1=>point:add($dp=>point:times($l div $d))
          let $pts := (
            $mid=>point:add($dp=>point:times($h div $d)),
            $mid=>point:sub($dp=>point:times($h div $d))
          )
          return (
            some $pt in $pts 
            satisfies this:on-arc($arc, $pt, $tolerance) and
                      this:on-arc($other, $pt, $tolerance)
          )
        )
      )
    )
  default return errors:error("GEOM-BADREGION", ($other, "arc-intersects"))
}

Function: arc-intersects
declare function arc-intersects($arc as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean

Params

• arc as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:arc-intersects($arc as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean
{
  this:arc-intersects($arc, $other, $config:tolerance)
}

Function: edge-intersects
declare function edge-intersects($region as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean

Params

• region as map(xs:string,item()*)
• other as map(xs:string,item()*)
• tolerance as xs:double

Returns

• xs:boolean

declare function this:edge-intersects($region as map(xs:string,item()*), $other as map(xs:string,item()*), $tolerance as xs:double) as xs:boolean
{
  switch (this:kind($region))
  case "point" return this:edge-intersects($other, $region, $tolerance)
  case "edge" return this:linear-intersects($region, $other, $tolerance)
  case "quad" return this:quad-intersects($region, $other, $tolerance)
  case "cubic" return this:cubic-intersects($region, $other, $tolerance)
  case "arc" return this:arc-intersects($region, $other, $tolerance)
  default return errors:error("GEOM-BADREGION", ($other, "edge-intersects"))
}

Function: edge-intersects
declare function edge-intersects($region as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean

Params

• region as map(xs:string,item()*)
• other as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:edge-intersects($region as map(xs:string,item()*), $other as map(xs:string,item()*)) as xs:boolean
{
  this:edge-intersects($region, $other, $config:tolerance)
}

Function: tangent
declare function tangent($region as map(xs:string,item()*),
  $t as xs:double) as map(xs:string,item()*)

tangent()
Return the tangent vector to the given point on the edge (2D)

Params

• region as map(xs:string,item()*)
• t as xs:double

Returns

• map(xs:string,item()*)

declare function this:tangent(
  $region as map(xs:string,item()*),
  $t as xs:double
) as map(xs:string,item()*)
{
  switch(this:kind($region))
  case "edge" return (
    this:end($region)=>point:sub(this:start($region))=>point:normalize()
  )
  case "quad" return (
    (: 
     : Derivative:
     : P0 = start, P1 = control, P2 = end 
     : B(t) = (1-t)²·P0 + 2(1-t)t·P1 + t²·P2 
     : B'(t) = (1-t)·A + t·B
     : B'(t) = a(1-t) + b where a = 2(B-A), b=2(C-A)
     : A=P0 B=P1
     :)
    let $P0 := this:start($region)
    let $P1 := this:controls($region)[1]
    let $P2 := this:end($region)
    return (
      point:map3(
        function ($p0 as xs:double, $p1 as xs:double, $p2 as xs:double) as xs:double {
          let $A := $p0
          let $B := $p1
          let $C := $p2
          let $a := 2*($B - $A)
          let $b := 2*($C - $B)
          return $a*(1 - $t) + $b
        },
        $P0, $P1, $P2
      )=>point:normalize()
    )
  )
  case "cubic" return (
    (: 
     : Derivative 
     : Cubic P1 to P4 with controls P2, P3 
     : B(t) = (1-t)³·P1 + 3(1-t)²t·P2 + 3(1-t)t²·P3 + t³·P2 
     : B'(t) = (1-t)²·A + 2(1-t)t·B + t²·C 
     : A=3(P2-P1), B=3(P3-P2), C=3(P4-P3)
     : B'(t) = at² + bt + c = 0
     : a = A - 2B + C = 3(-P1 + 3P2 - 3P3 + P4)
     : b = 2(B - A) = 6(P1 - 2P2 + P3)
     : c = A = 3(P2 - P1)
     :)
    let $P1 := this:start($region)
    let $P2 := this:controls($region)[1]
    let $P3 := this:controls($region)[2]
    let $P4 := this:end($region)
    return (
      point:map4(
        function ($p1 as xs:double, $p2 as xs:double, $p3 as xs:double, $p4 as xs:double) as xs:double {
          let $a := 3*(-$p1 + 3*$p2 - 3*$p3 + $p4)
          let $b := 6*($p1 - 2*$p2 + $p3)
          let $c := 3*($p2 - $p1)
          return $a*$t*$t + $b*$t + $c
        },
        $P1, $P2, $P3, $P4
      )
    )=>point:normalize()
  )
  case "arc" return (
    let $region := this:normalize-arc($region)
    let $c := this:arc-center($region)
    let $r := this:arc-radius($region)
    let $ellipse := ellipse:circle($c, $r)
    let $arc-angles := this:arc-angles($region)
    let $start-t := $arc-angles[1] div 360
    let $end-t := $arc-angles[2] div 360
    (: t for ellipse: ts + (te - ts)*ta :)
    let $revised-t := $start-t + ($end-t - $start-t)*$t
    let $p := $ellipse=>ellipse:ellipse-point($revised-t)
    let $angle := point:angle($c, $p)
    return (
      this:edge(
        point:destination($p, $angle - 90, 1),
        point:destination($p, $angle + 90, 1)
      )=>point:normalize()
    )
  )
  case "ellipse" return (
    (: May seem odd for this to be here, but edge depends on ellipse
     : and this is making an edge :)
    let $c := ellipse:center($region)
    let $p := $region=>ellipse:ellipse-point($t)
    let $angle := point:angle($c, $p)
    return (
      this:edge(
        point:destination($p, $angle - 90, 1),
        point:destination($p, $angle + 90, 1)
      )=>point:normalize()
    )
  )
  default return errors:error("GEOM-NOTIMPLEMENTED", ("tangent", this:kind($region)))
}

Function: curvature
declare function curvature($edge as map(xs:string,item()*),
  $t as xs:double) as xs:double

curvature()
Return the curvature at the given point on the edge (2D)
κ(t) = |det(B(t),B''(t)|/||B'(t)||³

Params

• edge as map(xs:string,item()*)
• t as xs:double

Returns

• xs:double

declare function this:curvature(
  $edge as map(xs:string,item()*),
  $t as xs:double
) as xs:double
{
  abs(this:signed-curvature($edge, $t))
}

Function: signed-curvature
declare function signed-curvature($edge as map(xs:string,item()*),
  $t as xs:double) as xs:double

signed-curvature()
Return the signed curvature at the given point on the edge (2D)
k(t) = det(B(t),B''(t)/||B'(t)||³

Params

• edge as map(xs:string,item()*)
• t as xs:double

Returns

• xs:double

declare function this:signed-curvature(
  $edge as map(xs:string,item()*),
  $t as xs:double
) as xs:double
{
  switch(this:kind($edge))
  case "edge" return (
    0
  )
  case "quad" return (
    (: 
     : Derivative:
     : P0 = start, P1 = control, P2 = end 
     : B(t) = (1-t)²·P0 + 2(1-t)t·P1 + t²·P2
     : B(t) = (P0 - 2P1 + P2)t² + (-2P0 + 2P1)t + P0
     : B'(t) = a(1-t) + b where a = 2(B-A), b=2(C-A)
     : B''(t) = -a where a=2(B-A) i.e. 2(A-B)
     : A=P0 B=P1 C=P2
     :)
    let $P0 := this:start($edge)=>point:pcoordinates()
    let $P1 := (this:controls($edge)[1])=>point:pcoordinates()
    let $P2 := this:end($edge)=>point:pcoordinates()
    let $Bt := (
      v:map3(
        function ($p0 as xs:double, $p1 as xs:double, $p2 as xs:double) as xs:double {
          ($p0 - 2*$p1 + $p2)*$t*$t + 2*($p1 - $p0) + $p0
        },
        $P0, $P1, $P2
      )
    )
    let $Btder := (
      v:map3(
        function ($p0 as xs:double, $p1 as xs:double, $p2 as xs:double) as xs:double {
          let $A := $p0
          let $B := $p1
          let $C := $p2
          let $a := 2*($B - $A)
          let $b := 2*($C - $B)
          return $a*(1 - $t) + $b
        },
        $P0, $P1, $P2
      )
    )
    let $Btdoubleder :=  
      v:map2( function ($p0 as xs:double, $p1 as xs:double) as xs:double { 2*($p0 - $p1) }, $P0, $P1 ) 
    return (
      (: k(t) = det(B(t),B''(t)/||B'(t)||³ :)
      v:determinant($Bt, $Btdoubleder) div math:pow(v:magnitude($Btder), 3)
    )
  )
  case "cubic" return (
    (: 
     : Derivative 
     : Cubic P1 to P4 with controls P2, P3 
     : B(t) = (1-t)³·P1 + 3(1-t)²t·P2 + 3(1-t)t²·P3 + t³·P2
     : B'(t) = (1-t)²·A + 2(1-t)t·B + t²·C 
     : A=3(P2-P1), B=3(P3-P2), C=3(P4-P3)
     : B'(t) = at² + bt + c = 0
     : a = A - 2B + C = 3(-P1 + 3P2 - 3P3 + P4)
     : b = 2(B - A) = 6(P1 - 2P2 + P3)
     : c = A = 3(P2 - P1)
     : B''(t) = 2at + b
     :)
    let $P1 := this:start($edge)=>point:pcoordinates()
    let $P2 := (this:controls($edge)[1])=>point:pcoordinates()
    let $P3 := (this:controls($edge)[2])=>point:pcoordinates()
    let $P4 := this:end($edge)=>point:pcoordinates()
    let $Bt := (
      v:map4(
        function ($p1 as xs:double, $p2 as xs:double, $p3 as xs:double, $p4 as xs:double) as xs:double {
          let $one-t := 1 - $t
          return (
            math:pow($one-t, 3)*$p1 +
            2*math:pow($one-t, 2)*$t*$p2 +
            2*$one-t*math:pow($t, 2)*$p3 +
            math:pow($t, 3)*$p2
          )
        },
        $P1, $P2, $P3, $P4
      )
    )
    let $Btder := (
      v:map4(
        function ($p1 as xs:double, $p2 as xs:double, $p3 as xs:double, $p4 as xs:double) as xs:double {
          let $a := 3*(-$p1 + 3*$p2 - 3*$p3 + $p4)
          let $b := 6*($p1 - 2*$p2 + $p3)
          let $c := 3*($p2 - $p1)
          return $a*$t*$t + $b*$t + $c
        },
        $P1, $P2, $P3, $P4
      )
    )
    let $Btdoubleder := (
      v:map4(
        function ($p1 as xs:double, $p2 as xs:double, $p3 as xs:double, $p4 as xs:double) as xs:double {
          let $a := 3*(-$p1 + 3*$p2 - 3*$p3 + $p4)
          let $b := 6*($p1 - 2*$p2 + $p3)
          return 2*$a*$t + $b
        },
        $P1, $P2, $P3, $P4
      )
    )
    return (
      (: k(t) = det(B(t),B''(t)/||B'(t)||³ :)
      v:determinant($Bt, $Btdoubleder) div math:pow(v:magnitude($Btder), 3)
    )
  )
  case "arc" return
    if (this:arc-flipped($edge))
    then -1 div this:arc-radius($edge)
    else 1 div this:arc-radius($edge)
  default return errors:error("GEOM-NOTIMPLEMENTED", ("curvature", this:kind($edge)))
}

Function: osculating-circle
declare function osculating-circle($edge as map(xs:string,item()*),
  $t as xs:double) as map(xs:string,item()*)

osculating-circle()
Compute the osculating circle at the given point on the edge.
Returns a zero radius circle at the edge point for infinite or NaN
curvatures.

Params

• edge as map(xs:string,item()*)
• t as xs:double

Returns

• map(xs:string,item()*)

declare function this:osculating-circle(
  $edge as map(xs:string,item()*),
  $t as xs:double
) as map(xs:string,item()*)
{
  (:
   :
   : N(t) = normal unit vector
   : T'(t) = k(t)N(t)
   : k(t) is signed version of κ(t) 
   : R(t) = 1/κ(t)
   : C(t) = B(t) + (1/κ²(t))T'(t) center of osculating circle  
   :      = B(t) + (1/κ²(t))k(t)N(t)
   :      = B(t) + R²(t)(sign(k(t))/R(t))N(t)
   :      = B(t) + sign(k(t))R(t)N(t)
   :)
  let $k := $edge=>this:signed-curvature($t)
  let $κ := abs($k)
  let $n := $edge=>this:tangent($t)=>point:perpendicular()=>point:normalize()
  let $p := $edge=>this:edge-point($t)
  return (
    if (not($κ=$κ)) then ellipse:circle($p, 0)
    else if ($κ = xs:double("INF")) then ellipse:circle($p, 0)
    else (
      let $radius := if ($κ = 0) then this:length($edge) div 2 else 1 div $κ
      let $sign := if ($κ = 0) then 1 else util:zsign($k)
      let $center := $n=>point:times($sign*$radius)=>point:add($p)
      return (
        util:assert(not($radius=xs:double("INF")), "Bad radius: INF "||($κ=0)),
        util:assert($radius=$radius, "Bad radius: NaN"),
        ellipse:circle($center, $radius)
      )
    )
  )
}

Function: interpolate-edge-using
declare function interpolate-edge-using($edge as map(xs:string,item()*),
  $divisions as function(item()) as xs:double*) as map(xs:string,item()*)*

Params

• edge as map(xs:string,item()*)
• divisions as function(item())asxs:double*

Returns

• map(xs:string,item()*)*

declare function this:interpolate-edge-using(
  $edge as map(xs:string,item()*),
  $divisions as function(item()) as xs:double*
) as map(xs:string,item()*)*
{
  let $from := this:start($edge)
  let $to := this:end($edge)
  let $d := point:max-dimension(($from, $to))
  for $t in $divisions($edge)
  order by $t ascending
  return (
    point:map2(
      function ($a as xs:double, $b as xs:double) as xs:double {
        $a + $t * ($b - $a)
      },
      $from,
      $to,
      $d
    )
  )
}

Function: interpolate-edge
declare function interpolate-edge($n as xs:integer,
  $edge as map(xs:string,item()*),
  $exclusive as xs:boolean) as map(xs:string,item()*)*

interpolate-edge()
Interpolate a linear edge.

Params

• n as xs:integer: number of interpolating points
• edge as map(xs:string,item()*): the edge
• exclusive as xs:boolean: exclude end point? default=false

Returns

• map(xs:string,item()*)*

declare function this:interpolate-edge(
  $n as xs:integer,
  $edge as map(xs:string,item()*),
  $exclusive as xs:boolean
) as map(xs:string,item()*)*
{
  this:interpolate-edge-using($edge,
    function ($region as map(xs:string,item()*)) as xs:double* {
      util:linspace($n, 0, 1, $exclusive)
    }
  )
}

Function: interpolate-edge
declare function interpolate-edge($n as xs:integer,
  $edge as map(xs:string,item()*)) as map(xs:string,item()*)*

Params

• n as xs:integer
• edge as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:interpolate-edge(
  $n as xs:integer,
  $edge as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  this:interpolate-edge($n, $edge, false())
}

Function: interpolate-quadratic-using
declare function interpolate-quadratic-using($quadratic as map(xs:string,item()*),
  $divisions as function(item()) as xs:double*) as map(xs:string,item()*)*

Params

• quadratic as map(xs:string,item()*)
• divisions as function(item())asxs:double*

Returns

• map(xs:string,item()*)*

declare function this:interpolate-quadratic-using(
  $quadratic as map(xs:string,item()*),
  $divisions as function(item()) as xs:double*
) as map(xs:string,item()*)*
{
  let $from := $quadratic=>this:start()
  let $to := $quadratic=>this:end()
  let $controls := $quadratic=>this:controls()
  let $d := point:max-dimension(($from, $to, $controls[1]))
  for $t in $divisions($quadratic)
  order by $t ascending
  return (
    point:map3(
      function ($a as xs:double, $b as xs:double, $c as xs:double) as xs:double {
        (1 - $t)*(1 - $t)*$a +
        2*(1 - $t)*$t*$c +
        $t*$t*$b
      },
      $from, $to, $controls[1],
      $d
    )
  )
}

Function: interpolate-quadratic
declare function interpolate-quadratic($n as xs:integer,
  $quadratic as map(xs:string,item()*),
  $exclusive as xs:boolean) as map(xs:string,item()*)*

interpolate-quadratic()
Interpolate a quadratic edge.

B(t)=(1-t)²P0 + 2(1-t)tP1 + t²P2, 0 <= t <= 1

Params

• n as xs:integer: number of interpolating points
• quadratic as map(xs:string,item()*) the edge
• exclusive as xs:boolean: exclude end point? default=false

Returns

• map(xs:string,item()*)*

declare function this:interpolate-quadratic(
  $n as xs:integer,
  $quadratic as map(xs:string,item()*),
  $exclusive as xs:boolean
) as map(xs:string,item()*)*
{
  this:interpolate-quadratic-using($quadratic,
    function ($region as map(xs:string,item()*)) as xs:double* {
      util:linspace($n, 0, 1, $exclusive)
    }
  )
}

Function: interpolate-quadratic
declare function interpolate-quadratic($n as xs:integer,
  $quadratic as map(xs:string,item()*)) as map(xs:string,item()*)*

Params

• n as xs:integer
• quadratic as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:interpolate-quadratic(
  $n as xs:integer,
  $quadratic as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  this:interpolate-quadratic($n, $quadratic, false())
}

Function: interpolate-cubic-using
declare function interpolate-cubic-using($cubic as map(xs:string,item()*),
  $divisions as function(item()) as xs:double*) as map(xs:string,item()*)*

Params

• cubic as map(xs:string,item()*)
• divisions as function(item())asxs:double*

Returns

• map(xs:string,item()*)*

declare function this:interpolate-cubic-using(
  $cubic as map(xs:string,item()*),
  $divisions as function(item()) as xs:double*
) as map(xs:string,item()*)*
{
  let $from := $cubic=>this:start()
  let $to := $cubic=>this:end()
  let $controls := $cubic=>this:controls()
  let $d := point:max-dimension(($from, $to, $controls[1], $controls[2]))
  for $t in $divisions($cubic)
  order by $t ascending
  return (
    point:map4(
      function ($a as xs:double, $b as xs:double, $c as xs:double, $d as xs:double) as xs:double {
        (1 - $t)*(1 - $t)*(1 - $t)*$a +
        3*(1 - $t)*(1 - $t)*$t*$c +
        3*(1 - $t)*$t*$t*$d +
        $t*$t*$t*$b
      },
      $from, $to, $controls[1], $controls[2],
      $d
    )
  )
}

Function: interpolate-cubic
declare function interpolate-cubic($n as xs:integer,
  $cubic as map(xs:string,item()*),
  $exclusive as xs:boolean) as map(xs:string,item()*)*

interpolate-cubic()
Interpolate a cubic edge.

B(t)=(1-t)³P0 + 3(1-t)²tP1 + 3(1-t)t²P2 + t³P3, 0 <= t <= 1

Params

• n as xs:integer: number of interpolating points
• cubic as map(xs:string,item()*) the edge
• exclusive as xs:boolean: exclude end point? default=false

Returns

• map(xs:string,item()*)*

declare function this:interpolate-cubic(
  $n as xs:integer,
  $cubic as map(xs:string,item()*),
  $exclusive as xs:boolean
) as map(xs:string,item()*)*
{
  this:interpolate-cubic-using($cubic,
    function ($region as map(xs:string,item()*)) as xs:double* {
      util:linspace($n, 0, 1, $exclusive)
    }
  )
}

Function: interpolate-cubic
declare function interpolate-cubic($n as xs:integer,
  $cubic as map(xs:string,item()*)) as map(xs:string,item()*)*

Params

• n as xs:integer
• cubic as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:interpolate-cubic(
  $n as xs:integer,
  $cubic as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  this:interpolate-cubic($n, $cubic, false())
}

Function: interpolate-arc-using
declare function interpolate-arc-using($arc as map(xs:string,item()*),
  $divisions as function(item()) as xs:double*) as map(xs:string,item()*)*

interpolate-arc-using()
angle arc: break into sub-angles
point arc: point on circle => dest(center, angle, radius)
We only do angle interpolations; so convert to angle representation

However: the center and start/end to use depends on large and flipped
We reflect around the line between start/end points when we drawing on
the arc from the other circle through the points

Remapped degrees run from 0 to 360
We need to adjust the angles to account for running backwards and
for crossing 0
If flipped then reflect, unless we swapped, in which case reflect if we
aren't flipped.

Cases:
from=200 to=10 large => to-from = -190 swap; 10 to 200; reverse
from=200 to=40 large => to-from = -160 to+=360; 200 to 400
from=10 to=200 large => to-from = 190 10 to 200
from=40 to=200 large => to-from = 160 swap; from+=360; 200 to 400; reverse

from=200 to=10 !large => to-from = -190 to+=360; 200 to 370
from=200 to=40 !large => to-from = -160 swap; 40 to 200; reverse
from=10 to=200 !large => to-from = 190 swap; from+=360; 200 to 370; reverse
from=40 to=200 !large => to-from = 160 40 to 200

Params

• arc as map(xs:string,item()*)
• divisions as function(item())asxs:double*

Returns

• map(xs:string,item()*)*

declare function this:interpolate-arc-using(
  $arc as map(xs:string,item()*),
  $divisions as function(item()) as xs:double*
) as map(xs:string,item()*)*
{
  let $arc := this:normalize-arc($arc)
  let $center := $arc=>this:arc-center()
  let $radius := $arc=>this:arc-radius()
  let $angles := $arc=>this:arc-angles()
  let $from-angle := $angles[1]
  let $to-angle := $angles[2]
  let $da := $to-angle - $from-angle
  return (
    for $t in $divisions($arc)
    order by $t ascending
    return (
      point:destination($center, $from-angle + $t * $da, $radius)
    )
  )
}

Function: interpolate-arc
declare function interpolate-arc($n as xs:integer,
  $arc as map(xs:string,item()*),
  $exclusive as xs:boolean) as map(xs:string,item()*)*

interpolate-arc()
Interpolate a arc edge.

Params

• n as xs:integer: number of interpolating points
• arc as map(xs:string,item()*) the edge
• exclusive as xs:boolean: exclude end point? default=false

Returns

• map(xs:string,item()*)*

declare function this:interpolate-arc(
  $n as xs:integer,
  $arc as map(xs:string,item()*),
  $exclusive as xs:boolean
) as map(xs:string,item()*)*
{
  this:interpolate-arc-using($arc,
    function ($region as map(xs:string,item()*)) as xs:double* {
      util:linspace($n, 0, 1, $exclusive)
    }
  )
}

Function: interpolate-arc
declare function interpolate-arc($n as xs:integer,
  $arc as map(xs:string,item()*)) as map(xs:string,item()*)*

Params

• n as xs:integer
• arc as map(xs:string,item()*)

Returns

• map(xs:string,item()*)*

declare function this:interpolate-arc(
  $n as xs:integer,
  $arc as map(xs:string,item()*)
) as map(xs:string,item()*)*
{
  this:interpolate-arc($n, $arc, false())
}

Function: interpolate-using
declare function interpolate-using($edges as map(xs:string,item()*)*,
  $divisions as function(item()) as xs:double*) as map(xs:string,item()*)*

Params

• edges as map(xs:string,item()*)*
• divisions as function(item())asxs:double*

Returns

• map(xs:string,item()*)*

declare function this:interpolate-using(
  $edges as map(xs:string,item()*)*,
  $divisions as function(item()) as xs:double*
) as map(xs:string,item()*)*
{
  for $edge in $edges return
  switch (this:kind($edge))
  case "edge" return this:interpolate-edge-using($edge, $divisions)
  case "arc" return this:interpolate-arc-using($edge, $divisions)
  case "quad" return this:interpolate-quadratic-using($edge, $divisions)
  case "cubic" return this:interpolate-cubic-using($edge, $divisions)
  default return $edge
}

Function: interpolate
declare function interpolate($n as xs:integer,
  $edges as map(xs:string,item()*)*,
  $exclusive as xs:boolean) as map(xs:string,item()*)*

interpolate()
Interpolate the edges; return the interpolated points.

Params

• n as xs:integer: number of points of interpolation for each edge
• edges as map(xs:string,item()*)*
• exclusive as xs:boolean: include end point? default=false

Returns

• map(xs:string,item()*)*

declare function this:interpolate(
  $n as xs:integer,
  $edges as map(xs:string,item()*)*,
  $exclusive as xs:boolean
) as map(xs:string,item()*)*
{
  this:interpolate-using($edges,
    if ($exclusive) then (
      function ($edge as map(xs:string,item()*)) as xs:double* {
        util:linspace($n, 0, 1, true())
      }
    ) else (
      function ($edge as map(xs:string,item()*)) as xs:double* {
        util:linspace($n, 0, 1)
      }
    )
  )
}

Function: interpolate
declare function interpolate($n as xs:integer,
  $edges as map(xs:string,item()*)*) as map(xs:string,item()*)*

Params

• n as xs:integer
• edges as map(xs:string,item()*)*

Returns

• map(xs:string,item()*)*

declare function this:interpolate(
  $n as xs:integer,
  $edges as map(xs:string,item()*)*
) as map(xs:string,item()*)*
{
  this:interpolate($n, $edges, false())
}

Function: is-straight-edge
declare function is-straight-edge($edge as map(xs:string,item()*)) as xs:boolean

is-straight-edge()
Test whether the edge is straight: either a linear edge or degenerate.

Params

• edge as map(xs:string,item()*)

Returns

• xs:boolean

declare function this:is-straight-edge(
  $edge as map(xs:string,item()*)
) as xs:boolean
{
  switch (this:kind($edge))
  case "edge" return true()
  case "quad" return
    point:sorientation(this:start($edge), this:controls($edge), this:end($edge))=0 or
    this:length($edge) = 0
  case "cubic" return
    (point:sorientation(this:start($edge), this:controls($edge)[1], this:end($edge))=0 and
    point:sorientation(this:start($edge), this:controls($edge)[2], this:end($edge))=0) or
    this:length($edge) = 0
  case "arc" return
    this:length($edge) = 0
  default return errors:error("GEOM-BADREGION", ($edge, "is-straight-edge"))
}

Function: is-straight
declare function is-straight($edges as map(xs:string,item()*)*) as xs:boolean

is-straight()
Does the sequence of edges align?

Params

• edges as map(xs:string,item()*)*

Returns

• xs:boolean

declare function this:is-straight($edges as map(xs:string,item()*)*) as xs:boolean
{
  let $n := count($edges)
  return (
    this:is-straight-edge(head($edges)) and
    (
      every $i in 2 to $n satisfies (
        this:is-straight-edge($edges[$i]) and
        point:sorientation(this:start($edges[$i - 1]), this:start($edges[$i]), this:end($edges[$i]))=0
      )
    )
  )
}

Function: map-command
declare function map-command($kind as xs:string?,
  $relative as xs:string?) as xs:string

Params

• kind as xs:string?
• relative as xs:string?

Returns

• xs:string

declare function this:map-command(
  $kind as xs:string?,
  $relative as xs:string?
) as xs:string
{
  switch ($relative)
  case "relative" return (
    switch ($kind)
    case "goto" return "m"
    case "close" return "z"
    case "line" return "l"
    case "hr" return "h"
    case "vr" return "v"
    case "cubic" return "c"
    case "smooth_cubic" return "s"
    case "quad" return "q"
    case "smooth_quad" return "t"
    case "arc" return "a"
    case "ellipse-arc" return "a"
    default (: line :) return "l"
  )
  default (: absolute :) return (
    switch ($kind)
    case "goto" return "M"
    case "close" return "Z"
    case "line" return "L"
    case "hr" return "H"
    case "vr" return "V"
    case "cubic" return "C"
    case "smooth_cubic" return "S"
    case "quad" return "Q"
    case "smooth_quad" return "T"
    case "arc" return "A"
    case "ellipse-arc" return "A"
    default (: line :) return "L"
  )
}

Function: translate-edge
declare function translate-edge($edge as map(xs:string,item()*)) as xs:string

Params

• edge as map(xs:string,item()*)

Returns

• xs:string

declare function this:translate-edge(
  $edge as map(xs:string,item()*)
) as xs:string
{
  string-join((
    this:map-command(($edge("variety"),$edge("kind"))[1],"absolute"),
    switch(this:kind($edge))
    case "arc" return (
      (: XYZZY should swap start and end for large to get proper intent :)
      this:arc-radius($edge), (: rx :)
      this:arc-radius($edge), (: ry :)
      0,                      (: rotate :)
      if (this:arc-large($edge)) then 1 else 0, (: large-arc :)
      if (this:arc-flipped($edge)) then 0 else 1 (: sweep :)
    )
    case "ellipse-arc" return (
      $edge("rx"), (: rx :)
      $edge("ry"), (: ry :)
      0,           (:rotate :)
      if (this:arc-large($edge)) then 1 else 0, (: large-arc :)
      if (this:arc-flipped($edge)) then 0 else 1 (: sweep :)
    )
    case "quad" return (
      point:px(this:controls($edge)[1]), (: c1.x :)
      point:py(this:controls($edge)[1])  (: c1.y :)
    )
    case "cubic" return (
      point:px(this:controls($edge)[1]), (: c1.x :)
      point:py(this:controls($edge)[1]), (: c1.y :)
      point:px(this:controls($edge)[2]), (: c2.x :)
      point:py(this:controls($edge)[2])  (: c2.y :)
    )
    default return ()
    ,
    point:px(this:end($edge)),
    point:py(this:end($edge))
  )!string(.)," ")
}

Function: draw
declare function draw($item as map(xs:string,item()*),
  $properties as map(xs:string,item()*),
  $drawing as map(xs:string,function(*)?)) as item()*

Params

• item as map(xs:string,item()*)
• properties as map(xs:string,item()*)
• drawing as map(xs:string,function(*)?)

Returns

• item()*

declare function this:draw(
  $item as map(xs:string,item()*),
  $properties as map(xs:string,item()*),
  $drawing as map(xs:string,function(*)?)
) as item()*
{
  if ($config:DRAWING-METHOD="art") then (
    switch(this:kind($item))
    case "edge" return $this:draw-edge-impl($item, $properties, $drawing)
    case "quad" return $this:draw-quad-impl($item, $properties, $drawing)
    case "cubic" return $this:draw-cubic-impl($item, $properties, $drawing)
    case "arc" return $this:draw-arc-impl($item, $properties, $drawing) 
    case "ellipse-arc" return $this:draw-ellipse-arc-impl($item, $properties, $drawing)
    default return ()
  ) else (
    $this:draw-svg-edge-impl($item, $properties, $drawing)
  )
}