mapserver error in handling colinear points

[tbonfort]

as pointed out by javier in mapserver-users, there's a bug in the handling of colinear points in line and polygon shapes, when the intent is to draw a line segments "outside" of the line string, like

this would happen for points p_i , p_i+1 , p_i+2 when p_i and p_i+2 are identical, and results in discarding the point p_i+1 , as can be seen in the provided screenshot where the mapserver generated linestring (in green) is missing two line segments.

the code in question is in mapprimitive.c and mapagg.cpp, in the msTransformShapeToPixel and msTransformShapeAGG functions:

if((shape->line[i].point[k-1].x != shape->line[i].point[k].x) || (shape->line[i].point[k-1].y != shape->line[i].point[k].y)) {
 if(((shape->line[i].point[k-2].y - shape->line[i].point[k-1].y)*(shape->line[i].point[k-1].x - shape->line[i].point[k].x)) == ((shape->line[i].point[k-2].x - shape->line[i].point[k-1].x)*(shape->line[i].point[k-1].y - shape->line[i].point[k].y))) {	    
  shape->line[i].point[k-1].x = shape->line[i].point[k].x;
  shape->line[i].point[k-1].y = shape->line[i].point[k].y;	
 } else {
  k++;
 }
}

[tbonfort]

proposed fix: replace the second if test with

if((s= ((shape->line[i].point[j].x-shape->line[i].point[k-2].x)/
       (shape->line[i].point[k-1].x-shape->line[i].point[k-2].x))
   )>1 &&
   (shape->line[i].point[j].y-shape->line[i].point[k-2].y) ==
   s*(shape->line[i].point[k-1].y-shape->line[i].point[k-2].y))

which basically tests if p₂p₀ = s * p₁p₀ with s>1, i.e. the points are colinear but with p₂ not "behind" p₁

compared to the original implementation, there's one assignment more, and one multiplication replaced by a division.

Steve, any comments on this or can I commit?

[tbonfort]

arf... I'll have to go back to the drawing board again to account for division by 0 errors.

what is the use of testing for colinearity? only for performance reasons or is there something else?

[sdlime]

The original code in mapprimitive.c removed duplicate and collinear points for performance reasons (after conversion from map to image coordinates)- that's very old code. I need to download the shapefile and try it. Is the rendering identical with GD and AGG?

Steve

[tbonfort]

yes, identical in gd and agg.

I tracked it down to that particular test on the data javier attached

[sdlime]

I went back and read the thread, should have done that before replying. I'm surprised this hasn't turned up before. I suppose we should consider whether or not removing colinear points is worth the effort.

Steve

[tbonfort]

well just checking for duplicate points and removing the check for colinearity isn't much work. a quick and dirty benchmarking showed a tiny improvement with that test removed on a layer with a huge number of points. you can assigne that bug to me and I'll make the changes if you want.

tb

[sdlime]

Is it me or is there something weird about the shapefile Javier posted to MapServer users. I just ran it through a shapefile dumper and was surprised to see only 1 shape with only 1 part. I assume that's because the route doubles back on itself when it departs from the main route (self-intersecting?). That's why we haven't seen this before.

I suppose removing the test is the easiest fix if were not getting much (or any) benefit. I wonder if polygons are any different.

If you wouldn't mind taking that would be terrific.

Steve

[tbonfort]

fixed in r6973

steve, yes the shapefile has only one linestring and does seem rather strange. it has some points p_i , p_i+1 , p_i+2 with p_i == p_i+2

[sdlime]

What do you think about backporting to 5.0.1? It's a small change but it impacts all drawing operations so perhaps best to wait.

Steve

[tbonfort]

Steve, I'd at least wait to see if there aren't any side effects to the fix.

Was also wondering if we couldn't remove the checks for duplicate points too. They shouldn't happen very often, and I don't think they'd mess things up on the rendering.

thomas

[sdlime]

Was wondering the same thing as I looked at the change set. I think the duplicate points happen more often than we think especially when you draw relatively detailed features for large areas. Still, it's another loop through the vertices that could be avoided.

Steve

[tbonfort]

Steve, I'll remove that check from the AGG version, as in that case we're using floating point image coordinates and duplicate image points would only happen if there are duplicate points in the dataset. I'll leave the check for gd though as there's rounding going on.

thomas

[tbonfort]

Am I missing something or is there a nasty bug when treating point data: we never transform the first point in the datasource (for loop with j starting at 1 and not 0). Funny that never came up before.

removing javier from the cc to stop spamming him

[sdlime]

Points aren't run through that function. They are transformed in the draw point and draw functions in mapdraw.c.

Steve

[jacarma]

Thank you four your quick response. We have compiled and It works fine now.