GeometryCollection boundary

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

GeometryCollection boundary

Justin York
When I try to use the getBoundary() method on a GeometryCollection I get the following error:
      java.lang.IllegalArgumentException: This method does not support GeometryCollection arguments
at com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)
at com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)

I have a collection of polygons (countries) and I want to randomly choose points which lie within any of the polygons (which are adjacent). If I could calculate the border of the collection it would prevent me from iterating over all the polygons each time I draw a new random point. Is there an easier way to do this?

_______________________________________________
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: GeometryCollection boundary

michaelm-2
Hi Justin,

> When I try to use the getBoundary() method on a GeometryCollection I
> get the following error:
>       java.lang.IllegalArgumentException: This method does not support
> GeometryCollection arguments
> at
> com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)
> at
> com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)
I suppose that getBoundary throws an IllegalArgumentException because in
the case of a GeometryCollection, the getBoundary semantic is undefined
(for ex. what is the boundary of two overlapping polygons ?)
> I have a collection of polygons (countries) and I want to randomly
> choose points which lie within any of the polygons (which are
> adjacent). If I could calculate the border of the collection it would
> prevent me from iterating over all the polygons each time I draw a new
> random point. Is there an easier way to do this?
I'm not sure I fully understand what you try to achieve but,
- you can union your polygons instead of using boundary
- if you're looking for efficiency, I would not union my polygons,
instead, I would use a spatial index (STRTree). I see two benefits:
    * you iterate only over good candidates, not all polygons
    * for each point, you do within tests with a few simple polygon, not
with a huge one

Hope that helps

Michaël
> ------------------------------------------------------------------------
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

_______________________________________________
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: GeometryCollection boundary

Justin York
In reply to this post by Justin York
I had no idea that spatial indexes even existed. Thanks for bringing that to my attention. It doesn't quite work for this specific problems but I'm sure it will help me optimize my model in the future.

I'm designing a model which begins by loading any shapefile which defines the borders of countries. Then it randomly places a specified amount of agents within the borders of any of the countries. I solved that problem by combining the envelopes of all the countries, calculating the centroid, then randomly creating a point away from the centroid but still within the envelope, and then making sure that point lies within the borders of one of the countries. That is all just initialization of the model. The placement of 600 agents in Southeast Asia and some of the Indonesian islands took 3445 attempts in a matter of seconds. I'm not too concerned about that, but if anyone has a cleaner idea please do share. Spatial indexing doesn't seem as though it would quite work from the limited amount of understanding I could gain in a few minutes.

What now concerns me is the speed of running the model. Each turn, all agents move and interact with other agents within a specified radius (neighbors). Currently to calculate the neighbors I iterate over all agents and calculate the distance between them. I imagine this is where spatial indexing could make a huge difference, however it seems to only work with rectangles. In addition, since the agents move, it seems as though I'd have to reconstruct the index each turn. If that is true, would it still be worth rebuilding the index? I imagine there's a certain threshold where it would be worth it -- I guess I would just have to find it.
 
Hi Justin,

> When I try to use the getBoundary() method on a GeometryCollection I
> get the following error:
>       java.lang.IllegalArgumentException: This method does not support
> GeometryCollection arguments
> at
> com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)
> at
> com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)
I suppose that getBoundary throws an IllegalArgumentException because in
the case of a GeometryCollection, the getBoundary semantic is undefined
(for ex. what is the boundary of two overlapping polygons ?)
> I have a collection of polygons (countries) and I want to randomly
> choose points which lie within any of the polygons (which are
> adjacent). If I could calculate the border of the collection it would
> prevent me from iterating over all the polygons each time I draw a new
> random point. Is there an easier way to do this?
I'm not sure I fully understand what you try to achieve but,
- you can union your polygons instead of using boundary
- if you're looking for efficiency, I would not union my polygons,
instead, I would use a spatial index (STRTree). I see two benefits:
   * you iterate only over good candidates, not all polygons
   * for each point, you do within tests with a few simple polygon, not
with a huge one

Hope that helps

Micha?l

_______________________________________________
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: GeometryCollection boundary

David Zwiers

Hi Justin,

 

