FW: [UMN_MAPSERVER-DEV] specific raster queries

[Erick Ferreira]

>Erick,

>I think we discussed this in IRC before?  Forgive me if I've forgotten
>some of the details we worked out then.

>You write that "msRasterQueryByShape() function in fact queries the
>whole bounding box of the polygon, not the polygon itself."  Looking at
>the code it appears that a full resolution block the size of the
>requested line will be loaded into RAM, and then every single pixel in
>that region will be tested for being inside the polygon using
>msIntersectPointPolygon().

>It seems like this would produce the right results (assuming polygon
>input) but is still very ugly from a performance point of view.

>My suggestion would be to do some specializations in the implementation
>of msRasterQueryByShape() for line geometries at least.  So this would
>involve some gory work in maprasterquery.c.  If you are interested in
>pursuing this angle, I'd be happy to answer questions and commit changes
>after some checking.

>Best regards,



Frank,

I have done some tests by mesuring the time in three points inside msRasterQueryByRectLow(): 
   - in the begining of the scope (A), 
   - just before the comment "Loop over all pixels determining which are in" (B) 
   - and in the end of the scope (C).

I did not come with too many samples but I found that the time spent between A and B was allways comparable (or even greater) to the time spent between B and C.

I kept thinking that even if I specialized the implementation of that function in order to use the line-drawing algorithm, I would still have to keep the code between (A) and (B), which is O(N^2) in terms of memmory allocation and maybe enven in time complexity...and that made me believe that the specialization we've been considering would not represent a significant gain.

The fact is that my search shape is one-dimensional - "give me the points along a path, more specifically, along a line segment" - wchich would make sense to be realized by means of O(N) complexity.

So I thought of some possible implementation of a rasterQueryByPath() function in that basis, but that would _probably_ mean that a specialization in GDAL would be necessary as well.

For now, I'm a regular rasterQueryByShape() user and I will not focus on code optimization in this right moment. But certainly I will, soon.

What do you think of my considerations?
Thank you for your attention.

Best regards,
Erick