Hi,
Sorry for the bad example :
In the illustration, the medium shell does not pass the PiP test,
so it is never considered as a possible candidate.
After many useless tries to find a case where this test did not
work,
I tried to understand why it works.
Finally, that's how I explain it :
if one consider the geometry as valid :
If a hole h is included in 2 shells s1 and s2,
==> s1 and s2 are overlaping in h
==> as the multigeometry is valid ==> s1 (resp s2) shoul be
entirely in a hole of s2 (resp s1)
==> s1 envelope (resp s2 envelope) is included in s2 envelope
(resp s1 envelope)
==> h is in a polygon which in turn is in the hole of another
polygon,
it must be associated to the inner one (the one with the
smallest envelope)
Sorry for the noise, especially if the result was obvious for you,
guys,
it was certainly not for me ;-)
Michaël
About the #2, I think the test currently done in OpenJUMP is wrong
In case where several shell's ebvelope contain hole's envelope, if
shells are
included in each other, the hole is associated to the smallest :
if (shellEnvelope.contains(holeEnvelope)
&&
(minShellEnv == null || minShellEnv.contains(shellEnvelope))
&&
(cga.isPointInRing(testPt,coordList ))) {
minShellEnv = shellEnvelope;
}
I think it will not work in this case :
I'll measure the penalty if the second test is removed
and eventually, I'll try to implement Martin's #2 tip.
Michaël
Le 21/04/2012 06:03, Martin Davis a écrit :
The file I sent is in Ohio, I think. It was sent to me by
Stephen Mather, who I met in Washington DC at FOSS4GNA last
week. It's pretty excessive - not the normal kind of shapefile,
I think. But still, it's nice to optimize the corner cases,
especially if they take 10x longer to run.
I did realize that the use case for GeoTools (in GeoServer at
least) is a bit different to OJ. GeoServer doesn't cache data
in memory, so it's going to be reading data many times, so every
second is precious. And there's no expectation it will fix bad
data - it just has to provide something that mirrors what was
read. OJ on the other hand might be expected to try to fix some
of the bad data, and users might be willing to spend more time
on load to get that functionality.
Anyway, fix #3 is good in any case, and it seems like a good
thing that you added fix #1 too. Fix #2 was a bit more
speculative, and it only applies in very specific circumstances,
so it's probably not as critical. (BTW, the idea was not to
assume to which shell holes were assigned to, but to check if
only one shell could actually contain a given hole, by virtue of
the envelope intersection test).
On 4/20/2012 11:02 AM, Michaël Michaud wrote:
Martin,
Thanks for the file, very impressive (did not guess where it
was - but only searched in Canada).
You convinced me.
We had two previous discussions on the list about preserving
weird shapefile as much as possible,
but none of them was about holes lying out of their shell.
So let's go where geotools already is.
I had a quick look on your suggestion #2, but could not see a
way to improve.
For more than one shell case, we don't know which hole is
associated with which shell before the test
(except if we assume that the description of a shell is
immediately followed by the description of its holes)
Don't know if we should assume this.
For "more than one shell" case, I just changed the order of
tests to do a bit more envelope tests and a bit less PiP tests
but I could not measure the difference on your file.
Michaël
Very thorough investigation, Michael.
The shapefile I was using is here:
http://maps.cmparks.net/geoserver/metroparks/ows?service=WFS&version=1.0.0&request=GetFeature&typeName=metroparks:tpi_1&outputFormat=SHAPE-ZIP
( http://tinyurl.com/c9k26gp )
It is pretty gnarly - over 1M polygons, and has the
following stats for the largest (vertices/holes):
18527 1112
58597 5526
31087 1598
24152 1318
17989 1386
20280 1098
20815 1336
44871 1204
61496 3024
28370 1120
46058 2156
21970 1546
91379 3034
121028 8012
81172 4544
28544 1272
20524 1074
55556 1992
2282758 169278
1166731 94382
241350 14250
142028 5922
139035 5690
33610 1344
83112 3134
38464 1048
GeoTools has had optimization #1 for quite a while, I think,
if that's any reassurance.
On 4/20/2012 6:29 AM, Michaël Michaud wrote:
Hi,
Here are some test cases done with a 200 Mb shapefile
(thanks Jukka)
containing : 221770 polygons
worst case : 287273 pts and 5484 holes
Dataset : Current OJ code / 1st Martin's optimization /
3rd Martin's optimization / 1st+3rd
whole shapefile : 41 s / 24 s / 24 s / 11 s
worst polygon : 4.6 s / 0.16 s / 3.3 s / 0.13 s
==>
1st optimization has a big impact on worst case and a
medium impact on a whole file with mixed cases
3rd optimization has a small impact on worst case and a
medium impact on a whole file with mixed cases
I'll commit the 3rd optimization anyway has it has no side
effect.
For the 1st one, i'll try to check if it may have negative
impact on some shapefile (if I can find or produce such
shapefiles)
------------------------------------------------------------------------------
For Developers, A Lot Can Happen In A Second.
Boundary is the first to Know...and Tell You.
Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
http://p.sf.net/sfu/Boundary-d2dvs2
_______________________________________________
Jump-pilot-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
------------------------------------------------------------------------------
For Developers, A Lot Can Happen In A Second.
Boundary is the first to Know...and Tell You.
Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
http://p.sf.net/sfu/Boundary-d2dvs2
_______________________________________________
Jump-pilot-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
No virus
found in this message.
Checked by AVG - www.avg.com
Version: 2012.0.1913 / Virus Database: 2411/4948 - Release
Date: 04/20/12
------------------------------------------------------------------------------
For Developers, A Lot Can Happen In A Second.
Boundary is the first to Know...and Tell You.
Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
http://p.sf.net/sfu/Boundary-d2dvs2
_______________________________________________
Jump-pilot-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
------------------------------------------------------------------------------
For Developers, A Lot Can Happen In A Second.
Boundary is the first to Know...and Tell You.
Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
http://p.sf.net/sfu/Boundary-d2dvs2
_______________________________________________
Jump-pilot-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
|