For part two you can use the index to extract a set of candidate points using a bbox (rectangle) then just test the subset for your circular constraint – this should be faster. You can also select one of the updateable indexes (don’t have the class name off the top of my head), which means you can remove or add the points from the index – you’ll just have to include a little housekeeping code around these operations.

 

David

 


From: [hidden email] [mailto:[hidden email]] On Behalf Of Justin York
Sent: September 18, 2009 1:09 PM
To: [hidden email]
Subject: Re: [jts-devel] GeometryCollection boundary

 

I had no idea that spatial indexes even existed. Thanks for bringing that to my attention. It doesn't quite work for this specific problems but I'm sure it will help me optimize my model in the future.

 

I'm designing a model which begins by loading any shapefile which defines the borders of countries. Then it randomly places a specified amount of agents within the borders of any of the countries. I solved that problem by combining the envelopes of all the countries, calculating the centroid, then randomly creating a point away from the centroid but still within the envelope, and then making sure that point lies within the borders of one of the countries. That is all just initialization of the model. The placement of 600 agents in Southeast Asia and some of the Indonesian islands took 3445 attempts in a matter of seconds. I'm not too concerned about that, but if anyone has a cleaner idea please do share. Spatial indexing doesn't seem as though it would quite work from the limited amount of understanding I could gain in a few minutes.

 

What now concerns me is the speed of running the model. Each turn, all agents move and interact with other agents within a specified radius (neighbors). Currently to calculate the neighbors I iterate over all agents and calculate the distance between them. I imagine this is where spatial indexing could make a huge difference, however it seems to only work with rectangles. In addition, since the agents move, it seems as though I'd have to reconstruct the index each turn. If that is true, would it still be worth rebuilding the index? I imagine there's a certain threshold where it would be worth it -- I guess I would just have to find it.

 

Hi Justin,

 

> When I try to use the getBoundary() method on a GeometryCollection I

> get the following error:

>       java.lang.IllegalArgumentException: This method does not support

> GeometryCollection arguments

> at

> com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)

> at

> com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)

I suppose that getBoundary throws an IllegalArgumentException because in

the case of a GeometryCollection, the getBoundary semantic is undefined

(for ex. what is the boundary of two overlapping polygons ?)

> I have a collection of polygons (countries) and I want to randomly

> choose points which lie within any of the polygons (which are

> adjacent). If I could calculate the border of the collection it would

> prevent me from iterating over all the polygons each time I draw a new

> random point. Is there an easier way to do this?

I'm not sure I fully understand what you try to achieve but,

- you can union your polygons instead of using boundary

- if you're looking for efficiency, I would not union my polygons,

instead, I would use a spatial index (STRTree). I see two benefits:

   * you iterate only over good candidates, not all polygons

   * for each point, you do within tests with a few simple polygon, not

with a huge one

 

Hope that helps

 

Micha?l


_______________________________________________
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: GeometryCollection boundary

Martin Davis
Further to what Dave said, the updateable spatial index JTS provides is
the Quadtree.

Using a spatial index for determining neighbours within a given distance
is absolutely the way to go - it should speed things up a lot.
As David said, you use the spatial index as a primary filter using an
appropriate bounding box, and then apply the distance test as a
secondary filter. You should use Geometry#withinDistance rather than
distance - that allows some further optimization to take place.

And Michael was right about why boundary doesn't work on
GeometryCollections, and how you might use union to get around that. But
for the problem you describe, your approach works just as well. A
spatial index would help to speed up testing whether the point lies
inside a polygon boundary, but if the operation isn't time critical it
may not matter that much.

A more sophisticated approach for placing agents might be to create a
conformal TIN on the polygonal coverage, and then place the points into
a random TIN facet of one of the countries. But that is a LOT more work
to code, so almost certainly not worth it. Sometimes brute force is best!

Martin

David Zwiers wrote:

>
> Hi Justin,
>
> For part two you can use the index to extract a set of candidate
> points using a bbox (rectangle) then just test the subset for your
> circular constraint – this should be faster. You can also select one
> of the updateable indexes (don’t have the class name off the top of my
> head), which means you can remove or add the points from the index –
> you’ll just have to include a little housekeeping code around these
> operations.
>
> David
>
> ------------------------------------------------------------------------
>
> *From:* [hidden email]
> [mailto:[hidden email]] *On Behalf Of
> *Justin York
> *Sent:* September 18, 2009 1:09 PM
> *To:* [hidden email]
> *Subject:* Re: [jts-devel] GeometryCollection boundary
>
> I had no idea that spatial indexes even existed. Thanks for bringing
> that to my attention. It doesn't quite work for this specific problems
> but I'm sure it will help me optimize my model in the future.
>
> I'm designing a model which begins by loading any shapefile which
> defines the borders of countries. Then it randomly places a specified
> amount of agents within the borders of any of the countries. I solved
> that problem by combining the envelopes of all the countries,
> calculating the centroid, then randomly creating a point away from the
> centroid but still within the envelope, and then making sure that
> point lies within the borders of one of the countries. That is all
> just initialization of the model. The placement of 600 agents in
> Southeast Asia and some of the Indonesian islands took 3445 attempts
> in a matter of seconds. I'm not too concerned about that, but if
> anyone has a cleaner idea please do share. Spatial indexing doesn't
> seem as though it would quite work from the limited amount of
> understanding I could gain in a few minutes.
>
> What now concerns me is the speed of running the model. Each turn, all
> agents move and interact with other agents within a specified radius
> (neighbors). Currently to calculate the neighbors I iterate over all
> agents and calculate the distance between them. I imagine this is
> where spatial indexing could make a huge difference, however it seems
> to only work with rectangles. In addition, since the agents move, it
> seems as though I'd have to reconstruct the index each turn. If that
> is true, would it still be worth rebuilding the index? I imagine
> there's a certain threshold where it would be worth it -- I guess I
> would just have to find it.
>
>     Hi Justin,
>
>     > When I try to use the getBoundary() method on a GeometryCollection I
>
>     > get the following error:
>
>     > java.lang.IllegalArgumentException: This method does not support
>
>     > GeometryCollection arguments
>
>     > at
>
>     > com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)
>
>     > at
>
>     > com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)
>
>     I suppose that getBoundary throws an IllegalArgumentException
>     because in
>
>     the case of a GeometryCollection, the getBoundary semantic is
>     undefined
>
>     (for ex. what is the boundary of two overlapping polygons ?)
>
>     > I have a collection of polygons (countries) and I want to randomly
>
>     > choose points which lie within any of the polygons (which are
>
>     > adjacent). If I could calculate the border of the collection it would
>
>     > prevent me from iterating over all the polygons each time I draw
>     a new
>
>     > random point. Is there an easier way to do this?
>
>     I'm not sure I fully understand what you try to achieve but,
>
>     - you can union your polygons instead of using boundary
>
>     - if you're looking for efficiency, I would not union my polygons,
>
>     instead, I would use a spatial index (STRTree). I see two benefits:
>
>     * you iterate only over good candidates, not all polygons
>
>     * for each point, you do within tests with a few simple polygon, not
>
>     with a huge one
>
>     Hope that helps
>
>     Micha?l
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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: GeometryCollection boundary

Justin York
If I move the agents after inserting them into the Quadtree, does the index update itself or do I need to re-insert them with a new envelope?

On Mon, Sep 21, 2009 at 9:56 AM, Martin Davis <[hidden email]> wrote:
Further to what Dave said, the updateable spatial index JTS provides is the Quadtree.

Using a spatial index for determining neighbours within a given distance is absolutely the way to go - it should speed things up a lot.
As David said, you use the spatial index as a primary filter using an appropriate bounding box, and then apply the distance test as a secondary filter. You should use Geometry#withinDistance rather than distance - that allows some further optimization to take place.

And Michael was right about why boundary doesn't work on GeometryCollections, and how you might use union to get around that. But for the problem you describe, your approach works just as well. A spatial index would help to speed up testing whether the point lies inside a polygon boundary, but if the operation isn't time critical it may not matter that much.

A more sophisticated approach for placing agents might be to create a conformal TIN on the polygonal coverage, and then place the points into a random TIN facet of one of the countries. But that is a LOT more work to code, so almost certainly not worth it. Sometimes brute force is best!

Martin

David Zwiers wrote:

Hi Justin,

