Intersection results, are they in order?

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

Intersection results, are they in order?

Jeff Adams-4
If I have a linestring, and I do an intersection with a large random collection of polygons such that the result will be a bunch of little linestrings in a row, I.E.

original linestring:
-----------------------------------------------
Intersection results:
        ---       --------      --

Will the MultiLineString or GeometryCollection (since I suppose some of the results could just be points where a polygon touches my linestring) result that I get back from the Intersection call be in order?  Assuming the original was something like:

LINESTRING(0 0, 100 0)

Will the results be:
MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0))

Or could they be in any order?  Will the direction of the linestrings be the same as the original, or could I get one that was (75 0, 70 0)?

_______________________________________________
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: Intersection results, are they in order?

Jeff Adams-4
Perhaps it would be helpful if I said WHY I was doing this ;-).  Often you guys suggest much better alternatives to what I'm trying anyway.

I have a starting point and a direction.  I want to find the nearest point on any of the polygons along that direction.  What I'm trying to do in my previous email is make a linestring that goes in the direction I want, using my starting point and a point I generate an arbitrary distance out, then take the intersection results and use the first (hopefully nearest) point.

Is there a "first intersection along line" method that I overlooked?  Or a cleaner way of doing this?

Thanks,
Jeff

On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams <[hidden email]> wrote:
If I have a linestring, and I do an intersection with a large random collection of polygons such that the result will be a bunch of little linestrings in a row, I.E.

original linestring:
-----------------------------------------------
Intersection results:
        ---       --------      --

Will the MultiLineString or GeometryCollection (since I suppose some of the results could just be points where a polygon touches my linestring) result that I get back from the Intersection call be in order?  Assuming the original was something like:

LINESTRING(0 0, 100 0)

Will the results be:
MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0))

Or could they be in any order?  Will the direction of the linestrings be the same as the original, or could I get one that was (75 0, 70 0)?


_______________________________________________
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: Intersection results, are they in order?

Martin Davis
In reply to this post by Jeff Adams-4
Afraid the answer is no and no.  Linestrings returned from an
intersection may be in any order and any orientation, relative to the input.

I can see that it might be useful to have the intersection operation
preserve input order and orientation for LineStrings.  Currently this
information isn't maintained, in order to make the algorithm simpler and
improve efficiency.  At the moment I can't think of a simple way of
doing this, but perhaps it's not that difficult with the right internal
structures.


Jeff Adams wrote:

> If I have a linestring, and I do an intersection with a large random
> collection of polygons such that the result will be a bunch of little
> linestrings in a row, I.E.
>
> original linestring:
> -----------------------------------------------
> Intersection results:
>         ---       --------      --
>
> Will the MultiLineString or GeometryCollection (since I suppose some
> of the results could just be points where a polygon touches my
> linestring) result that I get back from the Intersection call be in
> order?  Assuming the original was something like:
>
> LINESTRING(0 0, 100 0)
>
> Will the results be:
> MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0))
>
> Or could they be in any order?  Will the direction of the linestrings
> be the same as the original, or could I get one that was (75 0, 70 0)?
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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: Intersection results, are they in order?

Martin Davis
In reply to this post by Jeff Adams-4
How about this?

Intersect the line with the *boundaries* of the polygons.  Then take the
resulting point set and compute the distance between each point and your
start point.  The smallest distance is the one you want.

That will have the nice side effect of being faster, too.

If you need to know the actual polygon which is closest, iterate over
the polygons individually, and keep track of the one with the closest
intersection point.

Jeff Adams wrote:

> Perhaps it would be helpful if I said WHY I was doing this ;-).  Often
> you guys suggest much better alternatives to what I'm trying anyway.
>
> I have a starting point and a direction.  I want to find the nearest
> point on any of the polygons along that direction.  What I'm trying to
> do in my previous email is make a linestring that goes in the
> direction I want, using my starting point and a point I generate an
> arbitrary distance out, then take the intersection results and use the
> first (hopefully nearest) point.
>
> Is there a "first intersection along line" method that I overlooked?  
> Or a cleaner way of doing this?
>
> Thanks,
> Jeff
>
> On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     If I have a linestring, and I do an intersection with a large
>     random collection of polygons such that the result will be a bunch
>     of little linestrings in a row, I.E.
>
>     original linestring:
>     -----------------------------------------------
>     Intersection results:
>             ---       --------      --
>
>     Will the MultiLineString or GeometryCollection (since I suppose
>     some of the results could just be points where a polygon touches
>     my linestring) result that I get back from the Intersection call
>     be in order?  Assuming the original was something like:
>
>     LINESTRING(0 0, 100 0)
>
>     Will the results be:
>     MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0))
>
>     Or could they be in any order?  Will the direction of the
>     linestrings be the same as the original, or could I get one that
>     was (75 0, 70 0)?
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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: Intersection results, are they in order?

