gdalgorithms-list

RE: [Algorithms] Modifying the min and max altitude in a heightma p

[Robert D. <RD...@ac...>]

He could however optimise the occasions when he does the full rescan, by
checking to see if the value you are replacing was the maximum value, in
which case it is _possible_ but by no means certain that your max value has
decreased.

Or even, when tracking the maximum value, keep a count of how many match the
maximum (after all you will have to scan at the outset, so can get the
initial count there) and then if you increase the max, it becomes 1 (ie just
the new entry) and if you replace an entry with the current max height, with
a lower value, you can decrement the count.  If the count of max height
entries reaches zero, then do a rescan.  Oh, and make sure if you replace an
entry with a new one which matches the max value that you increment the
count too.

Still doesn't solve the basic problem that you have to do a rescan
occasionally, but stops you doing it when you really don't need to.

Rob

-----Original Message-----
From: Jamie Fowlston [mailto:j.f...@re...]
Sent: 01 August 2000 11:35
To: gda...@li...
Subject: Re: [Algorithms] Modifying the min and max altitude in a
heightmap


Unless you maintain a list of heixels sorted by height, I'm pretty sure you
can't do what you want. Sorry.

Jamie


Sam McGrath wrote:

> This may have a simple solution, but I haven't thought of one yet...
>
> I have a heightmap of altitude values.  The heightmap is subject to
> modification during the course of my program.  When I load the heightmap I
> compute the maximum and minimum values (altitudes).  During the program,
if
> a value in heightmap that is modified goes beyond the maximum altitude, I
> assign that value to the maximum altitude (and similarly for the minimum
> altitude).
>
> However, I also want to be able to tell if the maximum value has _shrunk_
> (or if this minimum value has increased).  So far I can't think of a
simple
> way to do this other than rescanning the whole heightmap whenever a value
is
> modified, and clearly this is not a practical solution.
>
> Hopefully there's a nice simple method that I'm blind to, so please
> enlighten me if you can.  (-:
>
> -Sam
> ______________________
> Sam McGrath
> sa...@dn...
> http://www.dnai.com/~sammy
> ICQ 5151160
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Modifying the min and max altitude in a heightmap

[Jamie F. <j.f...@re...>]

True. I tend to think of worst cases :)

Jamie


Robert Dibley wrote:

> He could however optimise the occasions when he does the full rescan, by
> checking to see if the value you are replacing was the maximum value, in
> which case it is _possible_ but by no means certain that your max value has
> decreased.
>
> Or even, when tracking the maximum value, keep a count of how many match the
> maximum (after all you will have to scan at the outset, so can get the
> initial count there) and then if you increase the max, it becomes 1 (ie just
> the new entry) and if you replace an entry with the current max height, with
> a lower value, you can decrement the count.  If the count of max height
> entries reaches zero, then do a rescan.  Oh, and make sure if you replace an
> entry with a new one which matches the max value that you increment the
> count too.
>
> Still doesn't solve the basic problem that you have to do a rescan
> occasionally, but stops you doing it when you really don't need to.
>
> Rob
>
> -----Original Message-----
> From: Jamie Fowlston [mailto:j.f...@re...]
> Sent: 01 August 2000 11:35
> To: gda...@li...
> Subject: Re: [Algorithms] Modifying the min and max altitude in a
> heightmap
>
> Unless you maintain a list of heixels sorted by height, I'm pretty sure you
> can't do what you want. Sorry.
>
> Jamie
>
> Sam McGrath wrote:
>
> > This may have a simple solution, but I haven't thought of one yet...
> >
> > I have a heightmap of altitude values.  The heightmap is subject to
> > modification during the course of my program.  When I load the heightmap I
> > compute the maximum and minimum values (altitudes).  During the program,
> if
> > a value in heightmap that is modified goes beyond the maximum altitude, I
> > assign that value to the maximum altitude (and similarly for the minimum
> > altitude).
> >
> > However, I also want to be able to tell if the maximum value has _shrunk_
> > (or if this minimum value has increased).  So far I can't think of a
> simple
> > way to do this other than rescanning the whole heightmap whenever a value
> is
> > modified, and clearly this is not a practical solution.
> >
> > Hopefully there's a nice simple method that I'm blind to, so please
> > enlighten me if you can.  (-:
> >
> > -Sam
> > ______________________
> > Sam McGrath
> > sa...@dn...
> > http://www.dnai.com/~sammy
> > ICQ 5151160
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Modifying the min and max altitude in a heightmap

[Allan B. <A.B...@Re...>]

Why not have a lower resolution height map that simply contains the values
of the max and min height 'hiexels' in that particular cell?

That way you can more easily reject a large (depending of course on your
chosen resolution) number of 'heixels'.

You'll still have to do a complete scan of your low res map but it will be
faster than goin through the individual 'hiexel' map.


Al.

----- Original Message -----
From: "Robert Dibley" <RD...@ac...>
To: <gda...@li...>
Sent: Tuesday, August 01, 2000 12:00 PM
Subject: RE: [Algorithms] Modifying the min and max altitude in a heightmap


> He could however optimise the occasions when he does the full rescan, by
> checking to see if the value you are replacing was the maximum value, in
> which case it is _possible_ but by no means certain that your max value
has
> decreased.
>
> Or even, when tracking the maximum value, keep a count of how many match
the
> maximum (after all you will have to scan at the outset, so can get the
> initial count there) and then if you increase the max, it becomes 1 (ie
just
> the new entry) and if you replace an entry with the current max height,
with
> a lower value, you can decrement the count.  If the count of max height
> entries reaches zero, then do a rescan.  Oh, and make sure if you replace
an
> entry with a new one which matches the max value that you increment the
> count too.
>
> Still doesn't solve the basic problem that you have to do a rescan
> occasionally, but stops you doing it when you really don't need to.
>
> Rob
>
> -----Original Message-----
> From: Jamie Fowlston [mailto:j.f...@re...]
> Sent: 01 August 2000 11:35
> To: gda...@li...
> Subject: Re: [Algorithms] Modifying the min and max altitude in a
> heightmap
>
>
> Unless you maintain a list of heixels sorted by height, I'm pretty sure
you
> can't do what you want. Sorry.
>
> Jamie
>
>
> Sam McGrath wrote:
>
> > This may have a simple solution, but I haven't thought of one yet...
> >
> > I have a heightmap of altitude values.  The heightmap is subject to
> > modification during the course of my program.  When I load the heightmap
I
> > compute the maximum and minimum values (altitudes).  During the program,
> if
> > a value in heightmap that is modified goes beyond the maximum altitude,
I
> > assign that value to the maximum altitude (and similarly for the minimum
> > altitude).
> >
> > However, I also want to be able to tell if the maximum value has
_shrunk_
> > (or if this minimum value has increased).  So far I can't think of a
> simple
> > way to do this other than rescanning the whole heightmap whenever a
value
> is
> > modified, and clearly this is not a practical solution.
> >
> > Hopefully there's a nice simple method that I'm blind to, so please
> > enlighten me if you can.  (-:
> >
> > -Sam
> > ______________________
> > Sam McGrath
> > sa...@dn...
> > http://www.dnai.com/~sammy
> > ICQ 5151160
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Modifying the min and max altitude in a heightmap

[Thatcher U. <tu...@tu...>]

From: Allan Bentham <A.B...@Re...>
To: <gda...@li...>
Sent: Tuesday, August 01, 2000 7:19 AM
Subject: Re: [Algorithms] Modifying the min and max altitude in a heightmap


> Why not have a lower resolution height map that simply contains the values
> of the max and min height 'hiexels' in that particular cell?
>
> That way you can more easily reject a large (depending of course on your
> chosen resolution) number of 'heixels'.
>
> You'll still have to do a complete scan of your low res map but it will be
> faster than goin through the individual 'hiexel' map.

If you take that idea to its logical extreme (i.e. give the lower-res bitmap
its own even-lower-res min/max map, etc), you end up with a hierarchy of
maps.  The mighty quadtree is an example of such a hierarchy, and it crushes
this problem.  A "linear" quadtree is probably what you want, and probably
not to the full resolution of the original heightfield, to keep the memory
costs down.  Check the list archives and/or the web for copious info.

--
Thatcher Ulrich
http://tulrich.com


> > Sam McGrath wrote:
> >
> > > This may have a simple solution, but I haven't thought of one yet...
> > >
> > > I have a heightmap of altitude values.  The heightmap is subject to
> > > modification during the course of my program.  When I load the
heightmap
> I
> > > compute the maximum and minimum values (altitudes).  During the
program,
> > if
> > > a value in heightmap that is modified goes beyond the maximum
altitude,
> I
> > > assign that value to the maximum altitude (and similarly for the
minimum
> > > altitude).
> > >
> > > However, I also want to be able to tell if the maximum value has
> _shrunk_
> > > (or if this minimum value has increased).  So far I can't think of a
> > simple
> > > way to do this other than rescanning the whole heightmap whenever a
> value
> > is
> > > modified, and clearly this is not a practical solution.
> > >
> > > Hopefully there's a nice simple method that I'm blind to, so please
> > > enlighten me if you can.  (-:

Re: [Algorithms] Modifying the min and max altitude in a heightmap

[Allan B. <a.b...@re...>]

(2nd attempt at posting..)

Why not have a lower resolution height map that represents small grids on
your proper height map (e.g. 1 low res cell maps to say a 4x4 grid on your
full detail map) the cells of your low res height map will contain the
maximum and minimum values of the hiexels in the grid it represents on the
full detail map.

This way you can more easily reject a large (depending of course on your
chosen resolution) numbers of 'heixels'.

You'll still have to do a complete scan of this low res map but I think it
will be faster than going through your full 'hiexel' map.


Al.

----- Original Message -----
From: "Robert Dibley" <RD...@ac...>
To: <gda...@li...>
Sent: Tuesday, August 01, 2000 12:00 PM
Subject: RE: [Algorithms] Modifying the min and max altitude in a heightmap


> He could however optimise the occasions when he does the full rescan, by
> checking to see if the value you are replacing was the maximum value, in
> which case it is _possible_ but by no means certain that your max value
has
> decreased.
>
> Or even, when tracking the maximum value, keep a count of how many match
the
> maximum (after all you will have to scan at the outset, so can get the
> initial count there) and then if you increase the max, it becomes 1 (ie
just
> the new entry) and if you replace an entry with the current max height,
with
> a lower value, you can decrement the count.  If the count of max height
> entries reaches zero, then do a rescan.  Oh, and make sure if you replace
an
> entry with a new one which matches the max value that you increment the
> count too.
>
> Still doesn't solve the basic problem that you have to do a rescan
> occasionally, but stops you doing it when you really don't need to.
>
> Rob
>
> -----Original Message-----
> From: Jamie Fowlston [mailto:j.f...@re...]
> Sent: 01 August 2000 11:35
> To: gda...@li...
> Subject: Re: [Algorithms] Modifying the min and max altitude in a
> heightmap
>
>
> Unless you maintain a list of heixels sorted by height, I'm pretty sure
you
> can't do what you want. Sorry.
>
> Jamie
>
>
> Sam McGrath wrote:
>
> > This may have a simple solution, but I haven't thought of one yet...
> >
> > I have a heightmap of altitude values.  The heightmap is subject to
> > modification during the course of my program.  When I load the heightmap
I
> > compute the maximum and minimum values (altitudes).  During the program,
> if
> > a value in heightmap that is modified goes beyond the maximum altitude,
I
> > assign that value to the maximum altitude (and similarly for the minimum
> > altitude).
> >
> > However, I also want to be able to tell if the maximum value has
_shrunk_
> > (or if this minimum value has increased).  So far I can't think of a
> simple
> > way to do this other than rescanning the whole heightmap whenever a
value
> is
> > modified, and clearly this is not a practical solution.
> >
> > Hopefully there's a nice simple method that I'm blind to, so please
> > enlighten me if you can.  (-:
> >
> > -Sam
> > ______________________
> > Sam McGrath
> > sa...@dn...
> > http://www.dnai.com/~sammy
> > ICQ 5151160
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list