For part two you can use the index to extract a set of candidate points using a bbox (rectangle) then just test the subset for your circular constraint – this should be faster. You can also select one of the updateable indexes (don’t have the class name off the top of my head), which means you can remove or add the points from the index – you’ll just have to include a little housekeeping code around these operations.

David

------------------------------------------------------------------------

*From:* [hidden email] [mailto:[hidden email]] *On Behalf Of *Justin York
*Sent:* September 18, 2009 1:09 PM
*To:* [hidden email]
*Subject:* Re: [jts-devel] GeometryCollection boundary

I had no idea that spatial indexes even existed. Thanks for bringing that to my attention. It doesn't quite work for this specific problems but I'm sure it will help me optimize my model in the future.

I'm designing a model which begins by loading any shapefile which defines the borders of countries. Then it randomly places a specified amount of agents within the borders of any of the countries. I solved that problem by combining the envelopes of all the countries, calculating the centroid, then randomly creating a point away from the centroid but still within the envelope, and then making sure that point lies within the borders of one of the countries. That is all just initialization of the model. The placement of 600 agents in Southeast Asia and some of the Indonesian islands took 3445 attempts in a matter of seconds. I'm not too concerned about that, but if anyone has a cleaner idea please do share. Spatial indexing doesn't seem as though it would quite work from the limited amount of understanding I could gain in a few minutes.

What now concerns me is the speed of running the model. Each turn, all agents move and interact with other agents within a specified radius (neighbors). Currently to calculate the neighbors I iterate over all agents and calculate the distance between them. I imagine this is where spatial indexing could make a huge difference, however it seems to only work with rectangles. In addition, since the agents move, it seems as though I'd have to reconstruct the index each turn. If that is true, would it still be worth rebuilding the index? I imagine there's a certain threshold where it would be worth it -- I guess I would just have to find it.

   Hi Justin,

   > When I try to use the getBoundary() method on a GeometryCollection I

   > get the following error:

   > java.lang.IllegalArgumentException: This method does not support

   > GeometryCollection arguments

   > at

   > com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)

   > at

   > com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)

   I suppose that getBoundary throws an IllegalArgumentException
   because in

   the case of a GeometryCollection, the getBoundary semantic is
   undefined

   (for ex. what is the boundary of two overlapping polygons ?)

   > I have a collection of polygons (countries) and I want to randomly

   > choose points which lie within any of the polygons (which are

   > adjacent). If I could calculate the border of the collection it would

   > prevent me from iterating over all the polygons each time I draw
   a new

   > random point. Is there an easier way to do this?

   I'm not sure I fully understand what you try to achieve but,

   - you can union your polygons instead of using boundary

   - if you're looking for efficiency, I would not union my polygons,

   instead, I would use a spatial index (STRTree). I see two benefits:

   * you iterate only over good candidates, not all polygons

   * for each point, you do within tests with a few simple polygon, not

   with a huge one

   Hope that helps

   Micha?l

------------------------------------------------------------------------

_______________________________________________
jts-devel mailing listhttp://lists.refractions.net/mailman/listinfo/jts-devel
 

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing listhttp://lists.refractions.net/mailman/listinfo/jts-devel


_______________________________________________
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: GeometryCollection boundary

Martin Davis
You need to delete the original version and reinsert the new one.  
Quadtree cannot tell if the member objects have changed while they're in
the tree.

Justin York wrote:

> If I move the agents after inserting them into the Quadtree, does the
> index update itself or do I need to re-insert them with a new envelope?
>
> On Mon, Sep 21, 2009 at 9:56 AM, Martin Davis <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Further to what Dave said, the updateable spatial index JTS
>     provides is the Quadtree.
>
>     Using a spatial index for determining neighbours within a given
>     distance is absolutely the way to go - it should speed things up a
>     lot.
>     As David said, you use the spatial index as a primary filter using
>     an appropriate bounding box, and then apply the distance test as a
>     secondary filter. You should use Geometry#withinDistance rather
>     than distance - that allows some further optimization to take place.
>
>     And Michael was right about why boundary doesn't work on
>     GeometryCollections, and how you might use union to get around
>     that. But for the problem you describe, your approach works just
>     as well. A spatial index would help to speed up testing whether
>     the point lies inside a polygon boundary, but if the operation
>     isn't time critical it may not matter that much.
>
>     A more sophisticated approach for placing agents might be to
>     create a conformal TIN on the polygonal coverage, and then place
>     the points into a random TIN facet of one of the countries. But
>     that is a LOT more work to code, so almost certainly not worth it.
>     Sometimes brute force is best!
>
>     Martin
>
>     David Zwiers wrote:
>
>
>         Hi Justin,
>
>         For part two you can use the index to extract a set of
>         candidate points using a bbox (rectangle) then just test the
>         subset for your circular constraint – this should be faster.
>         You can also select one of the updateable indexes (don’t have
>         the class name off the top of my head), which means you can
>         remove or add the points from the index – you’ll just have to
>         include a little housekeeping code around these operations.
>
>         David
>
>         ------------------------------------------------------------------------
>
>         *From:* [hidden email]
>         <mailto:[hidden email]>
>         [mailto:[hidden email]
>         <mailto:[hidden email]>] *On Behalf
>         Of *Justin York
>         *Sent:* September 18, 2009 1:09 PM
>         *To:* [hidden email]
>         <mailto:[hidden email]>
>         *Subject:* Re: [jts-devel] GeometryCollection boundary
>
>         I had no idea that spatial indexes even existed. Thanks for
>         bringing that to my attention. It doesn't quite work for this
>         specific problems but I'm sure it will help me optimize my
>         model in the future.
>
>         I'm designing a model which begins by loading any shapefile
>         which defines the borders of countries. Then it randomly
>         places a specified amount of agents within the borders of any
>         of the countries. I solved that problem by combining the
>         envelopes of all the countries, calculating the centroid, then
>         randomly creating a point away from the centroid but still
>         within the envelope, and then making sure that point lies
>         within the borders of one of the countries. That is all just
>         initialization of the model. The placement of 600 agents in
>         Southeast Asia and some of the Indonesian islands took 3445
>         attempts in a matter of seconds. I'm not too concerned about
>         that, but if anyone has a cleaner idea please do share.
>         Spatial indexing doesn't seem as though it would quite work
>         from the limited amount of understanding I could gain in a few
>         minutes.
>
>         What now concerns me is the speed of running the model. Each
>         turn, all agents move and interact with other agents within a
>         specified radius (neighbors). Currently to calculate the
>         neighbors I iterate over all agents and calculate the distance
>         between them. I imagine this is where spatial indexing could
>         make a huge difference, however it seems to only work with
>         rectangles. In addition, since the agents move, it seems as
>         though I'd have to reconstruct the index each turn. If that is
>         true, would it still be worth rebuilding the index? I imagine
>         there's a certain threshold where it would be worth it -- I
>         guess I would just have to find it.
>
>            Hi Justin,
>
>            > When I try to use the getBoundary() method on a
>         GeometryCollection I
>
>            > get the following error:
>
>            > java.lang.IllegalArgumentException: This method does not
>         support
>
>            > GeometryCollection arguments
>
>            > at
>
>            >
>         com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)
>
>            > at
>
>            >
>         com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)
>
>            I suppose that getBoundary throws an IllegalArgumentException
>            because in
>
>            the case of a GeometryCollection, the getBoundary semantic is
>            undefined
>
>            (for ex. what is the boundary of two overlapping polygons ?)
>
>            > I have a collection of polygons (countries) and I want to
>         randomly
>
>            > choose points which lie within any of the polygons (which are
>
>            > adjacent). If I could calculate the border of the
>         collection it would
>
>            > prevent me from iterating over all the polygons each time
>         I draw
>            a new
>
>            > random point. Is there an easier way to do this?
>
>            I'm not sure I fully understand what you try to achieve but,
>
>            - you can union your polygons instead of using boundary
>
>            - if you're looking for efficiency, I would not union my
>         polygons,
>
>            instead, I would use a spatial index (STRTree). I see two
>         benefits:
>
>            * you iterate only over good candidates, not all polygons
>
>            * for each point, you do within tests with a few simple
>         polygon, not
>
>            with a huge one
>
>            Hope that helps
>
>            Micha?l
>
>         ------------------------------------------------------------------------
>
>         _______________________________________________
>         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
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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: GeometryCollection boundary