Jeff Adams-4
Thanks, I'll try that.

What is the fastest way of boiling down the polygon outlines?  I do not need to know the one that intersected, and in fact I don't even need them to remain distinct (many of the polygons are touching or even overlapping).  I could union them into a non-overlapping multipolygon and use that boundary, which would give me the fewest intersecting points to test.  I was making a multipolygon with them already (but not unioning them), is the fastest thing to do multipoly.union(multipoly.getSomePoint()).getBoundary()?  Or will the boundary of a multipolygon already go around overlapping/touching polygons inside it?

I am calculating distance from a point to the polygon group repeatedly (probably 50 -100 times on average) for each polygon group so it is probably worth it do as much prep as possible before I start figuring distances.

On Thu, Jul 30, 2009 at 2:27 PM, Martin Davis <[hidden email]> wrote:
How about this?

Intersect the line with the *boundaries* of the polygons.  Then take the resulting point set and compute the distance between each point and your start point.  The smallest distance is the one you want.

That will have the nice side effect of being faster, too.

If you need to know the actual polygon which is closest, iterate over the polygons individually, and keep track of the one with the closest intersection point.

Jeff Adams wrote:
Perhaps it would be helpful if I said WHY I was doing this ;-).  Often you guys suggest much better alternatives to what I'm trying anyway.

I have a starting point and a direction.  I want to find the nearest point on any of the polygons along that direction.  What I'm trying to do in my previous email is make a linestring that goes in the direction I want, using my starting point and a point I generate an arbitrary distance out, then take the intersection results and use the first (hopefully nearest) point.

Is there a "first intersection along line" method that I overlooked?  Or a cleaner way of doing this?

Thanks,
Jeff

On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams <[hidden email] <mailto:[hidden email]>> wrote:

   If I have a linestring, and I do an intersection with a large
   random collection of polygons such that the result will be a bunch
   of little linestrings in a row, I.E.

   original linestring:
   -----------------------------------------------
   Intersection results:
           ---       --------      --

   Will the MultiLineString or GeometryCollection (since I suppose
   some of the results could just be points where a polygon touches
   my linestring) result that I get back from the Intersection call
   be in order?  Assuming the original was something like:

   LINESTRING(0 0, 100 0)

   Will the results be:
   MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0))

   Or could they be in any order?  Will the direction of the
   linestrings be the same as the original, or could I get one that
   was (75 0, 70 0)?


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

_______________________________________________
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: Intersection results, are they in order?

Martin Davis
If you have a lot of overlapping polygons, it's probably faster to union
them all together.  This will get rid of internal linework, which should
speed things up.

JTS 1.9 and above have a Geometry.union() (unary union) method, which
uses a fast algorithm to merge geometries.  So you can just call
multipoly.union() to get the union.

Note that a MultiPolygon with overlapping components is actually an
invalid geometry.  JTS will let you build this, tho, and will let you
run unary union() on it (for just this kind of situation). But you can't
run binary overlay operations successfully on an invalid geometry.

To answer your last question, the boundary of a MultiPolygon is just a
collection of the boudaries of the components.  So boundary() by itself
won't reduce the amount of linework you are processing.

Jeff Adams wrote:

> Thanks, I'll try that.
>
> What is the fastest way of boiling down the polygon outlines?  I do
> not need to know the one that intersected, and in fact I don't even
> need them to remain distinct (many of the polygons are touching or
> even overlapping).  I could union them into a non-overlapping
> multipolygon and use that boundary, which would give me the fewest
> intersecting points to test.  I was making a multipolygon with them
> already (but not unioning them), is the fastest thing to do
> multipoly.union(multipoly.getSomePoint()).getBoundary()?  Or will the
> boundary of a multipolygon already go around overlapping/touching
> polygons inside it?
>
> I am calculating distance from a point to the polygon group repeatedly
> (probably 50 -100 times on average) for each polygon group so it is
> probably worth it do as much prep as possible before I start figuring
> distances.
>
> On Thu, Jul 30, 2009 at 2:27 PM, Martin Davis <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     How about this?
>
>     Intersect the line with the *boundaries* of the polygons.  Then
>     take the resulting point set and compute the distance between each
>     point and your start point.  The smallest distance is the one you
>     want.
>
>     That will have the nice side effect of being faster, too.
>
>     If you need to know the actual polygon which is closest, iterate
>     over the polygons individually, and keep track of the one with the
>     closest intersection point.
>
>     Jeff Adams wrote:
>
>         Perhaps it would be helpful if I said WHY I was doing this
>         ;-).  Often you guys suggest much better alternatives to what
>         I'm trying anyway.
>
>         I have a starting point and a direction.  I want to find the
>         nearest point on any of the polygons along that direction.
>          What I'm trying to do in my previous email is make a
>         linestring that goes in the direction I want, using my
>         starting point and a point I generate an arbitrary distance
>         out, then take the intersection results and use the first
>         (hopefully nearest) point.
>
>         Is there a "first intersection along line" method that I
>         overlooked?  Or a cleaner way of doing this?
>
>         Thanks,
>         Jeff
>
>         On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams
>         <[hidden email] <mailto:[hidden email]>
>         <mailto:[hidden email] <mailto:[hidden email]>>> wrote:
>
>            If I have a linestring, and I do an intersection with a large
>            random collection of polygons such that the result will be
>         a bunch
>            of little linestrings in a row, I.E.
>
>            original linestring:
>            -----------------------------------------------
>            Intersection results:
>                    ---       --------      --
>
>            Will the MultiLineString or GeometryCollection (since I suppose
>            some of the results could just be points where a polygon
>         touches
>            my linestring) result that I get back from the Intersection
>         call
>            be in order?  Assuming the original was something like:
>
>            LINESTRING(0 0, 100 0)
>
>            Will the results be:
>            MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0))
>
>            Or could they be in any order?  Will the direction of the
>            linestrings be the same as the original, or could I get one
>         that
>            was (75 0, 70 0)?
>
>
>         ------------------------------------------------------------------------
>
>         _______________________________________________
>         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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Intersection results, are they in order?

Jeff Adams-4
Unfortunately I'm actually using NTS, which is I think on level with JTS 1.8... so no unary Union method.

What about using buffer(0.0) instead of union?  Will that eliminate the internal linework?

I realize it's a bit of a hack, but it is a handy one in lots of other situations.

On Thu, Jul 30, 2009 at 3:11 PM, Martin Davis <[hidden email]> wrote:
If you have a lot of overlapping polygons, it's probably faster to union them all together.  This will get rid of internal linework, which should speed things up.
JTS 1.9 and above have a Geometry.union() (unary union) method, which uses a fast algorithm to merge geometries.  So you can just call multipoly.union() to get the union.

Note that a MultiPolygon with overlapping components is actually an invalid geometry.  JTS will let you build this, tho, and will let you run unary union() on it (for just this kind of situation). But you can't run binary overlay operations successfully on an invalid geometry.

To answer your last question, the boundary of a MultiPolygon is just a collection of the boudaries of the components.  So boundary() by itself won't reduce the amount of linework you are processing.

Jeff Adams wrote:
Thanks, I'll try that.

What is the fastest way of boiling down the polygon outlines?  I do not need to know the one that intersected, and in fact I don't even need them to remain distinct (many of the polygons are touching or even overlapping).  I could union them into a non-overlapping multipolygon and use that boundary, which would give me the fewest intersecting points to test.  I was making a multipolygon with them already (but not unioning them), is the fastest thing to do multipoly.union(multipoly.getSomePoint()).getBoundary()?  Or will the boundary of a multipolygon already go around overlapping/touching polygons inside it?

I am calculating distance from a point to the polygon group repeatedly (probably 50 -100 times on average) for each polygon group so it is probably worth it do as much prep as possible before I start figuring distances.

