SPB Git

Repository Public MIT

CurveAndImplicitTests.swift 15.5 KB 273 lines swift

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
Files main
Menu

Theme