FW: [UMN_MAPSERVER-DEV] specific raster queries
erick.ferreira at WINGSTELECOM.COM.BR
Tue Apr 11 14:16:50 EDT 2006
>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
>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.
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.
More information about the mapserver-dev