On Thu, Jul 30, 2009 at 2:27 PM, Martin Davis <[hidden email] <mailto:[hidden email]>> wrote:

   How about this?

   Intersect the line with the *boundaries* of the polygons.  Then
   take the resulting point set and compute the distance between each
   point and your start point.  The smallest distance is the one you
   want.

   That will have the nice side effect of being faster, too.

   If you need to know the actual polygon which is closest, iterate
   over the polygons individually, and keep track of the one with the
   closest intersection point.

   Jeff Adams wrote:

       Perhaps it would be helpful if I said WHY I was doing this
       ;-).  Often you guys suggest much better alternatives to what
       I'm trying anyway.

       I have a starting point and a direction.  I want to find the
       nearest point on any of the polygons along that direction.
        What I'm trying to do in my previous email is make a
       linestring that goes in the direction I want, using my
       starting point and a point I generate an arbitrary distance
       out, then take the intersection results and use the first
       (hopefully nearest) point.

       Is there a "first intersection along line" method that I
       overlooked?  Or a cleaner way of doing this?

       Thanks,
       Jeff

       On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams
       <[hidden email] <mailto:[hidden email]>
       <mailto:[hidden email] <mailto:[hidden email]>>> wrote:

          If I have a linestring, and I do an intersection with a large
          random collection of polygons such that the result will be
       a bunch
          of little linestrings in a row, I.E.

          original linestring:
          -----------------------------------------------
          Intersection results:
                  ---       --------      --

          Will the MultiLineString or GeometryCollection (since I suppose
          some of the results could just be points where a polygon
       touches
          my linestring) result that I get back from the Intersection
       call
          be in order?  Assuming the original was something like:

          LINESTRING(0 0, 100 0)

          Will the results be:
          MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0))

          Or could they be in any order?  Will the direction of the
          linestrings be the same as the original, or could I get one
       that
          was (75 0, 70 0)?


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

       _______________________________________________
       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



--
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: Intersection results, are they in order?

Martin Davis
Sure, buffer(0) should work (that was the recommended way to do unary
union in JTS prior to the introduction of the union() method).

Just be aware that buffer is not 100% robust, and can produce some
peculiar results in some situations.  However, these are fairly rare.  
If you do encounter robustness exceptions, you can alway drop back to
the slower method for that particular case.

Jeff Adams wrote:

> Unfortunately I'm actually using NTS, which is I think on level with
> JTS 1.8... so no unary Union method.
>
> What about using buffer(0.0) instead of union?  Will that eliminate
> the internal linework?
>
> I realize it's a bit of a hack, but it is a handy one in lots of other
> situations.
>
> On Thu, Jul 30, 2009 at 3:11 PM, Martin Davis <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     If you have a lot of overlapping polygons, it's probably faster to
>     union them all together.  This will get rid of internal linework,
>     which should speed things up.
>     JTS 1.9 and above have a Geometry.union() (unary union) method,
>     which uses a fast algorithm to merge geometries.  So you can just
>     call multipoly.union() to get the union.
>
>     Note that a MultiPolygon with overlapping components is actually
>     an invalid geometry.  JTS will let you build this, tho, and will
>     let you run unary union() on it (for just this kind of situation).
>     But you can't run binary overlay operations successfully on an
>     invalid geometry.
>
>     To answer your last question, the boundary of a MultiPolygon is
>     just a collection of the boudaries of the components.  So
>     boundary() by itself won't reduce the amount of linework you are
>     processing.
>
>     Jeff Adams wrote:
>
>         Thanks, I'll try that.
>
>         What is the fastest way of boiling down the polygon outlines?
>          I do not need to know the one that intersected, and in fact I
>         don't even need them to remain distinct (many of the polygons
>         are touching or even overlapping).  I could union them into a
>         non-overlapping multipolygon and use that boundary, which
>         would give me the fewest intersecting points to test.  I was
>         making a multipolygon with them already (but not unioning
>         them), is the fastest thing to do
>         multipoly.union(multipoly.getSomePoint()).getBoundary()?  Or
>         will the boundary of a multipolygon already go around
>         overlapping/touching polygons inside it?
>
>         I am calculating distance from a point to the polygon group
>         repeatedly (probably 50 -100 times on average) for each
>         polygon group so it is probably worth it do as much prep as
>         possible before I start figuring distances.
>
>         On Thu, Jul 30, 2009 at 2:27 PM, Martin Davis
>         <[hidden email] <mailto:[hidden email]>
>         <mailto:[hidden email]
>         <mailto:[hidden email]>>> wrote:
>
>            How about this?
>
>            Intersect the line with the *boundaries* of the polygons.  Then
>            take the resulting point set and compute the distance
>         between each
>            point and your start point.  The smallest distance is the
>         one you
>            want.
>
>            That will have the nice side effect of being faster, too.
>
>            If you need to know the actual polygon which is closest,
>         iterate
>            over the polygons individually, and keep track of the one
>         with the
>            closest intersection point.
>
>            Jeff Adams wrote:
>
>                Perhaps it would be helpful if I said WHY I was doing this
>                ;-).  Often you guys suggest much better alternatives
>         to what
>                I'm trying anyway.
>
>                I have a starting point and a direction.  I want to
>         find the
>                nearest point on any of the polygons along that direction.
>                 What I'm trying to do in my previous email is make a
>                linestring that goes in the direction I want, using my
>                starting point and a point I generate an arbitrary distance
>                out, then take the intersection results and use the first
>                (hopefully nearest) point.
>
>                Is there a "first intersection along line" method that I
>                overlooked?  Or a cleaner way of doing this?
>
>                Thanks,
>                Jeff
>
>                On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams
>                <[hidden email] <mailto:[hidden email]>
>         <mailto:[hidden email] <mailto:[hidden email]>>
>                <mailto:[hidden email] <mailto:[hidden email]>
>         <mailto:[hidden email] <mailto:[hidden email]>>>> wrote:
>
>                   If I have a linestring, and I do an intersection
>         with a large
>                   random collection of polygons such that the result
>         will be
>                a bunch
>                   of little linestrings in a row, I.E.
>
>                   original linestring:
>                   -----------------------------------------------
>                   Intersection results:
>                           ---       --------      --
>
>                   Will the MultiLineString or GeometryCollection
>         (since I suppose
>                   some of the results could just be points where a polygon
>                touches
>                   my linestring) result that I get back from the
>         Intersection
>                call
>                   be in order?  Assuming the original was something like:
>
>                   LINESTRING(0 0, 100 0)
>
>                   Will the results be:
>                   MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0))
>
>                   Or could they be in any order?  Will the direction
>         of the
>                   linestrings be the same as the original, or could I
>         get one
>                that
>                   was (75 0, 70 0)?
>
>
>              
>          ------------------------------------------------------------------------
>
>                _______________________________________________
>                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
>
>
>
>
>         --
>         Jeff Adams
>         Avencia, Inc.
>         215-701-7717
>         ------------------------------------------------------------------------
>
>         _______________________________________________
>         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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Intersection results, are they in order?

Martin Davis
It occurs to me that an even more efficient way of doing this
computation is simply to scan the line segments of the polygons and
compute their intersection (if any) with the line.  This requires a bit
more low-level coding, but should be faster than either of the
approaches discussed so far.

Martin Davis wrote:

