Pharo test defects

Geometry-intersections

State
Fixed (image fix)
Defect in
the Pharo image
Tests
3
Fix
image fix 20-Geometry-intersections.st
Upstream repository
pharo-contributions/Geometry

Record

The Geometry package (GEllipse, GArc) had no ellipse-ellipse intersection: GEllipse>>intersectionsWithEllipse: was a stub that called shouldBeImplemented. Circles inherit it, and GArc/GElement>>intersectionsWithArc: use a circle for the arc, so all three tests hit the stub. The three tests were marked expectedFailure with the comment that the ellipse-ellipse intersection was missing. The fix implements GEllipse>>intersectionsWithEllipse: for any two ellipses, circles included, in any orientation, including tangent boundaries. It writes the receiver as P(t)=c+cos t u+sin t v, maps the argument ellipse to the unit circle, and finds the zeros of g(t)=|Q(t)|^2-1 by 720 samples, bisection for sign changes, and a ternary search for dips that touch zero (tangent cases; both test cases are tangent at (1,3)). Results closer than 1e-7*scale are merged; identical ellipses answer an empty collection. The three tests lose the expectedFailure mark and keep their assertions unchanged. I also checked extra cases on both VMs: two circles crossing at (3,+-4), an external tangent, disjoint and nested circles (empty), and two rotated and unrotated ellipses (4 points, each checked on both ellipses).

Test Defect in State Cause
GArcTest>>testIntersectionsWithArc image-code repaired GEllipse>>intersectionsWithEllipse: was a shouldBeImplemented stub; GCircle inherits it
GArcTest>>testIntersectionsWithEllipse image-code repaired same stub, reached through GArc>>intersectionsWith: and GElement>>intersectionsWithArc:
GEllipseTest>>testIntersectionsWithArc image-code repaired same stub, reached through GEllipse>>intersectionsWith: and GElement>>intersectionsWithArc:

Regression check: Whole classes run with the fix and on the base image, on both VMs (ours JIT, Cog arm64): GArcTest 14 PASS + 2 ERROR before, 16 PASS after. GEllipseTest 22 PASS + 1 ERROR before, 23 PASS after. GCircleTest 11 PASS before and after. GElementTest does not exist (MISSING-CLASS). Same counts on both VMs. I ran only these classes, not the other Geometry test classes; the only existing method I replaced was the stub.

Upstream note: Title: Geometry: implement GEllipse>>intersectionsWithEllipse: (ellipse-ellipse intersection). Project: pharo-graphics/Geometry (the package is loaded in the Pharo 14 image). Description: GEllipse>>intersectionsWithEllipse: only called shouldBeImplemented, so GCircle and GArc intersections with ellipses/arcs failed, and GArcTest>>testIntersectionsWithArc, GArcTest>>testIntersectionsWithEllipse and GEllipseTest>>testIntersectionsWithArc were marked expectedFailure. The method now finds the real zeros of the trigonometric function g(t)=|Q(t)|^2-1 (the receiver in the coordinates where the argument is the unit circle) with sampling, bisection and a search for tangent dips, and the three tests lose their expectedFailure pragma. Not opened as a pull request; the owner must review it first.

Results

Last full sweeps of 2026-11-17: iospharo (sweep14-new14) and stock Cog with the Cog changes (sweepcogp14-new10), with all image fixes. "Before" is the state of the test before the repairs. The Stock Cog column has a value only where the record measured stock Cog: "PASS 3 of 3 (repair run)" is the check of each repair on stock Cog v12.0.6 with the fix entry; "-" is not measured separately.

TestBeforeStateiospharo VMPatched CogStock Cog
GArcTest>>testIntersectionsWithArcXFAILrepairedPASSPASSPASS 3 of 3 (repair run)
GArcTest>>testIntersectionsWithEllipseXFAILrepairedPASSPASSPASS 3 of 3 (repair run)
GEllipseTest>>testIntersectionsWithArcXFAILrepairedPASSPASSPASS 3 of 3 (repair run)

Test

Run the tests in a Pharo 14 image (build 791). Before the fix they skip, fail or carry the expected-failure mark.

