I'm doing a check for intersection and it is going extremely slowly, and I was wondering whether anyone might have some advice for how I could speed it up.
I have a process that iterates over 700,000 points and determines what polygons they intersect in a group of polygons. I'm already using an STRtree to reduce the number of polygons I'm actually calling intersects on (typically for each point it is only 1 or 2 polygons). Are there any tricks for point-in-poly lookups? I'm currently checking whether the time (average 200 ms/intersection) is actually evenly spread, or if I have a couple polygons in particular that are taking all the time (it is possible I have one polygon with a million points mixed in there or something). Thanks, Jeff _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Try using SimplePointInAreaLocater rather than intersects. intersects
computes a lot of extra information which is not relevant for simple PiP tests. And yes, this is an obvious optimization which should be made to the code base. Hopefully it will happen soon... Jeff Adams wrote: > I'm doing a check for intersection and it is going extremely slowly, > and I was wondering whether anyone might have some advice for how I > could speed it up. > > I have a process that iterates over 700,000 points and determines what > polygons they intersect in a group of polygons. > > I'm already using an STRtree to reduce the number of polygons I'm > actually calling intersects on (typically for each point it is only 1 > or 2 polygons). Are there any tricks for point-in-poly lookups? > > I'm currently checking whether the time (average 200 ms/intersection) > is actually evenly spread, or if I have a couple polygons in > particular that are taking all the time (it is possible I have one > polygon with a million points mixed in there or something). > > > Thanks, > Jeff > ------------------------------------------------------------------------ > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Thanks, I'm trying that now.
It turns out the time is definitely not evenly spread, I have a couple large polygons (~1800 points) where the intersection call takes as much as a second or more, and the majority of calls take under 50 ms. Does it matter which way I do the intersection? Would either of these be faster: bigGeom.intersects(smallGeom) vs smallGeom.intersects(bigGeom) I'm still curious because I have a small subset of cases where the "search point" is not a point but a small polygon. Thanks again, Jeff On Tue, Oct 6, 2009 at 2:36 PM, Martin Davis <[hidden email]> wrote: Try using SimplePointInAreaLocater rather than intersects. intersects computes a lot of extra information which is not relevant for simple PiP tests. _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
The order of arguments in the intersects call doesn't make any
difference to performance. You should be better off using SimplePointInAreaLocater for every Pt-in-poly call, no matter what the size of the polygon. Obviously you'll have to use intersects for the polygon-polygon case (or possibly covers(), if you are really wanting to determine proper intersection (ie containment)) Jeff Adams wrote: > Thanks, I'm trying that now. > > It turns out the time is definitely not evenly spread, I have a couple > large polygons (~1800 points) where the intersection call takes as > much as a second or more, and the majority of calls take under 50 ms. > > Does it matter which way I do the intersection? Would either of these > be faster: > > bigGeom.intersects(smallGeom) vs > smallGeom.intersects(bigGeom) > > I'm still curious because I have a small subset of cases where the > "search point" is not a point but a small polygon. > > Thanks again, > Jeff > > On Tue, Oct 6, 2009 at 2:36 PM, Martin Davis <[hidden email] > <mailto:[hidden email]>> wrote: > > Try using SimplePointInAreaLocater rather than intersects. > intersects computes a lot of extra information which is not > relevant for simple PiP tests. > > And yes, this is an obvious optimization which should be made to > the code base. Hopefully it will happen soon... > > Jeff Adams wrote: > > I'm doing a check for intersection and it is going extremely > slowly, and I was wondering whether anyone might have some > advice for how I could speed it up. > > I have a process that iterates over 700,000 points and > determines what polygons they intersect in a group of polygons. > > I'm already using an STRtree to reduce the number of polygons > I'm actually calling intersects on (typically for each point > it is only 1 or 2 polygons). Are there any tricks for > point-in-poly lookups? > > I'm currently checking whether the time (average 200 > ms/intersection) is actually evenly spread, or if I have a > couple polygons in particular that are taking all the time (it > is possible I have one polygon with a million points mixed in > there or something). > > > Thanks, > Jeff > ------------------------------------------------------------------------ > > > ------------------------------------------------------------------------ > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
So, using SimplePointInAreaLocater for my points improved performance by a factor of 100!
This is the best mailing list ever ;-). Thanks again! The polygon-polygon case occurs rarely enough that it isn't a problem, I just happen to always know one will be small and one will be huge so I figured it was easy enough to order the arguments if it would make a difference. On Tue, Oct 6, 2009 at 3:30 PM, Martin Davis <[hidden email]> wrote: The order of arguments in the intersects call doesn't make any difference to performance. -- Jeff Adams Avencia, Inc. 215-701-7717 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Glad that worked out for you, Jeff.
Jeff Adams wrote: > So, using SimplePointInAreaLocater for my points improved performance > by a factor of 100! > > This is the best mailing list ever ;-). Thanks again! > > The polygon-polygon case occurs rarely enough that it isn't a problem, > I just happen to always know one will be small and one will be huge so > I figured it was easy enough to order the arguments if it would make a > difference. > > > On Tue, Oct 6, 2009 at 3:30 PM, Martin Davis <[hidden email] > <mailto:[hidden email]>> wrote: > > The order of arguments in the intersects call doesn't make any > difference to performance. > > You should be better off using SimplePointInAreaLocater for every > Pt-in-poly call, no matter what the size of the polygon. > > Obviously you'll have to use intersects for the polygon-polygon > case (or possibly covers(), if you are really wanting to determine > proper intersection (ie containment)) > > Jeff Adams wrote: > > Thanks, I'm trying that now. > > It turns out the time is definitely not evenly spread, I have > a couple large polygons (~1800 points) where the intersection > call takes as much as a second or more, and the majority of > calls take under 50 ms. > > Does it matter which way I do the intersection? Would either > of these be faster: > > bigGeom.intersects(smallGeom) vs > smallGeom.intersects(bigGeom) > > I'm still curious because I have a small subset of cases where > the "search point" is not a point but a small polygon. > > Thanks again, > Jeff > > On Tue, Oct 6, 2009 at 2:36 PM, Martin Davis > <[hidden email] <mailto:[hidden email]> > <mailto:[hidden email] > <mailto:[hidden email]>>> wrote: > > Try using SimplePointInAreaLocater rather than intersects. > intersects computes a lot of extra information which is not > relevant for simple PiP tests. > > And yes, this is an obvious optimization which should be > made to > the code base. Hopefully it will happen soon... > > Jeff Adams wrote: > > I'm doing a check for intersection and it is going > extremely > slowly, and I was wondering whether anyone might have some > advice for how I could speed it up. > > I have a process that iterates over 700,000 points and > determines what polygons they intersect in a group of > polygons. > > I'm already using an STRtree to reduce the number of > polygons > I'm actually calling intersects on (typically for each > point > it is only 1 or 2 polygons). Are there any tricks for > point-in-poly lookups? > > I'm currently checking whether the time (average 200 > ms/intersection) is actually evenly spread, or if I have a > couple polygons in particular that are taking all the > time (it > is possible I have one polygon with a million points > mixed in > there or something). > > > Thanks, > Jeff > > ------------------------------------------------------------------------ > > > ------------------------------------------------------------------------ > > _______________________________________________ > jts-devel mailing list > [hidden email] > <mailto:[hidden email]> > http://lists.refractions.net/mailman/listinfo/jts-devel > > > > -- > Martin Davis > Senior Technical Architect > Refractions Research, Inc. > (250) 383-3022 > > _______________________________________________ > jts-devel mailing list > [hidden email] > <mailto:[hidden email]> > http://lists.refractions.net/mailman/listinfo/jts-devel > > > > > -- > Jeff Adams > Avencia, Inc. > 215-701-7717 > ------------------------------------------------------------------------ > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Free forum by Nabble | Edit this page |