> Sure, buffer(0) should work (that was the recommended way to do unary
> union in JTS prior to the introduction of the union() method).
>
> Just be aware that buffer is not 100% robust, and can produce some
> peculiar results in some situations.  However, these are fairly rare.  
> If you do encounter robustness exceptions, you can alway drop back to
> the slower method for that particular case.
>
> Jeff Adams wrote:
>> Unfortunately I'm actually using NTS, which is I think on level with
>> JTS 1.8... so no unary Union method.
>>
>> What about using buffer(0.0) instead of union?  Will that eliminate
>> the internal linework?
>>
>> I realize it's a bit of a hack, but it is a handy one in lots of
>> other situations.
>>
>> On Thu, Jul 30, 2009 at 3:11 PM, Martin Davis
>> <[hidden email] <mailto:[hidden email]>> wrote:
>>
>>     If you have a lot of overlapping polygons, it's probably faster to
>>     union them all together.  This will get rid of internal linework,
>>     which should speed things up.
>>     JTS 1.9 and above have a Geometry.union() (unary union) method,
>>     which uses a fast algorithm to merge geometries.  So you can just
>>     call multipoly.union() to get the union.
>>
>>     Note that a MultiPolygon with overlapping components is actually
>>     an invalid geometry.  JTS will let you build this, tho, and will
>>     let you run unary union() on it (for just this kind of situation).
>>     But you can't run binary overlay operations successfully on an
>>     invalid geometry.
>>
>>     To answer your last question, the boundary of a MultiPolygon is
>>     just a collection of the boudaries of the components.  So
>>     boundary() by itself won't reduce the amount of linework you are
>>     processing.
>>
>>     Jeff Adams wrote:
>>
>>         Thanks, I'll try that.
>>
>>         What is the fastest way of boiling down the polygon outlines?
>>          I do not need to know the one that intersected, and in fact I
>>         don't even need them to remain distinct (many of the polygons
>>         are touching or even overlapping).  I could union them into a
>>         non-overlapping multipolygon and use that boundary, which
>>         would give me the fewest intersecting points to test.  I was
>>         making a multipolygon with them already (but not unioning
>>         them), is the fastest thing to do
>>         multipoly.union(multipoly.getSomePoint()).getBoundary()?  Or
>>         will the boundary of a multipolygon already go around
>>         overlapping/touching polygons inside it?
>>
>>         I am calculating distance from a point to the polygon group
>>         repeatedly (probably 50 -100 times on average) for each
>>         polygon group so it is probably worth it do as much prep as
>>         possible before I start figuring distances.
>>
>>         On Thu, Jul 30, 2009 at 2:27 PM, Martin Davis
>>         <[hidden email] <mailto:[hidden email]>
>>         <mailto:[hidden email]
>>         <mailto:[hidden email]>>> wrote:
>>
>>            How about this?
>>
>>            Intersect the line with the *boundaries* of the polygons.  
>> Then
>>            take the resulting point set and compute the distance
>>         between each
>>            point and your start point.  The smallest distance is the
>>         one you
>>            want.
>>
>>            That will have the nice side effect of being faster, too.
>>
>>            If you need to know the actual polygon which is closest,
>>         iterate
>>            over the polygons individually, and keep track of the one
>>         with the
>>            closest intersection point.
>>
>>            Jeff Adams wrote:
>>
>>                Perhaps it would be helpful if I said WHY I was doing
>> this
>>                ;-).  Often you guys suggest much better alternatives
>>         to what
>>                I'm trying anyway.
>>
>>                I have a starting point and a direction.  I want to
>>         find the
>>                nearest point on any of the polygons along that
>> direction.
>>                 What I'm trying to do in my previous email is make a
>>                linestring that goes in the direction I want, using my
>>                starting point and a point I generate an arbitrary
>> distance
>>                out, then take the intersection results and use the first
>>                (hopefully nearest) point.
>>
>>                Is there a "first intersection along line" method that I
>>                overlooked?  Or a cleaner way of doing this?
>>
>>                Thanks,
>>                Jeff
>>
>>                On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams
>>                <[hidden email] <mailto:[hidden email]>
>>         <mailto:[hidden email] <mailto:[hidden email]>>
>>                <mailto:[hidden email] <mailto:[hidden email]>
>>         <mailto:[hidden email] <mailto:[hidden email]>>>> wrote:
>>
>>                   If I have a linestring, and I do an intersection
>>         with a large
>>                   random collection of polygons such that the result
>>         will be
>>                a bunch
>>                   of little linestrings in a row, I.E.
>>
>>                   original linestring:
>>                   -----------------------------------------------
>>                   Intersection results:
>>                           ---       --------      --
>>
>>                   Will the MultiLineString or GeometryCollection
>>         (since I suppose
>>                   some of the results could just be points where a
>> polygon
>>                touches
>>                   my linestring) result that I get back from the
>>         Intersection
>>                call
>>                   be in order?  Assuming the original was something
>> like:
>>
>>                   LINESTRING(0 0, 100 0)
>>
>>                   Will the results be:
>>                   MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0,
>> 75 0))
>>
>>                   Or could they be in any order?  Will the direction
>>         of the
>>                   linestrings be the same as the original, or could I
>>         get one
>>                that
>>                   was (75 0, 70 0)?
>>
>>
>>                      
>> ------------------------------------------------------------------------
>>
>>                _______________________________________________
>>                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
>>
>>
>>
>>
>>         --         Jeff Adams
>>         Avencia, Inc.
>>         215-701-7717
>>        
>> ------------------------------------------------------------------------
>>
>>         _______________________________________________
>>         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...