Justin York
Adding the spatial indexing didn't speed things up -- it actually slowed things down slightly. Could it be that I implemented it poorly? Does the size of the bounding boxes impact it much? I use rather small envelopes.

On Mon, Sep 28, 2009 at 9:49 AM, Martin Davis <[hidden email]> wrote:
You need to delete the original version and reinsert the new one.  Quadtree cannot tell if the member objects have changed while they're in the tree.

Justin York wrote:
If I move the agents after inserting them into the Quadtree, does the index update itself or do I need to re-insert them with a new envelope?

On Mon, Sep 21, 2009 at 9:56 AM, Martin Davis <[hidden email] <mailto:[hidden email]>> wrote:

   Further to what Dave said, the updateable spatial index JTS
   provides is the Quadtree.

   Using a spatial index for determining neighbours within a given
   distance is absolutely the way to go - it should speed things up a
   lot.
   As David said, you use the spatial index as a primary filter using
   an appropriate bounding box, and then apply the distance test as a
   secondary filter. You should use Geometry#withinDistance rather
   than distance - that allows some further optimization to take place.

   And Michael was right about why boundary doesn't work on
   GeometryCollections, and how you might use union to get around
   that. But for the problem you describe, your approach works just
   as well. A spatial index would help to speed up testing whether
   the point lies inside a polygon boundary, but if the operation
   isn't time critical it may not matter that much.

   A more sophisticated approach for placing agents might be to
   create a conformal TIN on the polygonal coverage, and then place
   the points into a random TIN facet of one of the countries. But
   that is a LOT more work to code, so almost certainly not worth it.
   Sometimes brute force is best!

   Martin

   David Zwiers wrote:


       Hi Justin,

       For part two you can use the index to extract a set of
       candidate points using a bbox (rectangle) then just test the
       subset for your circular constraint – this should be faster.
       You can also select one of the updateable indexes (don’t have
       the class name off the top of my head), which means you can
       remove or add the points from the index – you’ll just have to
       include a little housekeeping code around these operations.

       David

       ------------------------------------------------------------------------

       *From:* [hidden email]
       <mailto:[hidden email]>
       [mailto:[hidden email]
       <mailto:[hidden email]>] *On Behalf
       Of *Justin York
       *Sent:* September 18, 2009 1:09 PM
       *To:* [hidden email]
       <mailto:[hidden email]>

       *Subject:* Re: [jts-devel] GeometryCollection boundary

       I had no idea that spatial indexes even existed. Thanks for
       bringing that to my attention. It doesn't quite work for this
       specific problems but I'm sure it will help me optimize my
       model in the future.

       I'm designing a model which begins by loading any shapefile
       which defines the borders of countries. Then it randomly
       places a specified amount of agents within the borders of any
       of the countries. I solved that problem by combining the
       envelopes of all the countries, calculating the centroid, then
       randomly creating a point away from the centroid but still
       within the envelope, and then making sure that point lies
       within the borders of one of the countries. That is all just
       initialization of the model. The placement of 600 agents in
       Southeast Asia and some of the Indonesian islands took 3445
       attempts in a matter of seconds. I'm not too concerned about
       that, but if anyone has a cleaner idea please do share.
       Spatial indexing doesn't seem as though it would quite work
       from the limited amount of understanding I could gain in a few
       minutes.

       What now concerns me is the speed of running the model. Each
       turn, all agents move and interact with other agents within a
       specified radius (neighbors). Currently to calculate the
       neighbors I iterate over all agents and calculate the distance
       between them. I imagine this is where spatial indexing could
       make a huge difference, however it seems to only work with
       rectangles. In addition, since the agents move, it seems as
       though I'd have to reconstruct the index each turn. If that is
       true, would it still be worth rebuilding the index? I imagine
       there's a certain threshold where it would be worth it -- I
       guess I would just have to find it.

          Hi Justin,

          > When I try to use the getBoundary() method on a
       GeometryCollection I

          > get the following error:

          > java.lang.IllegalArgumentException: This method does not
       support

          > GeometryCollection arguments

          > at

          >
       com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)

          > at

          >
       com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)

          I suppose that getBoundary throws an IllegalArgumentException
          because in

          the case of a GeometryCollection, the getBoundary semantic is
          undefined

          (for ex. what is the boundary of two overlapping polygons ?)

          > I have a collection of polygons (countries) and I want to
       randomly

          > choose points which lie within any of the polygons (which are

          > adjacent). If I could calculate the border of the
       collection it would

          > prevent me from iterating over all the polygons each time
       I draw
          a new

          > random point. Is there an easier way to do this?

          I'm not sure I fully understand what you try to achieve but,

          - you can union your polygons instead of using boundary

          - if you're looking for efficiency, I would not union my
       polygons,

          instead, I would use a spatial index (STRTree). I see two
       benefits:

          * you iterate only over good candidates, not all polygons

          * for each point, you do within tests with a few simple
       polygon, not

          with a huge one

          Hope that helps

          Micha?l

       ------------------------------------------------------------------------

       _______________________________________________
       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


