GIS systems commonly store data as a sequence of vectors, such that a
road curve may be represented as a sequence of straight lines which
'approximates' the curve. Mathematical methods are commonly used to
approximate curves, yet these are apparently not widely used in the
GIS community, despite the explosion in digital data.

A good reason for compression of GIS data may be for a vehicle
navigation device, where there is limited storage space for road data
and polygons.

Given a curve can be represented by just two points and a radius, or a
radius and an angle, why is a road not stored in this way for GIS
databases, as opposed to perhaps storing 20 points to approximate the
curve via straight lines)- and then still not doing it was well as
other methods. This would best be done by some discrete way of
disecting a curve, perhaps at inflexion points, or via some other way
of determining a curve has changed in radius by a given threshold.
Clearly a maximum radius would be appropriate for representing a
straight line.

Fourier analysis allows for a sequence of coefficients to approximate
a curve, and this can model many twists and turns, with a very low
data overhead. One difficulty in this method is that the calculation
of fourier analysis is harder and more processor intensive than the
first method mentioned.

The question is: Given a limited processor and memory, what is the
best way to store and display 'compressed' GIS road / polygon data.
Comment on the proposed solution of road polylines being a sequence of
radius/angle pairs.

---

Clarification of Question by chrispeaks-ga on 26 Oct 2003 19:04 PST

This question is related to several others I have placed, perhaps you
may wish to consider them if your answere relates to more than one -
IE it may be preferable to answer two or three together by one
researcher, or use any posted answers to one question as a starting
block to others.

Below is the list of my open questions
Detecting velocity via with correction
Accelerometers to detect angular rotation or velocity 
Velocity detection via doppler effect with observer situated ON moving
object!
Compass heading determined with tilt correction algorithm (negative
pitch error)

Hi Chris

      The best way to represent smooth curves, such as roads,
are splines. Definitly superior to Fourier for this case.

See:
http://www.mathworks.com/access/helpdesk/help/toolbox/splines/tutor.shtml

It is a huge topic and recommended search terms are

Splines tutorial
GRASS GIS splines

The second term set shows that splines indeed are used in GIS system:

viz e.g.
New GRASS 5 Applications ... proj: reproject raster map,
nearest,bilinear,cubic interpolation
 method; r.resamp.rst: resampling with regularized splines with tension ... 
www.geog.uni-hannover.de/users/neteler/ itc_irst/grass5/11_spline.html
- 5k - Cached - Similar pages


OpenOSX.com: PRODUCTS: A GRASS GIS Approach: TOC
 ... temporal interpolation; Geostatistics and splines. Graphical
output ... for land management:
 Building the GIS database; ... problems and solutions. Using GRASS with other ... 
openosx.com/grassbook/toc.html - 42k - Cached - Similar pages 


[PDF] OPEN SOURCE GIS: A GRASS GIS APPROACH First Edition
File Format: PDF/Adobe Acrobat - View as HTML
 ... temporal interpolation ( ) 178 7.4.8 Geostatistics and splines
180 ... x OPEN SOURCE GIS
 8. GRAPHICAL OUTPUT AND ... Displaying map layers using the GRASS monitor 183 ... 
mpa.itc.it/grassbook/open_source_gis2002.pdf - Similar pages 


[PDF] Volume modeling of soils using GRASS GIS 3D-Tools
File Format: PDF/Adobe Acrobat - View as HTML
 ... It uses the regularized splines with tension (RST) algorithm
(Mitásová & ... spatially
 and temporally distributed phenomena: New methods and tools for GRASS GIS. ... 
mpa.itc.it/markus/papers/geomaticsWB2_volume.pdf - Similar pages
[ More results from mpa.itc.it ] 


GDP - GRASS Documentation Project
 ... Interpolation by regularized splines with tension - II. ... in
the Snowy Mountains using
 a GIS (online); GRASS 4.0 Tutorial: DTED and DEM Elevation Data Extraction 

grass.itc.it/gdp/special.html - 11k - Cached - Similar pages

etc
............
............
..............

Now, looking at all your open questions, which add up to about $50
I want to volunteer something you did not ask, but perhaps should
have asked. It is about

Google Answers and patentability:

 This comment is based on a course given by an US patent attorney, but 
(as stated in Important Disclaimer at the bottom of the page) it is
not a legal advice.
 Google Answer is a great service, but the bussines model selected
 places certain limitations on interactions. For people working on
 an innovative devices an on-line consulting service (such as elance)
 may be prefferable. There are several reasons for this:
1) Anything discussed here is 'published' and so (within a year) makes
 eventual patent claims invalid.
