sundar@wheaties.ai.mit.edu (Sundar Narasimhan) (03/02/89)
Hi: I have a matrix of numbers (a discrete sampling of an underlying continuous space) that I'd like to produce a contour plot from. I'd like the plot to do subpixel calculations (i.e. I dont want lines Manhattan routed). Does anyone have a reference to algorithms that will do this? (I tried the usual hacks of modifying something like Breshenham's line drawing algorithm and a thresholding algorithm (i.e. you threshold above a certain height and then compute the boundary of the resulting regions for all heights given by the contour quantization step) but they don't quite work). -Sundar (reply to sundar@wheaties.ai.mit.edu -- I'll summarize if there is interest) PS: Note that I DO NOT have equations to describe the surface. If I did, I could probably use macsyma's contour plotting option. (BTW, does anyone know how the algorithm for macsyma's contour plotting works?)
aramini@apollo.COM (Michael Aramini) (03/03/89)
I did my master's thesis on the topic of contour plotting when I was at the Univsity of Illinois in 1981. I don't have a copy of my thesis with me at work, and I don't remember the list of references off the top of my head. The most straightforward algorithm is to consider the region of interest to be tiled by equal sized rectangles, such that the verticies coincide with the positions for the data values in your 2-D array. Lets call each of these little rectangles cells. For each cell you do the following: For a particular level curve height h, determine, which, if any of the 4 edges of a cell are intersected by that level curve. Consider an edge interesected if h is numerically between the known Z values at the endpoints of that edge (corners of the cell). It is easy to show that only 0, 2, or 4 edges or a cell can be intersected by a given level curve. If 0 edges are intersected, do nothing for this cell. If exactly 2 edges are intersected, determine, by reverse linear interpolation, approximatations for the coordinates of the points of intersection between the level curve and each of the two relvant cell edges, and draw a line segment connecting these points. If all 4 edges are intersected, there are a variety of tricks to try to determine which intersection points to connect to which other intersection points. My favorite is to determine the point of intersection between the line segment connecting the top and bottom intersection points with the line segment connecting the left and right intersection points (*don't* actually draw those line segments). Determine an approximation for Z at that intersection point by bilinear interpolation of the Z values at the 4 corners of the cell. Use that appoximate Z value to disambiguate a ridge in one diagonal direction from a valley in another diagonal direction. Back in 1981 I had discussed contour plotting algorithms with the author of the contour plotting code in Macsyma (I think his name is Charles Kearney, I'm not sure of the spelling, his username on the ITS machines back then was CFFK, I believe he works at the Princeton Plasma Physics Lab, of course this was almost 8 years ago, so I don't know if the the contour plotting code currently in Macsyma is still the same). His algorithm is similar to mine except that he tesselates the region in question with right triangles instead of rectangles (basically by adding the southwest to northeast diagonal edges). Since only 0 or 2 edges of a triangle can be intersected by the level curve, this eliminates having to handle the 4 edges intersected case that rectangles can have, although it does so in an arbitrary way; for those cases where the rectangle method has a 4 edges interescted cell, the triangle method will effective arbitrarily connect the left of the rectangle to the top, and the bottom of the rectangle to the right. So this really doesn't solve the problem, it just arbitrarily avoids it. In addition, the triangle method is more expensive (more intersection point to compute, more line segments to draw). -Michael