------------------------------------------------------------------------

_______________________________________________
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


_______________________________________________
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: GeometryCollection boundary

Martin Davis
Smaller bounding boxes should make the index run faster, not slower.

Possibly the re-indexing is taking up a lot of time - although it seems
like this should still be faster than brute force search.

You might try and look for a kdtree implementation.  kdTrees are the
fastest way to index sets of points.  JTS 1.11 (in CVS) now has a
kdtree, but it is not dynamic (ie doesn't support deletion).

Justin York wrote:

> Adding the spatial indexing didn't speed things up -- it actually
> slowed things down slightly. Could it be that I implemented it poorly?
> Does the size of the bounding boxes impact it much? I use rather small
> envelopes.
>
> On Mon, Sep 28, 2009 at 9:49 AM, Martin Davis <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     You need to delete the original version and reinsert the new one.
>      Quadtree cannot tell if the member objects have changed while
>     they're in the tree.
>
>     Justin York wrote:
>
>         If I move the agents after inserting them into the Quadtree,
>         does the index update itself or do I need to re-insert them
>         with a new envelope?
>
>         On Mon, Sep 21, 2009 at 9:56 AM, Martin Davis
>         <[hidden email] <mailto:[hidden email]>
>         <mailto:[hidden email]
>         <mailto:[hidden email]>>> wrote:
>
>            Further to what Dave said, the updateable spatial index JTS
>            provides is the Quadtree.
>
>            Using a spatial index for determining neighbours within a given
>            distance is absolutely the way to go - it should speed
>         things up a
>            lot.
>            As David said, you use the spatial index as a primary
>         filter using
>            an appropriate bounding box, and then apply the distance
>         test as a
>            secondary filter. You should use Geometry#withinDistance rather
>            than distance - that allows some further optimization to
>         take place.
>
>            And Michael was right about why boundary doesn't work on
>            GeometryCollections, and how you might use union to get around
>            that. But for the problem you describe, your approach works
>         just
>            as well. A spatial index would help to speed up testing whether
>            the point lies inside a polygon boundary, but if the operation
>            isn't time critical it may not matter that much.
>
>            A more sophisticated approach for placing agents might be to
>            create a conformal TIN on the polygonal coverage, and then
>         place
>            the points into a random TIN facet of one of the countries. But
>            that is a LOT more work to code, so almost certainly not
>         worth it.
>            Sometimes brute force is best!
>
>            Martin
>
>            David Zwiers wrote:
>
>
>                Hi Justin,
>
>                For part two you can use the index to extract a set of
>                candidate points using a bbox (rectangle) then just
>         test the
>                subset for your circular constraint – this should be
>         faster.
>                You can also select one of the updateable indexes
>         (don’t have
>                the class name off the top of my head), which means you can
>                remove or add the points from the index – you’ll just
>         have to
>                include a little housekeeping code around these operations.
>
>                David
>
>              
>          ------------------------------------------------------------------------
>
>                *From:* [hidden email]
>         <mailto:[hidden email]>
>                <mailto:[hidden email]
>         <mailto:[hidden email]>>
>                [mailto:[hidden email]
>         <mailto:[hidden email]>
>                <mailto:[hidden email]
>         <mailto:[hidden email]>>] *On Behalf
>                Of *Justin York
>                *Sent:* September 18, 2009 1:09 PM
>                *To:* [hidden email]
>         <mailto:[hidden email]>
>                <mailto:[hidden email]
>         <mailto:[hidden email]>>
>
>                *Subject:* Re: [jts-devel] GeometryCollection boundary
>
>                I had no idea that spatial indexes even existed. Thanks for
>                bringing that to my attention. It doesn't quite work
>         for this
>                specific problems but I'm sure it will help me optimize my
>                model in the future.
>
>                I'm designing a model which begins by loading any shapefile
>                which defines the borders of countries. Then it randomly
>                places a specified amount of agents within the borders
>         of any
>                of the countries. I solved that problem by combining the
>                envelopes of all the countries, calculating the
>         centroid, then
>                randomly creating a point away from the centroid but still
>                within the envelope, and then making sure that point lies
>                within the borders of one of the countries. That is all
>         just
>                initialization of the model. The placement of 600 agents in
>                Southeast Asia and some of the Indonesian islands took 3445
>                attempts in a matter of seconds. I'm not too concerned
>         about
>                that, but if anyone has a cleaner idea please do share.
>                Spatial indexing doesn't seem as though it would quite work
>                from the limited amount of understanding I could gain
>         in a few
>                minutes.
>
>                What now concerns me is the speed of running the model.
>         Each
>                turn, all agents move and interact with other agents
>         within a
>                specified radius (neighbors). Currently to calculate the
>                neighbors I iterate over all agents and calculate the
>         distance
>                between them. I imagine this is where spatial indexing
>         could
>                make a huge difference, however it seems to only work with
>                rectangles. In addition, since the agents move, it seems as
>                though I'd have to reconstruct the index each turn. If
>         that is
>                true, would it still be worth rebuilding the index? I
>         imagine
>                there's a certain threshold where it would be worth it -- I
>                guess I would just have to find it.
>
>                   Hi Justin,
>
>                   > When I try to use the getBoundary() method on a
>                GeometryCollection I
>
>                   > get the following error:
>
>                   > java.lang.IllegalArgumentException: This method
>         does not
>                support
>
>                   > GeometryCollection arguments
>
>                   > at
>
>                   >
>              
>          com.vividsolutions.jts.geom.Geometry.checkNotGeometryCollection(Geometry.java:1487)
>
>                   > at
>
>                   >
>              
>          com.vividsolutions.jts.geom.GeometryCollection.getBoundary(GeometryCollection.java:152)
>
>                   I suppose that getBoundary throws an
>         IllegalArgumentException
>                   because in
>
>                   the case of a GeometryCollection, the getBoundary
>         semantic is
>                   undefined
>
>                   (for ex. what is the boundary of two overlapping
>         polygons ?)
>
>                   > I have a collection of polygons (countries) and I
>         want to
>                randomly
>
>                   > choose points which lie within any of the polygons
>         (which are
>
>                   > adjacent). If I could calculate the border of the
>                collection it would
>
>                   > prevent me from iterating over all the polygons
>         each time
>                I draw
>                   a new
>
>                   > random point. Is there an easier way to do this?
>
>                   I'm not sure I fully understand what you try to
>         achieve but,
>
>                   - you can union your polygons instead of using boundary
>
>                   - if you're looking for efficiency, I would not union my
>                polygons,
>
>                   instead, I would use a spatial index (STRTree). I
>         see two
>                benefits:
>
>                   * you iterate only over good candidates, not all
>         polygons
>
>                   * for each point, you do within tests with a few simple
>                polygon, not
>
>                   with a huge one
>
>                   Hope that helps
>
>                   Micha?l
>
>              
>          ------------------------------------------------------------------------
>
>                _______________________________________________
>                jts-devel mailing list
>
>                [hidden email]
>         <mailto:[hidden email]>
>                <mailto:[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]>
>            <mailto:[hidden email]
>         <mailto:[hidden email]>>
>
>            http://lists.refractions.net/mailman/listinfo/jts-devel
>
>
>         ------------------------------------------------------------------------
>
>         _______________________________________________
>         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
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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...