Linear Mapping Between Two Triangles

Here is unoptimized Swift code for generating the linear transformation between two triangles. It’s extremely easy to miss dealing with some corner cases. I’m pretty sure this is correct. I’ve used it to generate dozens of IFS fractals and have not had an issue. One thing to note is that my C code in ‘Exploring Fractals on the Macintosh’ (see my links page) either isn’t completely right or my recent conversion of that code to Swift wasn’t correct, as I found some issues with it.

func CalcTransform(p11: NSPoint, p12: NSPoint, p13: NSPoint,
	p21: NSPoint, p22: NSPoint, p23: NSPoint) -> NSAffineTransformStruct
{
	var x12, x13, x23: CGFloat
	var y12, y13, y23: CGFloat
	var xp12, xp13, xp23: CGFloat
	var yp12, yp13, yp23: CGFloat
	var m11, m12, m21, m22, tx, ty: CGFloat
	
	x12 = p11.x - p12.x
	x23 = p12.x - p13.x
	x13 = p11.x - p13.x
	y12 = p11.y - p12.y
	y23 = p12.y - p13.y
	y13 = p11.y - p13.y
	
	xp12 = p21.x - p22.x
	xp23 = p22.x - p23.x
	xp13 = p21.x - p23.x
	yp12 = p21.y - p22.y
	yp23 = p22.y - p23.y
	yp13 = p21.y - p23.y
	
	// X TRANSFORM
	// m11 --
	if y12 == 0 && x12 != 0 {
		m11 = xp12  / x12
	} else if y13 == 0 && x13 != 0 {
		m11 = xp13 / x13
	} else if y23 == 0 && x23 != 0 {
		m11 = xp23 / x23
	} else {
		var denom = x12 * y13 - x13 * y12
		
		if (0 != denom) {
			m11 = (xp12 * y13 - xp13 * y12) / denom
		} else {
			denom = x12 * y23 - x23 * y12
			if (0 != denom) {
				m11 = (xp12 * y23 - xp23 * y12) / denom
			} else {
				denom = x13 * y23 - x23 * y13
				if (0 != denom) {
					m11 = (xp13 * y23 - xp23 * y13) / denom
				} else {
					Swift.print("Could not make transform (x)!")
					return NSAffineTransformStruct(
							m11: 1.0, m12: 1.0,
							m21: 1.0, m22: 1.0,
							tX: 0.0, tY: 0.0)
				}
			}
		}
	}
	
	// m12
	if (0 != y12) {
		m12 = (xp12 - m11 * x12) / y12
	} else if (0 != y13) {
		m12 = (xp13 - m11 * x13) / y13
	} else if (0 != y23) {
		m12 = (xp23 - m11 * x23) / y23
	} else {
		m12 = 0.0 // is this right? seems right but not sure
		Swift.print("Setting m12 to 0!")
	}
	
	// tx
	tx = p21.x - m11 * p11.x - m12 * p11.y
	
	// Y TRANSFORM
	
	// m11 --
	if y12 == 0 && x12 != 0 {
		m21 = yp12  / x12
	} else if y13 == 0 && x13 != 0 {
		m21 = yp13 / x13
	} else if y23 == 0 && x23 != 0 {
		m21 = yp23 / x23
	} else {
		var denom = x12 * y23 - x23 * y12
		
		if (0 != denom) {
			m21 = (yp12 * y23 - yp23 * y12) / denom
		} else {
			denom = x13 * y23 - x23 * y13
			if (0 != denom) {
				m21 = (yp13 * y23 - yp23 * y13) / denom
			} else {
				denom = x12 * y13 - x13 * y12
				if (0 != denom) {
					m21 = (yp12 * y13 - yp13 * y12) / denom
				} else {
					Swift.print("Could not make transform (y)!")
					return NSAffineTransformStruct(
							m11: 1.0, m12: 1.0,
							m21: 1.0, m22: 1.0,
							tX: 0.0, tY: 0.0)
				}
			}
		}
	}
	
	// m12
	if (0 != y12) {
		m22 = (yp12 - m21 * x12) / y12
	} else if (0 != y13) {
		m22 = (yp13 - m21 * x13) / y13
	} else if (0 != y23) {
		m22 = (yp23 - m21 * x23) / y23
	} else {
		m22 = 0.0 // is this right? seems right but not sure
		Swift.print("Setting m12 to 0!")
	}
	
	ty = p21.y - m21 * p11.x - m22 * p11.y
	
	
	let ret = NSAffineTransformStruct(m11: m11, m12: m12, 
					m21: m21, m22: m22, 
					tX: tx, tY: ty)
	
	return ret;
}

In the past Apple supplied an API that allowed one to set an NSAffineTransform from an NSAffineTransformStruct but I think it no longer exists (?). If you want to know how to use the resultant from the above, below is an example mapping one point to another.

func transformPoint(xform: NSAffineTransformStruct, point: NSPoint) -> NSPoint {
	var ret = NSPoint()
	ret.x = xform.m11 * point.x + xform.m12 * point.y + xform.tX
	ret.y = xform.m21 * point.x + xform.m22 * point.y + xform.tY
	
	return ret
}

Leave a Reply

Your email address will not be published. Required fields are marked *