[PATCH] Improved polygon scan conversion for imageFilledPolygon()
|Reported by:||brage||Owned by:||sdlime|
|Component:||MapServer C Library||Version:||svn-trunk (development)|
The attached patch is a new implemetation of imageFilledPolygon() for mapgd.c.
With the current mapgd.c it is not really possible to make a polygon without an outline. If no outline is specified, the polygon will have a outline the same color as the fill. This results in loss of detail, and makes small polygons (for instance lakes and islands) look bigger than they should.
The problem is that imageFilledPolygon() uses a midpoint line algorithm, and includes points which are not strictly interior to the polygon. The patch replaces this with an interior extrema algorithm, based on Paul Heckbert's algorithm from from "Graphics Gems".
The attached examples should demonstrate how big difference this makes.
The patch is also eliminates the loop iterating over every point for every scanline, and is generally much faster than the old imageFilledPolygon. It should actually give mapsever appliactions using the gd backend a noticable performance improvement.
For example, the average runtime for shp2img when creating the example maps was
|North Europe coastline||610ms||399ms|
And, at last, Mapserver should be able to render the coastline of Norway correctly!
-- Brage Førland
Change History (17)
comment:1 Changed 9 years ago by
|Summary:||Improved polygon scan conversion for imageFilledPolygon() → [PATCH] Improved polygon scan conversion for imageFilledPolygon()|
comment:2 follow-up: 5 Changed 9 years ago by
|Milestone:||→ 5.4 release|
|Status:||new → assigned|
|Version:||unspecified → svn-trunk (development)|