Spheres, centered at airplane locations, fly around and try to avoid bumping into each other and the underlying terrain. How does a system keep track of these objects? What flight path should be followed by each plane if the system goes down for 5 minutes, 10 minutes, longer?
Ref: Alfred Inselberg seems to be a big researcher in this
area.
Simon Kahan wrote a PhD thesis at the University of
Washington on some related theoretical problems. That thesis
is probably a good source of references.
Some of this is fitting planes to scattered point sets. Some of it is figuring out the inside and the outside of the body.
Ref: papers by Hugues Hoppe and papers by Tony DeRose
What is the equivalent of the traditional 2.5 dimensional Greedy TIN construction in 3 dimensions? Implement this.
Ref: David Dobkin did work on polyhedral decomposition, Mitchell and Suri. Also a paper on Simplification Envelopes from SIGGRAPH 96.
Given a 3-dimensional region, fill it with small "basic" pieces (such as tertrahedron). There may be density constraints requiring, for example, that the region in front of a wing be sampled at 1mm intervals, while 1cm intervals suffice for the top of the wing. How does one satisfy these simultaneously?
Garland and Heckbert provide a great implementation ( Scape) and a thorough discussion of techniques.
Delaunay triangulations deal only with the projection of the sample points into the x-y plane. The height information is ignored. What can be done if height information is used to influence the choice of triangulation?
Ref: Data dependent triangulations for piecewise linear interpolation by Dyn, Levin, and Rippa.
Ref: Garland and Heckbert have a nice list of references for these techniques.
Which gives the "best" approximation for a given amount of space? What is a good measure of "best"? Does the answer change based on the measure? Why does it change?
Ref: Kumler paper.
Does this hold for gridded surfaces? Ref: Agarwal and Suri. I don't understand why their proof is true.
How can one handle insertions and deletions of points from the terrain in a fast and efficient manner?
The general idea is to devise better (more visually realistic), smaller (less memory), faster (fewer triangles drawn, faster algorithms) heirarchies. Exisiting ones are based on TINS ( papers by Enrico Puppo de Berge and Dobrindt (Delaunay triangulations), De Floriani et al., Georgia Tech group (Real-Time, Continuous Level of Detail Rendering of Height Fields), Kropatsch (monkey retinas)).
Particular areas to explore: add satellite images, better refinement methods for RTINs, triangle strips to speed rendering, non-terrain applications (pictures), fractal tricks to add realism at no cost in space, seeding with important points, showing only certain features (eg. ridge-lines).
Given a surface, calculate the set of points whose height is a multiple of 10m.
Ref: Efficient methods for isoline extraction from a digital elevation model based on triangulated irregular networks, van Kreveld and references therein.
What triangles/horizon lines are visible from a given eye point? What if the eye point moves? What information should be stored to make updating the horizon fast?
Ref: Bern, Dobkin, Eppstein, Grossman (for moving points), De Floriani et al., (for fixed).
What is the set of points on a terrain which "drain" into a given river? "Drain" is taken to mean follow the path of steepest descent. Maybe other definitions would be interesting. A nice implementation would have the user select a river segment, or perhaps just a point on a river, and then the watershed for that segement would be shown.
Ref: Yu, van Kreveld, Snoeyink
What is the shortest path between two points on a terrain? How do you calculate this path from (a) an array of height values, (b) a TIN? What if the desire is for a path that stays below a certain elevation? or doesn't involve large variation in elevation? or has a cost associated with slope?
Ref: de Berg and van Kreveld, Hershberger and Snoeyink, Adegeest and Overmars and Snoeyink.
What is the analog of the Voronoi diagram on a terrain? when distance is distance on the surface? when distance incorporates costs for slope? Lots of questions such as where should one place fire observation stations in a forest? avalanche warning stations in the Alps?
Ref: ??
How much material must be removed to cut a road? Calculate the volumetric difference between two terrains. What is the surface area of a given region? Is fractal dimension a useful measure? How does one calculate it? These seem relatively easy.
Draw the New Yorkers view of the world. Or a map of the United States where area of a state reflects population. The shape of the distorted region should resemble the original shape and should border the same regions. Perhaps a method based on triangulations could yield decent results.
Ref: A Combinatorial Approach to Cartograms, H. Edelsbrunner, R. Waupotitsch UI Urbana-Champaign, ACM Geometry Conference, Vancouver BC, 1995.
Given a list of points and labels for these points, draw the labels in such a way that they are "close" the their point and do not overlap. What if we want to label lines (such as rivers and roads)? areas (states,counties,lakes)? Where should we place the labels of these objects?
Ref: Wagner and Wolff
How does one simplify a polyline and still retail the "basic" shape? Douglas/Peuker line simplification!
Refs: McMaster; Buttenfield; Hershberger and Snoeyink.
What if one wants coastal simplification to keep coastal cities on land? Refs: de Berg, van Kreveld, Schirra
What if the user specifies the "important" sections of the line?
At what point in the zooming out process should a collection of points become one? Where should the new point be located?
When should one exaggerate the squiggles in a line in order to convey the information that the road represented by the line is twisty? exaggerate the area to draw attention to a point of interest?
Rivers are often digitized by digitizing their left bank and right bank. Lakes by digitizing their shoreline. How do we extract from this set of polylines the underlying network of rivers and lakes? How do we simplify the left and right bank of a river into a single line representing the river? One solution is to use the medial axis of the river. What algorithms are used to calculate medial axis?
Ref: Chin, Snoeyink, and Wang; McAllister,Kirkpatrick, Snoeyink.
Many map operations involve overlaying two maps depicting two different spatial data sets. This involves calculating intersections of polygons and lines. For example, finding appropriate conditions for wildlife relocation may involve questions of forest type, temperature, and accessibility.
Refs: there are several listed in the NCGIA Course Outline Unit 32 and 34.
INPUT SIDE
One particular area I'm interested in is analyzing arrays of height values to find "important" points and "seeding" a surface approximation algorithm with these points. The idea is to get better representation of certain features (such as ridge lines) than can be obtained by traditional surface approximation methods.
Ref: Jim Little at UBC has some ideas on this as well.
This is known as photogrammetry. The area is large and involves all kinds of object reconstruction from 2d photos.
Ref: JPEG Compression and photogrammetry
Rather than precisely digitizing a boundary that contains a lot of superficial detail (such as a forest/plain boundary), scatter a bunch of points in the general area of the boundary and use the Voronoi diagram of the point set to give some idea of the boundary. Is this reasonable? Are there better methods for speeding up the digitizing of detailed boundaries? Is the Voronoi diagram the correct tool?
Ref: Christopher Gold at LaVal University is the main researcher in this area.
INTERNALS
R-trees, quad-edge, quad-trees, oct-trees, Reactive trees, Binary Space Partions, ...
Refs: Samet is the guru of quad-trees and oct-trees. van Oosterom developed the reactive data structures. Guibas and Stolfi defined the quad-edge data structure.
What are good methods to compress elevation data? Good in terms of reducing size, fast decompression, representations that still allow computation without decompression.
One way to represent a line is as a sequence of compass directions. N,NW,W,W,W,... describes a path which starts at some point, goes 1 meter north, then 1 meter northwest, etc. The path traced by following these directions approximates the desired line. What is the "best" such representation for a given line?
Another possibility is to use run-length encoding to represent areal features.
How do you perform basic calculations from these representations? How do you calculate area? intersection? etc.
Refs: The NCGIA Course outline unit 31 contains references.
Given a region represented by an array of 0's and 1's (a 1 in entry i,j meaning the i,j pixel is in the region) what is a polygonal approximation to this region? How do we transform a polygon to an array of 0's and 1's? These problems seem easy.