Repository Public MIT
1// ORIX Calc2// File: Packages/ORIXGraph/Tests/ORIXGraphTests/CurveAndImplicitTests.swift3// Description: Parametric, polar and implicit curves checked against the true curves; false contours across poles and jumps must be rejected.4//5// Author: Simon-Pierre Boucher6// Contact: contact@spboucher.ai7import Foundation8import Testing9import ORIXExpression10@testable import ORIXGraph1112private let square = Viewport(xMin: -3, xMax: 3, yMin: -3, yMax: 3, width: 600, height: 600)1314/// Largest screen distance between consecutive vertices and from the true curve to the polyline, sampled densely in t.15private func curveError(_ plot: CurvePlot, _ point: (Double) -> Point2, _ range: ClosedRange<Double>, _ view: Viewport) -> Double {16 var worst = 0.017 let segments = plot.polylines.flatMap { l in zip(l.points, l.points.dropFirst()).map { (view.toScreen($0), view.toScreen($1)) } }18 for i in 0...3000 {19 let t = range.lowerBound + (range.upperBound - range.lowerBound) * Double(i) / 300020 let p = point(t)21 guard p.x.isFinite, p.y.isFinite, view.contains(p) else { continue }22 let s = view.toScreen(p)23 var best = Double.infinity24 for (a, b) in segments { best = min(best, distanceToSegment(s, a, b)); if best < 0.05 { break } }25 worst = max(worst, best)26 }27 return worst28}2930@Suite struct ParametricAndPolar {31 @Test func unitCircle() {32 let p = Sampler.sampleParametric(x: { cos($0) }, y: { sin($0) }, range: 0...(2 * .pi), viewport: square)33 #expect(p.polylines.count == 1 && p.polylines[0].isClosed && p.discontinuities.isEmpty)34 #expect(p.polylines[0].points.allSatisfy { abs(($0.x * $0.x + $0.y * $0.y).squareRoot() - 1) < 1e-12 })35 #expect(curveError(p, { Point2(cos($0), sin($0)) }, 0...(2 * .pi), square) < 0.3)36 #expect(p.pointCount <= 2000)37 }3839 @Test func lissajous() throws {40 let item = try PlotParser.parse("(sin(3t), cos(2t))")41 let g = try GraphEngine.geometry(for: item, viewport: square)42 #expect(g.polylines.count == 1 && g.polylines[0].isClosed)43 // every vertex is on the curve: x = sin 3t, y = cos 2t ⇒ with u = acos(y)/2 the abscissa is ± sin(3u) or ± sin(3(π − u))44 for p in g.polylines[0].points {45 let u = acos(min(max(p.y, -1), 1)) / 246 let candidates = [sin(3 * u), -sin(3 * u), sin(3 * (.pi - u)), -sin(3 * (.pi - u))]47 #expect(candidates.contains { abs($0 - p.x) < 1e-6 })48 }49 let plot = Sampler.sampleParametric(x: { sin(3 * $0) }, y: { cos(2 * $0) }, range: 0...(2 * .pi), viewport: square)50 #expect(curveError(plot, { Point2(sin(3 * $0), cos(2 * $0)) }, 0...(2 * .pi), square) < 0.3)51 }5253 @Test func cardioid() throws {54 let item = try PlotParser.parse("r = 1 - cos(θ)")55 guard case .polar = item.kind else { Issue.record("not polar"); return }56 let g = try GraphEngine.geometry(for: item, viewport: square)57 #expect(g.polylines.count == 1 && g.polylines[0].isClosed)58 // (x² + y² + x)² = x² + y²59 #expect(g.polylines[0].points.allSatisfy { p in60 let r2 = p.x * p.x + p.y * p.y61 return abs((r2 + p.x) * (r2 + p.x) - r2) < 1e-962 })63 let xs = g.polylines[0].points.map(\.x)64 #expect(abs(xs.min()! + 2) < 1e-3 && xs.max()! < 0.26)65 }6667 @Test func roseWithNegativeRadius() throws {68 // r = cos(2θ) is negative for θ in (π/4, 3π/4): those points belong on the opposite ray (the petals along the y axis).69 let g = try GraphEngine.geometry(for: PlotParser.parse("r = cos(2 theta)"), viewport: square)70 #expect(g.polylines.count == 1 && g.polylines[0].isClosed)71 let pts = g.polylines[0].points72 // implicit form of the four-petal rose: (x² + y²)³ = (x² − y²)²73 #expect(pts.allSatisfy { p in74 let r2 = p.x * p.x + p.y * p.y75 return abs(r2 * r2 * r2 - (p.x * p.x - p.y * p.y) * (p.x * p.x - p.y * p.y)) < 1e-976 })77 // all four petal tips are reached, including (0, ±1) which come from negative r78 for tip in [Point2(1, 0), Point2(-1, 0), Point2(0, 1), Point2(0, -1)] {79 #expect(pts.contains { $0.distance(to: tip) < 0.01 })80 }81 // direct check of the sign convention82 let direct = Sampler.samplePolar({ _ in -1 }, range: 0...0.001, viewport: square)83 #expect(abs(direct.polylines[0].points[0].x + 1) < 1e-12)84 }8586 @Test func polarInDegrees() throws {87 var context = EvalContext()88 context.angleMode = .degrees89 let item = try PlotParser.parse("r = 2")90 #expect(item.effectiveParameterRange(angleMode: .degrees) == 0...360)91 let g = try GraphEngine.geometry(for: item, viewport: square, context: context)92 #expect(g.polylines.count == 1 && g.polylines[0].isClosed)93 #expect(g.polylines[0].points.allSatisfy { abs(($0.x * $0.x + $0.y * $0.y).squareRoot() - 2) < 1e-12 })94 }9596 @Test func parametricBreaksAtJumpsPolesAndUndefinedValues() throws {97 let view = Viewport(xMin: -4, xMax: 4, yMin: -4, yMax: 4, width: 800, height: 800)98 let steps = try GraphEngine.geometry(for: PlotParser.parse("(t, floor(t)) for -3 <= t <= 2.5"), viewport: view)99 #expect(steps.polylines.count == 6)100 #expect(steps.discontinuities.map(\.kind) == [.jump, .jump, .jump, .jump, .jump])101 #expect(steps.discontinuities.map(\.x) == [-2, -1, 0, 1, 2])102 for line in steps.polylines { #expect(Set(line.points.map(\.y)).count == 1) } // no riser103104 let hyperbola = try GraphEngine.geometry(for: PlotParser.parse("(t, 1/t) for -2 <= t <= 2"), viewport: view)105 #expect(hyperbola.polylines.count == 2)106 #expect(hyperbola.discontinuities.count == 1 && hyperbola.discontinuities[0].kind == .pole && hyperbola.discontinuities[0].x == 0)107 #expect(hyperbola.polylines.allSatisfy { l in l.points.allSatisfy { $0.x * $0.y > 0 } && Set(l.points.map { $0.x > 0 }).count == 1 })108 #expect(hyperbola.polylines.allSatisfy { l in l.points.allSatisfy { abs($0.y) <= 12.0001 && abs($0.x) <= 12.0001 } })109110 let tangent = try GraphEngine.geometry(for: PlotParser.parse("(t, tan(t)) for 0 <= t <= 6"), viewport: view)111 #expect(tangent.polylines.count == 3)112 #expect(tangent.discontinuities.map(\.kind) == [.pole, .pole])113 #expect(abs(tangent.discontinuities[0].x - .pi / 2) < 1e-9 && abs(tangent.discontinuities[1].x - 1.5 * .pi) < 1e-9)114 for line in tangent.polylines { #expect(zip(line.points, line.points.dropFirst()).allSatisfy { $1.y >= $0.y - 1e-9 }) }115116 let root = try GraphEngine.geometry(for: PlotParser.parse("(sqrt(t), t) for -1 <= t <= 3"), viewport: view)117 #expect(root.polylines.count == 1)118 #expect(root.polylines[0].points.first!.distance(to: .zero) < 1e-9)119 #expect(root.discontinuities.count == 1 && root.discontinuities[0].kind == .undefinedInterval && abs(root.discontinuities[0].xEnd) < 1e-15)120121 let hole = Sampler.sampleParametric(x: { $0 }, y: { $0 == 0 ? .nan : sin($0) / $0 }, range: -2...2, viewport: view)122 #expect(hole.polylines.count == 1 && hole.discontinuities.map(\.kind) == [.removable])123 }124125 @Test func spiralIsNotClosedAndStaysAccurate() {126 let view = Viewport(xMin: -20, xMax: 20, yMin: -20, yMax: 20, width: 800, height: 800)127 let p = Sampler.samplePolar({ $0 }, range: 0...(6 * .pi), viewport: view)128 #expect(p.polylines.count == 1 && !p.polylines[0].isClosed)129 #expect(curveError(p, { Point2($0 * cos($0), $0 * sin($0)) }, 0...(6 * .pi), view) < 0.3)130 }131}132133@Suite struct ImplicitCurves {134 let view = Viewport(xMin: -10, xMax: 10, yMin: -10, yMax: 10, width: 400, height: 400)135136 @Test func circle() {137 let p = ImplicitPlotter.plot(fn2("x^2 + y^2 - 25"), viewport: view)138 #expect(p.polylines.count == 1 && p.polylines[0].isClosed && p.reliable && p.rejectedCrossings == 0)139 let tolerance = 0.02 * view.unitsPerPixelX140 let worst = p.polylines[0].points.map { abs(($0.x * $0.x + $0.y * $0.y).squareRoot() - 5) }.max()!141 #expect(worst < tolerance, "worst radial error \(worst) units, allowed \(tolerance)")142 // the loop goes once around: the polygon area is that of the disc143 let pts = p.polylines[0].points144 var area = 0.0145 for i in 0..<pts.count { let a = pts[i], b = pts[(i + 1) % pts.count]; area += a.x * b.y - b.x * a.y }146 #expect(abs(abs(area) / 2 - 25 * .pi) < 0.05)147 // consecutive vertices are neighbours on screen148 #expect((0..<pts.count).allSatisfy { view.toScreen(pts[$0]).distance(to: view.toScreen(pts[($0 + 1) % pts.count])) < 3.5 })149 }150151 @Test func hyperbolaHasTwoBranchesThatNeverCrossTheAxes() throws {152 let item = try PlotParser.parse("xy = 1")153 guard case .implicit = item.kind else { Issue.record("xy = 1 should be implicit"); return }154 let g = try GraphEngine.geometry(for: item, viewport: view)155 #expect(g.polylines.count == 2)156 for line in g.polylines {157 #expect(line.points.allSatisfy { $0.x * $0.y > 0 })158 #expect(Set(line.points.map { $0.x > 0 }).count == 1)159 #expect(line.points.allSatisfy { abs($0.x * $0.y - 1) < 0.02 })160 #expect(!line.isClosed)161 }162 // y = 1/x written with the pole in the equation: the sign change across x = 0 is not a curve163 // (on this symmetric grid x = 0 is a lattice line where the equation is undefined: the cells are simply skipped)164 let p = ImplicitPlotter.plot(fn2("1/x - y"), viewport: view)165 #expect(p.polylines.count == 2 && p.reliable)166 #expect(p.polylines.allSatisfy { l in l.points.allSatisfy { abs($0.x) > 0.09 && abs($0.x * $0.y - 1) < 0.02 } })167 // off the lattice the equation has finite values of opposite signs on the two sides of the pole: rejected, not drawn168 let shifted = Viewport(xMin: -10.03, xMax: 9.97, yMin: -10, yMax: 10, width: 400, height: 400)169 let q = ImplicitPlotter.plot(fn2("1/x - y"), viewport: shifted)170 #expect(q.polylines.count == 2 && q.rejectedCrossings > 100 && q.reliable)171 #expect(q.polylines.allSatisfy { l in l.points.allSatisfy { abs($0.x) > 0.09 && abs($0.x * $0.y - 1) < 0.02 } })172 #expect(q.notices.contains { $0.kind == .rejectedFalseContour })173 }174175 @Test func tangentFalseContoursAreRejected() {176 let p = ImplicitPlotter.plot(fn2("tan(x) - y"), viewport: view)177 // branches between the poles at ±π/2, ±3π/2, ±5π/2178 #expect(p.polylines.count == 7)179 #expect(p.rejectedCrossings > 500)180 let poles = [-2.5, -1.5, -0.5, 0.5, 1.5, 2.5].map { $0 * Double.pi }181 for line in p.polylines {182 // no vertex sits on a pole line unless the curve itself is there (|y| large), and no segment crosses one183 for (a, b) in zip(line.points, line.points.dropFirst()) {184 #expect(!poles.contains { (a.x - $0) * (b.x - $0) < 0 })185 }186 // every vertex satisfies the equation to within a pixel of displacement187 #expect(line.points.allSatisfy { abs(tan($0.x) - $0.y) <= 0.06 * (1 + $0.y * $0.y) })188 // one branch is an increasing function of x189 let sorted = line.points.sorted { $0.x < $1.x }190 #expect(zip(sorted, sorted.dropFirst()).allSatisfy { $1.y >= $0.y - 0.06 })191 }192 }193194 @Test func jumpFalseContoursAreRejected() {195 let p = ImplicitPlotter.plot(fn2("floor(x) - y"), viewport: view)196 #expect(p.polylines.count == 20 && p.rejectedCrossings > 100)197 for line in p.polylines {198 // each piece is one horizontal tread; there are no risers199 let ys = line.points.map(\.y)200 #expect(ys.max()! - ys.min()! < 1e-9)201 #expect(line.points.map(\.x).max()! - line.points.map(\.x).min()! <= 1.0001)202 }203 }204205 @Test func intersectingLinesAndSaddles() {206 let p = ImplicitPlotter.plot(fn2("sin(x) - cos(y)"), viewport: view)207 #expect(p.reliable && p.rejectedCrossings == 0 && p.pointCount > 1500)208 // sin x = cos y ⇔ x ± y = π/2 + 2kπ209 #expect(p.polylines.allSatisfy { l in l.points.allSatisfy { q in210 func off(_ v: Double) -> Double { let r = (v - .pi / 2).truncatingRemainder(dividingBy: 2 * .pi); return min(abs(r), 2 * .pi - abs(r)) }211 return min(off(q.x + q.y), off(q.x - q.y)) < 0.02212 } })213 }214215 @Test func ellipticCurveAndEmptySet() {216 let p = ImplicitPlotter.plot(fn2("y^2 - (x^3 - x)"), viewport: Viewport(xMin: -3, xMax: 3, yMin: -3, yMax: 3, width: 400, height: 400))217 #expect(p.polylines.count == 2 && p.polylines.filter(\.isClosed).count == 1 && p.reliable)218 let empty = ImplicitPlotter.plot(fn2("x^2 + y^2 + 1"), viewport: view)219 #expect(empty.polylines.isEmpty && empty.reliable)220 let almost = ImplicitPlotter.plot(fn2("x^2 + y^2 + 0.001"), viewport: view)221 #expect(almost.polylines.isEmpty && almost.reliable)222 }223224 @Test func honestyNotices() {225 // zero reached without a sign change: nothing can be traced, and the plot says so226 let squared = ImplicitPlotter.plot(fn2("(x - y)^2"), viewport: view)227 #expect(squared.polylines.isEmpty && !squared.reliable && !squared.reasons.isEmpty)228 #expect(squared.notices.contains { $0.kind == .unreliable })229 let shifted = ImplicitPlotter.plot(fn2("(x - y - 0.0137)^2"), viewport: view)230 #expect(!shifted.reliable)231 // far too dense for the grid232 let dense = ImplicitPlotter.plot(fn2("sin(40x) - cos(40y)"), viewport: view)233 #expect(!dense.reliable)234 // budget235 var o = ImplicitOptions()236 o.maxEvaluations = 3000237 let cut = ImplicitPlotter.plot(fn2("sin(x) - cos(y)"), viewport: view, options: o)238 #expect(!cut.isComplete && !cut.reliable)239 }240241 @Test func undefinedRegionsEndTheCurve() {242 // sqrt(x) = y is only defined for x >= 0243 let p = ImplicitPlotter.plot(fn2("sqrt(x) - y"), viewport: view)244 #expect(p.polylines.count == 1 && p.reliable)245 #expect(p.polylines[0].points.allSatisfy { $0.x >= 0 && abs($0.x.squareRoot() - $0.y) < 0.03 })246 }247248 @Test func inequalityRegion() throws {249 let item = try PlotParser.parse("x^2 + y^2 <= 25")250 guard case .inequality(_, let boundaries) = item.kind else { Issue.record("not an inequality"); return }251 #expect(boundaries.count == 1 && !boundaries[0].strict)252 let g = try GraphEngine.geometry(for: item, viewport: view)253 #expect(!g.strictBoundary && g.polylines.count == 1 && g.polylines[0].isClosed)254 let fill = try #require(g.fill)255 let area = fill.spans.reduce(0) { $0 + ($1.x1 - $1.x0) * ($1.y1 - $1.y0) }256 #expect(abs(area - 25 * .pi) < 0.6)257 #expect(fill.spans.allSatisfy { s in258 let x = abs(s.x0) < abs(s.x1) ? s.x0 : s.x1, y = abs(s.y0) < abs(s.y1) ? s.y0 : s.y1259 return x * x + y * y <= 25.5260 })261 let strict = try GraphEngine.geometry(for: PlotParser.parse("y > x^2"), viewport: view)262 #expect(strict.strictBoundary && strict.polylines.count == 1)263 let s = try #require(strict.fill)264 #expect(s.spans.allSatisfy { 0.5 * ($0.y0 + $0.y1) > min($0.x0 * $0.x0, $0.x1 * $0.x1) - 0.5 })265 let strip = try PlotParser.parse("1 < x < 2")266 guard case .inequality(_, let two) = strip.kind else { Issue.record("not an inequality"); return }267 #expect(two.count == 2 && two.allSatisfy(\.strict))268 let sg = try GraphEngine.geometry(for: strip, viewport: view)269 let stripArea = try #require(sg.fill).spans.reduce(0) { $0 + ($1.x1 - $1.x0) * ($1.y1 - $1.y0) }270 #expect(abs(stripArea - 20) < 1.1)271 }272}273