Fwd: [mapserver-dev] Shapefile goes from 1 sec to 90+ sec just adding a labels!

[Paul Ramsey]

If I take out the if(isOuterRing(p, i)) test from
getPolygonCenterOfGravity the speed goes up by a factor of 30 and the
result looks the same. Since getPolygonCenterOfGravity only uses the
biggest ring, and holes are going to be smaller than the biggest ring,
I think this is a reasonable thing to do.

P


---------- Forwarded message ----------
From: Paul Ramsey <pramsey at cleverelephant.ca>
Date: Mon, Jun 15, 2009 at 2:00 PM
Subject: Re: [mapserver-dev] Shapefile goes from 1 sec to 90+ sec just
adding a labels!
To: Stephen Woodbridge <woodbri at swoodbridge.com>


and the relevant stack trace for msPointInPolygon seems to be

msPolygonLabelPoint calls
getPolygonCenterOfGravity calls
isOuterRing calls
msPointInPolygon

and it does so because shapeObj doesn't provide any guarantees about
ring order, so ring order must always be checked.

Also, because the test polygons are both huge (number of vertices)
*and* have lots of parts, this loop in getPolygonCenterOfGravity is
pretty rough:


 for(i=0; i<p->numlines; i++) {
   if(isOuterRing(p, i)) {}
 }

It's actually O(N^2) against the number of rings, since isOuterRing
itself runs through each ring (less one). So the high number of rings
in this test data is really exercising this.

pramsey=# select name,nrings(the_geom) from world order by nrings desc;
                    name                     | nrings
----------------------------------------------+--------
 Canada                                       |  18376
 Finland                                      |   8656
 United States                                |   7978
 Norway                                       |   7404
 Greenland                                    |   7091
 Sweden                                       |   5464
 Chile                                        |   5148
 Indonesia                                    |   4267
 Russia                                       |   3991
 Australia                                    |   3320
 China                                        |   2161
 Philippines                                  |   1662
 Cuba                                         |   1557
 Japan                                        |   1515
 Brazil                                       |   1465
 South Korea                                  |   1332
 Burma                                        |   1166
 United Kingdom                               |   1132
 The Bahamas                                  |   1111
 Mexico                                       |   1072
 Iceland                                      |   1018

That's right: blame Canada.

P.

On Mon, Jun 15, 2009 at 1:06 PM, Paul Ramsey<pramsey at cleverelephant.ca> wrote:
> Shark tells me that 83% of cycles are spend in msPointInPolygon.
> PostGIS tells me that these are some pretty damn big polygons:
>
> pramsey=# select npoints(the_geom) from world order by npoints desc;
>
>  npoints
> ---------
>  586416
>  265758
>  262693
>  201410
>  165279
>  164432
>  135854
>  117943
>   81531
>   70580
>   66749
>   62417
>   53843
>   53641
>   42864
>   41904
>
> Match made in hell.
>
> P
>
> On Mon, Jun 15, 2009 at 12:01 PM, Stephen
> Woodbridge<woodbri at swoodbridge.com> wrote:
>> http://trac.osgeo.org/mapserver/ticket/3053
>>
>> Steve Lime wrote:
>>>
>>> Did this test case materialize anywhere?
>>>
>>> Steve
>>>
>>>>>> On 6/10/2009 at 12
>