"Run in a Playground of a Pharo 14 image (Do it and print each line)."
((GArcTest selector: #testIntersectionsWithArc) run) printString.
((GArcTest selector: #testIntersectionsWithEllipse) run) printString.
((GEllipseTest selector: #testIntersectionsWithArc) run) printString.

Source of the tests before the fix

GArcTest>>testIntersectionsWithArc before the fix (Pharo 14 build 791)
testIntersectionsWithArc
	"Because we need the intersection between two ellipse to do that. Until we have that, we declare the test as expected failure"
	<expectedFailure>
	| arc2 |
	arc2 := GArc center: 1 , -1 origin: 5 , -1 direction: 5 , 0.
	arc := GArc center: 1 , 0 origin: 4 , 0 direction: -1 , 2.
	self assert: (arc intersectionsWith: arc2) isEmpty.


	arc2 := GArc center: 1 , -1 origin: 5 , -1 direction: 0 , 2.
	self assert: (arc intersectionsWith: arc2) hasCloseElementsTo: {(1 , 3)}.
	self assertCollection: (arc intersectionsWith: arc2) hasSameElements: (arc intersectionsWithArc: arc2)
GArcTest>>testIntersectionsWithEllipse before the fix (Pharo 14 build 791)
testIntersectionsWithEllipse
	"Because we need the intersection between two ellipse to do that. Until we have that, we declare the test as expected failure"
	<expectedFailure>
	| ellipse |
	ellipse := GEllipse center: -4 , 3 vertex: 1 , 3 coVertex: -4 , 7.
	arc := GArc center: 1 , 0 origin: 4 , 0 direction: 3 , 2.
	self assert: (arc intersectionsWith: ellipse) isEmpty.

	arc := GArc center: 1 , 0 origin: 4 , 0 direction: -1 , 2.
	self assert: (arc intersectionsWith: ellipse) hasCloseElementsTo: {(1 , 3)}.
	self assertCollection: (arc intersectionsWith: ellipse) hasSameElements: (arc intersectionsWithEllipse: ellipse)
GEllipseTest>>testIntersectionsWithArc before the fix (Pharo 14 build 791)
testIntersectionsWithArc
	"Because we need the intersection between two ellipse to do that. Until we have that, we declare the test as expected failure"
	<expectedFailure>
	| arc |
	ellipse := GEllipse center: -4 , 3 vertex: 1 , 3 coVertex: -4 , 7.
	arc := GArc center: 1 , 0 origin: 4 , 0 direction: 3 , 2.
	self assert: (ellipse intersectionsWith: arc) isEmpty.

	arc := GArc center: 1 , 0 origin: 4 , 0 direction: -1 , 2.
	self assert: (ellipse intersectionsWith: arc) hasCloseElementsTo: {(1 , 3)}.
	self assertCollection: (ellipse intersectionsWith: arc) hasSameElements: (ellipse intersectionsWithArc: arc)

Fix

How to apply an entries file: file in 00-header.st and the entries file as one chunk (the iospharo script scripts/gen-image-fixes.py makes that chunk). Each entry checks for the defect first and prints FIXED, ADDED or SKIP. Download 00-header.st.

20-Geometry-intersections.st (download)
fix value: #GEllipse value: #intersectionsWithEllipse: value: [ :src | src includesSubstring: 'shouldBeImplemented' ] value: 'intersectionsWithEllipse: aGEllipse
	"Answer the points where the boundary of the receiver and the boundary of aGEllipse meet. Works for any two ellipses (also circles), whatever their orientation, and also when the boundaries only touch. The boundaries of two equal ellipses have infinitely many common points; an empty collection is answered for them.

	Method: the receiver is written as P(t) = c + cos(t) u + sin(t) v. Seen from aGEllipse (the map that makes aGEllipse the unit circle), g(t) = |Q(t)|^2 - 1 is zero for a common point. The real zeros of g are found by sampling, bisection for sign changes and a search for the dips where g touches zero without crossing."

	| n h tol cax cay uax uay vax vay cbx cby ubx uby vbx vby det g values roots pointAt bisect result scale |
	cax := center x asFloat. cay := center y asFloat.
	uax := vertex x - center x. uay := vertex y - center y.
	vax := coVertex x - center x. vay := coVertex y - center y.
	cbx := aGEllipse center x asFloat. cby := aGEllipse center y asFloat.
	ubx := aGEllipse vertex x - aGEllipse center x. uby := aGEllipse vertex y - aGEllipse center y.
	vbx := aGEllipse coVertex x - aGEllipse center x. vby := aGEllipse coVertex y - aGEllipse center y.
	det := (ubx * vby - (vbx * uby)) asFloat.
	det = 0 ifTrue: [ ^ {  } ].
	pointAt := [ :t | | c s |
		c := t cos. s := t sin.
		Array with: cax + (c * uax) + (s * vax) with: cay + (c * uay) + (s * vay) ].
	g := [ :t | | p dx dy qx qy |
		p := pointAt value: t.
		dx := (p at: 1) - cbx. dy := (p at: 2) - cby.
		qx := ((vby * dx) - (vbx * dy)) / det.
		qy := ((ubx * dy) - (uby * dx)) / det.
		(qx * qx) + (qy * qy) - 1 ].
	n := 720.
	h := Float twoPi / n.
	tol := 1.0e-9.
	values := (0 to: n - 1) collect: [ :i | g value: i * h ].
	roots := OrderedCollection new.
	bisect := [ :lo :hi | | a b ga m gm |
		a := lo. b := hi. ga := g value: a.
		1 to: 100 do: [ :k |
			m := (a + b) / 2. gm := g value: m.
			(gm = 0 or: [ (gm > 0) = (ga > 0) ]) ifTrue: [ gm = 0 ifTrue: [ a := m. b := m ] ifFalse: [ a := m. ga := gm ] ] ifFalse: [ b := m ] ].
		roots add: (a + b) / 2 ].
	values isEmpty ifFalse: [
		(values allSatisfy: [ :each | each abs < tol ]) ifTrue: [ ^ {  } ] ].
	1 to: n do: [ :i | | gi gn gp t0 sign lo hi mid1 mid2 f1 f2 tmin gmin |
		gi := values at: i.
		gn := values at: i \\ n + 1.
		gp := values at: i - 2 \\ n + 1.
		t0 := (i - 1) * h.
		gi = 0
			ifTrue: [ roots add: t0 ]
			ifFalse: [
				(gi > 0) ~= (gn > 0)
					ifTrue: [ gn = 0 ifFalse: [ bisect value: t0 value: t0 + h ] ]
					ifFalse: [
						(((gp > 0) = (gi > 0)) and: [ gp ~= 0 and: [ gn ~= 0 and: [ gi abs <= gp abs and: [ gi abs <= gn abs ] ] ] ]) ifTrue: [
							sign := gi > 0 ifTrue: [ 1 ] ifFalse: [ -1 ].
							lo := t0 - h. hi := t0 + h.
							1 to: 100 do: [ :k |
								mid1 := lo + ((hi - lo) / 3). mid2 := hi - ((hi - lo) / 3).
								f1 := sign * (g value: mid1). f2 := sign * (g value: mid2).
								f1 < f2 ifTrue: [ hi := mid2 ] ifFalse: [ lo := mid1 ] ].
							tmin := (lo + hi) / 2.
							gmin := sign * (g value: tmin).
							gmin <= 0
								ifTrue: [
									gmin = 0
										ifTrue: [ roots add: tmin ]
										ifFalse: [ bisect value: t0 - h value: tmin. bisect value: tmin value: t0 + h ] ]
								ifFalse: [ gmin < tol ifTrue: [ roots add: tmin ] ] ] ] ] ].
	scale := (uax abs + uay abs + vax abs + vay abs + ubx abs + uby abs + vbx abs + vby abs) max: 1.
	result := OrderedCollection new.
	roots do: [ :t | | p candidate |
		p := pointAt value: t.
		candidate := (p at: 1) , (p at: 2).
		(result anySatisfy: [ :each | (each x - candidate x) abs + (each y - candidate y) abs < (1.0e-7 * scale) ])
			ifFalse: [ result add: candidate ] ].
	^ result asArray'.

fix value: #GArcTest value: #testIntersectionsWithArc value: [ :src | src includesSubstring: '<expectedFailure>' ] value: 'testIntersectionsWithArc
	| arc2 |
	arc2 := GArc center: 1 , -1 origin: 5 , -1 direction: 5 , 0.
	arc := GArc center: 1 , 0 origin: 4 , 0 direction: -1 , 2.
	self assert: (arc intersectionsWith: arc2) isEmpty.


	arc2 := GArc center: 1 , -1 origin: 5 , -1 direction: 0 , 2.
	self assert: (arc intersectionsWith: arc2) hasCloseElementsTo: {(1 , 3)}.
	self assertCollection: (arc intersectionsWith: arc2) hasSameElements: (arc intersectionsWithArc: arc2)'.

fix value: #GArcTest value: #testIntersectionsWithEllipse value: [ :src | src includesSubstring: '<expectedFailure>' ] value: 'testIntersectionsWithEllipse
	| ellipse |
	ellipse := GEllipse center: -4 , 3 vertex: 1 , 3 coVertex: -4 , 7.
	arc := GArc center: 1 , 0 origin: 4 , 0 direction: 3 , 2.
	self assert: (arc intersectionsWith: ellipse) isEmpty.

	arc := GArc center: 1 , 0 origin: 4 , 0 direction: -1 , 2.
	self assert: (arc intersectionsWith: ellipse) hasCloseElementsTo: {(1 , 3)}.
	self assertCollection: (arc intersectionsWith: ellipse) hasSameElements: (arc intersectionsWithEllipse: ellipse)'.

fix value: #GEllipseTest value: #testIntersectionsWithArc value: [ :src | src includesSubstring: '<expectedFailure>' ] value: 'testIntersectionsWithArc
	| arc |
	ellipse := GEllipse center: -4 , 3 vertex: 1 , 3 coVertex: -4 , 7.
	arc := GArc center: 1 , 0 origin: 4 , 0 direction: 3 , 2.
	self assert: (ellipse intersectionsWith: arc) isEmpty.

	arc := GArc center: 1 , 0 origin: 4 , 0 direction: -1 , 2.
	self assert: (ellipse intersectionsWith: arc) hasCloseElementsTo: {(1 , 3)}.
	self assertCollection: (ellipse intersectionsWith: arc) hasSameElements: (ellipse intersectionsWithArc: arc)'.

State of 2026-11-20. Made from the test records of the iospharo project (a second Pharo VM). The fixes are proposals for review.