Performance problem in "intersects"

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Performance problem in "intersects"

Jeff Adams-4
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Performance problem in "intersects"

Martin Davis
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Performance problem in "intersects"

Jeff Adams-4
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.

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Performance problem in "intersects"

Martin Davis
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Performance problem in "intersects"

Jeff Adams-4
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.

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



--
Jeff Adams
Avencia, Inc.
215-701-7717

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Performance problem in "intersects"

Martin Davis
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
Loading...