Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#2366 closed defect (fixed)

mapserver error in handling colinear points

Reported by: tbonfort Owned by: tbonfort
Priority: normal Milestone:
Component: MapServer C Library Version: unspecified
Severity: normal Keywords:
Cc: tbonfort, sdlime

Description

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 http://www.nabble.com/attachment/13407156/2/mapserv-incomplete.png

this would happen for points pi , pi+1 , pi+2 when pi and pi+2 are identical, and results in discarding the point pi+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++;
 }
}

Change History (16)

comment:1 Changed 12 years ago by 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 p2p0 = s * p1p0 with s>1, i.e. the points are colinear but with p2 not "behind" p1

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?

comment:2 Changed 12 years ago by 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?

comment:3 Changed 12 years ago by 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

comment:4 Changed 12 years ago by tbonfort

yes, identical in gd and agg.

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

comment:5 Changed 12 years ago by 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

comment:6 Changed 12 years ago by 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

comment:7 Changed 12 years ago by 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

comment:8 Changed 12 years ago by sdlime

Owner: changed from sdlime to tbonfort

comment:9 Changed 12 years ago by tbonfort

Resolution: fixed
Status: newclosed

fixed in r6973

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

comment:10 Changed 12 years ago by 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

comment:11 Changed 12 years ago by 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

comment:12 Changed 12 years ago by 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

comment:13 Changed 12 years ago by 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

comment:14 Changed 12 years ago by tbonfort

Cc: sdlime added; jcarrasco@… removed

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

comment:15 Changed 12 years ago by sdlime

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

Steve

comment:16 Changed 12 years ago by jacarma

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

Note: See TracTickets for help on using tickets.