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 |
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. _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
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 |
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 |
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? -- Jeff Adams Avencia, Inc. 215-701-7717 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
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 |
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. -- Jeff Adams Avencia, Inc. 215-701-7717 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
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 |
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 |
Free forum by Nabble | Edit this page |