2) For us, researchers this is 'work for hire'
 and Google Answers has rights to all derivative works. 
3)Anything published here is likely to be considered  'previously
 disclosed' or 'obvious to those skilled in the art' and as such 
 unpatentable.
 GA may be very good tool for that - for showing exisiting patents
 invalid, for one of the above reasons).

On-line consulting services do not have these limitations,
 business is conducted privately and you can ask for a
'non-disclosure agreement', which preserves your rights to an
eventual invention

So - this may be not relevant to your projects, 
and if that's the case I apologise -
 it was just a free add-on to the spline answer.

hedgie
.

---

Clarification of Answer by hedgie-ga on 13 Nov 2003 08:14 PST

I picked GRASS as an example since it's source is published,
I assume many other GIS programs use splines as well but they may
not be willing to describe their algorithms.

Re:
 I was meaning
embedded 16bit processors, not 'full' 32/64 bit processors running a
full operating system,

I am fairly confident that my comment apply to both,
actually even more to 'small' processors. Splines are 
numerically very efficient, in these application faster
then FFT.
 I would actually prefer if you would ask for clarification
before posting rating lower than my average, based on an
answer/question which was not fully clarified.
 Naturally, there is always space for difference of opinion,
 and there are several types of splines, but that splines 
 (probably cubic) 
  are an 'algorithm of choice' here is hardly just an opinion.

re:
(a year on a less visited
site for example)

It has nothing to do with poularity of a site. 
Actually, law probably does nor care how it is published.
There is some grace time interval there - (or used to be)
you would have to
consult a law expert on details. You may post a question for
a lawexpert-ga only re this.

---

Request for Answer Clarification by chrispeaks-ga on 13 Nov 2003 20:17 PST

You didn't comment on my proposed solution as asked, but I assume you
are implying splines are 'way' better that the proposed, so it is not
worth commenting on, and I suspect this may be true, though I have not
fully investigated splines yet.

Your answer clarification on both points was great, and I am now ready
to revise my rating of your answer. I should have asked for
clarification earlier though I am also conscious of not stretching the
friendship with what may be relatively low value questions that should
not involve numerous clarification requests. I suspect there is (now)
no way to modify my rating, so unless you can indicate how, I
appologise for not A) Phrasing my question specifically enough and B)
Failing to request clarification :-) It may not count to your average
rating (which I see is near on perfect), but I will award you a *****
5-Star posthumous question rating award all the same. I figure you
can't have an average overall rating of 100% or you would have to be
God, and I see you have managed to find him in here already (though I
note he is not a paid researcher, so his rating value is unfortunately
undefined!). All the best and thanks for some great answers anyway :-)

---

Clarification of Answer by hedgie-ga on 14 Nov 2003 05:00 PST

Hmmm,
      May be God will take the posthumous rating into account when my
time comes.And only He could change it. Admitedly, after the
"..I might not remember u when the film clicks ..."
http://answers.google.com/answers/threadview?id=261933
I have lost any hope about reward on this Earth,
beyond list price and eventual tips :-)

good luck

Good answer, Grass seems good, though I suspect it is more a high end
processor application, a little above the 'limited' processor
mentioned. This was perhaps unclear on my part, as I was meaning
embedded 16bit processors, not 'full' 32/64 bit processors running a
full operating system, for which there would be many ways to represent
GIS data, such as Grass. No comment on the 'proposed' solution, though
I suspect my unclear use of 'limited' caused you to consider splines
as the best solution by far, though they seem advanced for more
limited processors to deal with (Just as they would struggle with
Fourier).

Your comments on patents are valid and appreciated, and a timely
reminder. I query your comment 'within a year' - are you suggesting
published means published for long enough to invalidate novel claims,
IE most Patents allow 'breifly' or recently listed material without
invalidating it, but if it is up long enough (a year on a less visited
site for example) it will knock out the claims? Never the less your
caution is valued.