Hi,
I'm trying to create a negative mitred buffer on a (simple) polygon with JTS 1.10, and I'm getting strange results very occasionally. For example, the following code gives me an output geometry that actually extends outside the original geometry (even though a negative buffer is used). WKTReader wktReader = new WKTReader(); String geom = "POLYGON ((588736.6028960398 4518922.914991864, " + "588736.1060708747 4518922.061957178, 588718.6830715544 " + "4518930.620699637, 588712.0102834741 4518933.8985304395, " + "588722.7612465625 4518964.956739423, 588755.2073151038 " + "4518948.2420851765, 588750.2892019567 4518938.490656119, " + "588750.2892047082 4518938.490654858, 588741.1098934844 " + "4518920.290260831, 588736.6028960398 4518922.914991864))"; Geometry inputGeometry = wktReader.read(geom); BufferParameters bufferParameters = new BufferParameters(); bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); Geometry bufferedGeometry = BufferOp.bufferOp( inputGeometry, -5.0, bufferParameters); I've tried using a few different strategies in investigating this, such as reducing the coordinate precision, offsetting the x and/or y coordinates by a constant offset, or iteratively buffering the geometry (for example, buffering it five times by -1.0). All of these strategies have had limited success, and none seem to work in all cases that I'm encountering. Does this situation spring out to anyone, or is there any advice on how to get around this (or is this the expected behaviour for some reason?). I would be happy to *attempt* to fix this in JTS if someone can point me in the general direction of where the issue probably is. Thanks in advance for any information, Gabriel Reid _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
This is probably due to some sort of limitation with the mitring
algorithm. However, I notice that the 7th and 8th points of your geometry are almost identical. If I remove one of these, the mitred buffer looks fine. Can you clean the points of your geometries somehow to avoid this situation? Gabriel Reid wrote: > Hi, > > I'm trying to create a negative mitred buffer on a (simple) polygon with > JTS 1.10, and I'm getting strange results very occasionally. For > example, the following code gives me an output geometry that actually > extends outside the original geometry (even though a negative buffer is > used). > > WKTReader wktReader = new WKTReader(); > String geom = "POLYGON ((588736.6028960398 4518922.914991864, " > + "588736.1060708747 4518922.061957178, > 588718.6830715544 " > + "4518930.620699637, 588712.0102834741 > 4518933.8985304395, " > + "588722.7612465625 4518964.956739423, > 588755.2073151038 " > + "4518948.2420851765, 588750.2892019567 > 4518938.490656119, " > + "588750.2892047082 4518938.490654858, > 588741.1098934844 " > + "4518920.290260831, 588736.6028960398 > 4518922.914991864))"; > Geometry inputGeometry = wktReader.read(geom); > > BufferParameters bufferParameters = new BufferParameters(); > bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); > Geometry bufferedGeometry = BufferOp.bufferOp( > inputGeometry, -5.0, > bufferParameters); > > > > I've tried using a few different strategies in investigating this, such > as reducing the coordinate precision, offsetting the x and/or y > coordinates by a constant offset, or iteratively buffering the geometry > (for example, buffering it five times by -1.0). All of these strategies > have had limited success, and none seem to work in all cases that I'm > encountering. > > Does this situation spring out to anyone, or is there any advice on how > to get around this (or is this the expected behaviour for some reason?). > > I would be happy to *attempt* to fix this in JTS if someone can point me > in the general direction of where the issue probably is. > > > Thanks in advance for any information, > > Gabriel Reid > _______________________________________________ > 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 |
Hi Martin,
> > I'm trying to create a negative mitred buffer on a (simple) polygon with > > JTS 1.10, and I'm getting strange results very occasionally. For > > example, the following code gives me an output geometry that actually > > extends outside the original geometry (even though a negative buffer is > > used). > This is probably due to some sort of limitation with the mitring > algorithm. However, I notice that the 7th and 8th points of your > geometry are almost identical. If I remove one of these, the mitred > buffer looks fine. Can you clean the points of your geometries somehow > to avoid this situation? Based on what I've seen, it does indeed seem to be due to very short edges. I've tried cleaning the geometry by reducing coordinate precision to one place past the decimal and then running it through a DouglasPeuckerSimplifier with a tolerance of 0 to remove duplicate coordinates, but this still problem still comes out sometimes (as there are still some very close coordinates present). I believe I can clean out all the extremely short edges another way, but I'm also taking a look at the code in the OffsetCurveBuilder to see if I can find where it's going wrong. Regards, Gabriel _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Ok, let me know if you find anything. I'll try and take a look as well.
Gabriel Reid wrote: > Hi Martin, > > >>> I'm trying to create a negative mitred buffer on a (simple) polygon >>> > with > >>> JTS 1.10, and I'm getting strange results very occasionally. For >>> example, the following code gives me an output geometry that >>> > actually > >>> extends outside the original geometry (even though a negative buffer >>> > is > >>> used). >>> > > >> This is probably due to some sort of limitation with the mitring >> algorithm. However, I notice that the 7th and 8th points of your >> geometry are almost identical. If I remove one of these, the mitred >> buffer looks fine. Can you clean the points of your geometries >> > somehow > >> to avoid this situation? >> > > Based on what I've seen, it does indeed seem to be due to very short > edges. I've tried cleaning the geometry by reducing coordinate precision > to one place past the decimal and then running it through a > DouglasPeuckerSimplifier with a tolerance of 0 to remove duplicate > coordinates, but this still problem still comes out sometimes (as there > are still some very close coordinates present). > > I believe I can clean out all the extremely short edges another way, but > I'm also taking a look at the code in the OffsetCurveBuilder to see if I > can find where it's going wrong. > > > Regards, > > Gabriel > > _______________________________________________ > 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 Martin Davis
Good news! I looked into this problem, and found a minor bug in the
buffer input simplification algorithm. With this fix the situation you provided is no longer a problem. This is commited to CVS. Can you try this out on to see if it solves the other problems you have encountered? Martin Davis wrote: > This is probably due to some sort of limitation with the mitring > algorithm. However, I notice that the 7th and 8th points of your > geometry are almost identical. If I remove one of these, the mitred > buffer looks fine. Can you clean the points of your geometries > somehow to avoid this situation? > > Gabriel Reid wrote: >> Hi, >> >> I'm trying to create a negative mitred buffer on a (simple) polygon with >> JTS 1.10, and I'm getting strange results very occasionally. For >> example, the following code gives me an output geometry that actually >> extends outside the original geometry (even though a negative buffer is >> used). >> >> WKTReader wktReader = new WKTReader(); >> String geom = "POLYGON ((588736.6028960398 4518922.914991864, " >> + "588736.1060708747 4518922.061957178, >> 588718.6830715544 " >> + "4518930.620699637, 588712.0102834741 >> 4518933.8985304395, " >> + "588722.7612465625 4518964.956739423, >> 588755.2073151038 " >> + "4518948.2420851765, 588750.2892019567 >> 4518938.490656119, " >> + "588750.2892047082 4518938.490654858, >> 588741.1098934844 " >> + "4518920.290260831, 588736.6028960398 >> 4518922.914991864))"; >> Geometry inputGeometry = wktReader.read(geom); >> >> BufferParameters bufferParameters = new BufferParameters(); >> bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); >> Geometry bufferedGeometry = BufferOp.bufferOp( >> inputGeometry, -5.0, >> bufferParameters); >> >> >> >> I've tried using a few different strategies in investigating this, such >> as reducing the coordinate precision, offsetting the x and/or y >> coordinates by a constant offset, or iteratively buffering the geometry >> (for example, buffering it five times by -1.0). All of these strategies >> have had limited success, and none seem to work in all cases that I'm >> encountering. >> >> Does this situation spring out to anyone, or is there any advice on how >> to get around this (or is this the expected behaviour for some reason?). >> >> I would be happy to *attempt* to fix this in JTS if someone can point me >> in the general direction of where the issue probably is. >> >> >> Thanks in advance for any information, >> >> Gabriel Reid >> _______________________________________________ >> 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 |
Hi Martin,
Thanks a lot for the quick support! I just tested this on the full dataset that I've been working with, and there are still some cases coming out; I'll try to isolate what the situation is with those cases and see if there is a pattern (or if I can do something further with data cleaning). I'll keep you posted. Gabriel > -----Original Message----- > From: [hidden email] [mailto:jts-devel- > [hidden email]] On Behalf Of Martin Davis > Sent: donderdag 26 februari 2009 2:22 > To: JTS Topology Suite Development > Subject: Re: [jts-devel] Odd behavior in negative mitred buffer > > Good news! I looked into this problem, and found a minor bug in the > buffer input simplification algorithm. With this fix the situation you > provided is no longer a problem. > > This is commited to CVS. > > Can you try this out on to see if it solves the other problems you have > encountered? > > > Martin Davis wrote: > > This is probably due to some sort of limitation with the mitring > > algorithm. However, I notice that the 7th and 8th points of your > > geometry are almost identical. If I remove one of these, the mitred > > buffer looks fine. Can you clean the points of your geometries > > somehow to avoid this situation? > > > > Gabriel Reid wrote: > >> Hi, > >> > >> I'm trying to create a negative mitred buffer on a (simple) polygon > with > >> JTS 1.10, and I'm getting strange results very occasionally. For > >> example, the following code gives me an output geometry that > >> extends outside the original geometry (even though a negative buffer is > >> used). > >> > >> WKTReader wktReader = new WKTReader(); > >> String geom = "POLYGON ((588736.6028960398 4518922.914991864, " > >> + "588736.1060708747 4518922.061957178, > >> 588718.6830715544 " > >> + "4518930.620699637, 588712.0102834741 > >> 4518933.8985304395, " > >> + "588722.7612465625 4518964.956739423, > >> 588755.2073151038 " > >> + "4518948.2420851765, 588750.2892019567 > >> 4518938.490656119, " > >> + "588750.2892047082 4518938.490654858, > >> 588741.1098934844 " > >> + "4518920.290260831, 588736.6028960398 > >> 4518922.914991864))"; > >> Geometry inputGeometry = wktReader.read(geom); > >> > >> BufferParameters bufferParameters = new BufferParameters(); > >> bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); > >> Geometry bufferedGeometry = BufferOp.bufferOp( > >> inputGeometry, -5.0, > >> bufferParameters); > >> > >> > >> > >> I've tried using a few different strategies in investigating this, > >> as reducing the coordinate precision, offsetting the x and/or y > >> coordinates by a constant offset, or iteratively buffering the geometry > >> (for example, buffering it five times by -1.0). All of these strategies > >> have had limited success, and none seem to work in all cases that I'm > >> encountering. > >> > >> Does this situation spring out to anyone, or is there any advice on how > >> to get around this (or is this the expected behaviour for some > reason?). > >> > >> I would be happy to *attempt* to fix this in JTS if someone can point > me > >> in the general direction of where the issue probably is. > >> > >> > >> Thanks in advance for any information, > >> > >> Gabriel Reid > >> _______________________________________________ > >> 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 |
Ok, Gabriel. It sounds like some progress, at least.
Please post the other failure cases when you have isolated them. Perhaps the next problem will be as easy to solve as the last one... 8^) Gabriel Reid wrote: > Hi Martin, > > Thanks a lot for the quick support! > > I just tested this on the full dataset that I've been working with, and > there are still some cases coming out; I'll try to isolate what the > situation is with those cases and see if there is a pattern (or if I can > do something further with data cleaning). > > I'll keep you posted. > > > Gabriel > > > >> -----Original Message----- >> From: [hidden email] [mailto:jts-devel- >> [hidden email]] On Behalf Of Martin Davis >> Sent: donderdag 26 februari 2009 2:22 >> To: JTS Topology Suite Development >> Subject: Re: [jts-devel] Odd behavior in negative mitred buffer >> >> Good news! I looked into this problem, and found a minor bug in the >> buffer input simplification algorithm. With this fix the situation >> > you > >> provided is no longer a problem. >> >> This is commited to CVS. >> >> Can you try this out on to see if it solves the other problems you >> > have > >> encountered? >> >> >> Martin Davis wrote: >> >>> This is probably due to some sort of limitation with the mitring >>> algorithm. However, I notice that the 7th and 8th points of your >>> geometry are almost identical. If I remove one of these, the mitred >>> buffer looks fine. Can you clean the points of your geometries >>> somehow to avoid this situation? >>> >>> Gabriel Reid wrote: >>> >>>> Hi, >>>> >>>> I'm trying to create a negative mitred buffer on a (simple) polygon >>>> >> with >> >>>> JTS 1.10, and I'm getting strange results very occasionally. For >>>> example, the following code gives me an output geometry that >>>> > actually > >>>> extends outside the original geometry (even though a negative >>>> > buffer is > >>>> used). >>>> >>>> WKTReader wktReader = new WKTReader(); >>>> String geom = "POLYGON ((588736.6028960398 4518922.914991864, " >>>> + "588736.1060708747 4518922.061957178, >>>> 588718.6830715544 " >>>> + "4518930.620699637, 588712.0102834741 >>>> 4518933.8985304395, " >>>> + "588722.7612465625 4518964.956739423, >>>> 588755.2073151038 " >>>> + "4518948.2420851765, 588750.2892019567 >>>> 4518938.490656119, " >>>> + "588750.2892047082 4518938.490654858, >>>> 588741.1098934844 " >>>> + "4518920.290260831, 588736.6028960398 >>>> 4518922.914991864))"; >>>> Geometry inputGeometry = wktReader.read(geom); >>>> >>>> BufferParameters bufferParameters = new BufferParameters(); >>>> bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); >>>> Geometry bufferedGeometry = BufferOp.bufferOp( >>>> inputGeometry, -5.0, >>>> bufferParameters); >>>> >>>> >>>> >>>> I've tried using a few different strategies in investigating this, >>>> > such > >>>> as reducing the coordinate precision, offsetting the x and/or y >>>> coordinates by a constant offset, or iteratively buffering the >>>> > geometry > >>>> (for example, buffering it five times by -1.0). All of these >>>> > strategies > >>>> have had limited success, and none seem to work in all cases that >>>> > I'm > >>>> encountering. >>>> >>>> Does this situation spring out to anyone, or is there any advice on >>>> > how > >>>> to get around this (or is this the expected behaviour for some >>>> >> reason?). >> >>>> I would be happy to *attempt* to fix this in JTS if someone can >>>> > point > >> me >> >>>> in the general direction of where the issue probably is. >>>> >>>> >>>> Thanks in advance for any information, >>>> >>>> Gabriel Reid >>>> _______________________________________________ >>>> 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 > > -- 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 |
Hi Martin,
I've got a few other failure cases here, showing what seems to be a few different examples of this kind of behaviour: // Simple five-sided polygon that gets transformed into three triangles POLYGON ((589300.089821923 4519627.577687806, 589296.6197410262 4519621.834087054, 589292.5450979208 4519615.089809029, 589282.7894421419 4519620.983829066, 589289.8814929381 4519632.722288636, 589300.089821923 4519627.577687806)) // Another example of the same triangle behavior POLYGON ((588978.2942617612 4519797.499233156, 588989.1612999197 4519792.050291001, 588982.5784094566 4519779.549041149, 588962.0866377753 4519790.334848753, 588967.4026187821 4519802.960530801, 588978.2942617612 4519797.499233156)) // Resulting polygon has a single edge extending off one corner POLYGON ((589099.8017397423 4518490.719003885, 589097.1198886324 4518486.20858194, 589090.9424687021 4518475.819013388, 589069.8993093553 4518487.1362185385, 589078.7377975255 4518502.093799692, 589081.1515112884 4518509.334764771, 589103.7370954598 4518497.015419995, 589099.8017397423 4518490.719003885)) // Similar behaviour as the original case that was posted, this polygon // has to points that are very close together POLYGON ((587854.8616905196 4519121.941123185, 587863.6671614297 4519138.176489661, 587863.9386104685 4519138.676991724, 587880.5408633598 4519129.672513268, 587871.463857397 4519112.9366913745, 587854.8616905196 4519121.941123185)) All of these examples can be demonstrated with the code that I posted before (creating a mitred buffer with a magnitude of -5.0). Again, if you don't have time and/or motivation to look into this, I'd be more than happy to attempt to assist in doing that, especially if you have a good idea of where to look (I'm trying to have a look anyhow). Thanks again for the assistance, Gabriel > -----Original Message----- > From: [hidden email] [mailto:jts-devel- > [hidden email]] On Behalf Of Martin Davis > Sent: donderdag 26 februari 2009 17:50 > To: JTS Topology Suite Development > Subject: Re: [jts-devel] Odd behavior in negative mitred buffer > > Ok, Gabriel. It sounds like some progress, at least. > > Please post the other failure cases when you have isolated them. > Perhaps the next problem will be as easy to solve as the last one... > > Gabriel Reid wrote: > > Hi Martin, > > > > Thanks a lot for the quick support! > > > > I just tested this on the full dataset that I've been working with, and > > there are still some cases coming out; I'll try to isolate what the > > situation is with those cases and see if there is a pattern (or if I can > > do something further with data cleaning). > > > > I'll keep you posted. > > > > > > Gabriel > > > > > > > >> -----Original Message----- > >> From: [hidden email] [mailto:jts-devel- > >> [hidden email]] On Behalf Of Martin Davis > >> Sent: donderdag 26 februari 2009 2:22 > >> To: JTS Topology Suite Development > >> Subject: Re: [jts-devel] Odd behavior in negative mitred buffer > >> > >> Good news! I looked into this problem, and found a minor bug in > >> buffer input simplification algorithm. With this fix the situation > >> > > you > > > >> provided is no longer a problem. > >> > >> This is commited to CVS. > >> > >> Can you try this out on to see if it solves the other problems you > >> > > have > > > >> encountered? > >> > >> > >> Martin Davis wrote: > >> > >>> This is probably due to some sort of limitation with the mitring > >>> algorithm. However, I notice that the 7th and 8th points of your > >>> geometry are almost identical. If I remove one of these, the > >>> buffer looks fine. Can you clean the points of your geometries > >>> somehow to avoid this situation? > >>> > >>> Gabriel Reid wrote: > >>> > >>>> Hi, > >>>> > >>>> I'm trying to create a negative mitred buffer on a (simple) polygon > >>>> > >> with > >> > >>>> JTS 1.10, and I'm getting strange results very occasionally. For > >>>> example, the following code gives me an output geometry that > >>>> > > actually > > > >>>> extends outside the original geometry (even though a negative > >>>> > > buffer is > > > >>>> used). > >>>> > >>>> WKTReader wktReader = new WKTReader(); > >>>> String geom = "POLYGON ((588736.6028960398 4518922.914991864, > >>>> + "588736.1060708747 4518922.061957178, > >>>> 588718.6830715544 " > >>>> + "4518930.620699637, 588712.0102834741 > >>>> 4518933.8985304395, " > >>>> + "588722.7612465625 4518964.956739423, > >>>> 588755.2073151038 " > >>>> + "4518948.2420851765, 588750.2892019567 > >>>> 4518938.490656119, " > >>>> + "588750.2892047082 4518938.490654858, > >>>> 588741.1098934844 " > >>>> + "4518920.290260831, 588736.6028960398 > >>>> 4518922.914991864))"; > >>>> Geometry inputGeometry = wktReader.read(geom); > >>>> > >>>> BufferParameters bufferParameters = new BufferParameters(); > >>>> bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); > >>>> Geometry bufferedGeometry = BufferOp.bufferOp( > >>>> inputGeometry, -5.0, > >>>> bufferParameters); > >>>> > >>>> > >>>> > >>>> I've tried using a few different strategies in investigating > >>>> > > such > > > >>>> as reducing the coordinate precision, offsetting the x and/or y > >>>> coordinates by a constant offset, or iteratively buffering the > >>>> > > geometry > > > >>>> (for example, buffering it five times by -1.0). All of these > >>>> > > strategies > > > >>>> have had limited success, and none seem to work in all cases that > >>>> > > I'm > > > >>>> encountering. > >>>> > >>>> Does this situation spring out to anyone, or is there any advice > >>>> > > how > > > >>>> to get around this (or is this the expected behaviour for some > >>>> > >> reason?). > >> > >>>> I would be happy to *attempt* to fix this in JTS if someone can > >>>> > > point > > > >> me > >> > >>>> in the general direction of where the issue probably is. > >>>> > >>>> > >>>> Thanks in advance for any information, > >>>> > >>>> Gabriel Reid > >>>> _______________________________________________ > >>>> 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 > > > > > > -- > 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 |
In reply to this post by Gabriel Reid
why not simply disabling the simplification for negative buffer values.
that seems the easiest and fastest way? Or is there a real need for a speed improvement for negative buffers as well? stefan _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
No, the simplification *helped* in the case that I looked at. And for
the other cases, I'm pretty sure it's not the simplification which is causing the problem, it's the logic for generating the mitred offset curve. Stefan Steiniger wrote: > why not simply disabling the simplification for negative buffer values. > that seems the easiest and fastest way? Or is there a real need for a > speed improvement for negative buffers as well? > > stefan > > _______________________________________________ > 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 Gabriel Reid
Thanks for the test cases, Gabriel.
These errors are almost certainly caused by some shortcoming(s) in the algorithm for generating a mitred buffer offset curve. The errors seem to be linked to situations with almost flat angles - that might be part of the problem. Probably some further heuristics are needed to generate better quality offset curves in this case. Gabriel Reid wrote: > Hi Martin, > > I've got a few other failure cases here, showing what seems to be a few > different examples of this kind of behaviour: > > // Simple five-sided polygon that gets transformed into three triangles > POLYGON ((589300.089821923 4519627.577687806, 589296.6197410262 > 4519621.834087054, 589292.5450979208 4519615.089809029, > 589282.7894421419 4519620.983829066, 589289.8814929381 > 4519632.722288636, 589300.089821923 4519627.577687806)) > > // Another example of the same triangle behavior > POLYGON ((588978.2942617612 4519797.499233156, 588989.1612999197 > 4519792.050291001, 588982.5784094566 4519779.549041149, > 588962.0866377753 4519790.334848753, 588967.4026187821 > 4519802.960530801, 588978.2942617612 4519797.499233156)) > > // Resulting polygon has a single edge extending off one corner > POLYGON ((589099.8017397423 4518490.719003885, 589097.1198886324 > 4518486.20858194, 589090.9424687021 4518475.819013388, 589069.8993093553 > 4518487.1362185385, 589078.7377975255 4518502.093799692, > 589081.1515112884 4518509.334764771, 589103.7370954598 > 4518497.015419995, 589099.8017397423 4518490.719003885)) > > // Similar behaviour as the original case that was posted, this polygon > // has to points that are very close together > POLYGON ((587854.8616905196 4519121.941123185, 587863.6671614297 > 4519138.176489661, 587863.9386104685 4519138.676991724, > 587880.5408633598 4519129.672513268, 587871.463857397 > 4519112.9366913745, 587854.8616905196 4519121.941123185)) > > All of these examples can be demonstrated with the code that I posted > before (creating a mitred buffer with a magnitude of -5.0). > > Again, if you don't have time and/or motivation to look into this, I'd > be more than happy to attempt to assist in doing that, especially if you > have a good idea of where to look (I'm trying to have a look anyhow). > > > Thanks again for the assistance, > > Gabriel > > > >> -----Original Message----- >> From: [hidden email] [mailto:jts-devel- >> [hidden email]] On Behalf Of Martin Davis >> Sent: donderdag 26 februari 2009 17:50 >> To: JTS Topology Suite Development >> Subject: Re: [jts-devel] Odd behavior in negative mitred buffer >> >> Ok, Gabriel. It sounds like some progress, at least. >> >> Please post the other failure cases when you have isolated them. >> Perhaps the next problem will be as easy to solve as the last one... >> > 8^) > >> Gabriel Reid wrote: >> >>> Hi Martin, >>> >>> Thanks a lot for the quick support! >>> >>> I just tested this on the full dataset that I've been working with, >>> > and > >>> there are still some cases coming out; I'll try to isolate what the >>> situation is with those cases and see if there is a pattern (or if I >>> > can > >>> do something further with data cleaning). >>> >>> I'll keep you posted. >>> >>> >>> Gabriel >>> >>> >>> >>> >>>> -----Original Message----- >>>> From: [hidden email] [mailto:jts-devel- >>>> [hidden email]] On Behalf Of Martin Davis >>>> Sent: donderdag 26 februari 2009 2:22 >>>> To: JTS Topology Suite Development >>>> Subject: Re: [jts-devel] Odd behavior in negative mitred buffer >>>> >>>> Good news! I looked into this problem, and found a minor bug in >>>> > the > >>>> buffer input simplification algorithm. With this fix the situation >>>> >>>> >>> you >>> >>> >>>> provided is no longer a problem. >>>> >>>> This is commited to CVS. >>>> >>>> Can you try this out on to see if it solves the other problems you >>>> >>>> >>> have >>> >>> >>>> encountered? >>>> >>>> >>>> Martin Davis wrote: >>>> >>>> >>>>> This is probably due to some sort of limitation with the mitring >>>>> algorithm. However, I notice that the 7th and 8th points of your >>>>> geometry are almost identical. If I remove one of these, the >>>>> > mitred > >>>>> buffer looks fine. Can you clean the points of your geometries >>>>> somehow to avoid this situation? >>>>> >>>>> Gabriel Reid wrote: >>>>> >>>>> >>>>>> Hi, >>>>>> >>>>>> I'm trying to create a negative mitred buffer on a (simple) >>>>>> > polygon > >>>> with >>>> >>>> >>>>>> JTS 1.10, and I'm getting strange results very occasionally. For >>>>>> example, the following code gives me an output geometry that >>>>>> >>>>>> >>> actually >>> >>> >>>>>> extends outside the original geometry (even though a negative >>>>>> >>>>>> >>> buffer is >>> >>> >>>>>> used). >>>>>> >>>>>> WKTReader wktReader = new WKTReader(); >>>>>> String geom = "POLYGON ((588736.6028960398 4518922.914991864, >>>>>> > " > >>>>>> + "588736.1060708747 4518922.061957178, >>>>>> 588718.6830715544 " >>>>>> + "4518930.620699637, 588712.0102834741 >>>>>> 4518933.8985304395, " >>>>>> + "588722.7612465625 4518964.956739423, >>>>>> 588755.2073151038 " >>>>>> + "4518948.2420851765, 588750.2892019567 >>>>>> 4518938.490656119, " >>>>>> + "588750.2892047082 4518938.490654858, >>>>>> 588741.1098934844 " >>>>>> + "4518920.290260831, 588736.6028960398 >>>>>> 4518922.914991864))"; >>>>>> Geometry inputGeometry = wktReader.read(geom); >>>>>> >>>>>> BufferParameters bufferParameters = new BufferParameters(); >>>>>> bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); >>>>>> Geometry bufferedGeometry = BufferOp.bufferOp( >>>>>> inputGeometry, -5.0, >>>>>> bufferParameters); >>>>>> >>>>>> >>>>>> >>>>>> I've tried using a few different strategies in investigating >>>>>> > this, > >>> such >>> >>> >>>>>> as reducing the coordinate precision, offsetting the x and/or y >>>>>> coordinates by a constant offset, or iteratively buffering the >>>>>> >>>>>> >>> geometry >>> >>> >>>>>> (for example, buffering it five times by -1.0). All of these >>>>>> >>>>>> >>> strategies >>> >>> >>>>>> have had limited success, and none seem to work in all cases that >>>>>> >>>>>> >>> I'm >>> >>> >>>>>> encountering. >>>>>> >>>>>> Does this situation spring out to anyone, or is there any advice >>>>>> > on > >>> how >>> >>> >>>>>> to get around this (or is this the expected behaviour for some >>>>>> >>>>>> >>>> reason?). >>>> >>>> >>>>>> I would be happy to *attempt* to fix this in JTS if someone can >>>>>> >>>>>> >>> point >>> >>> >>>> me >>>> >>>> >>>>>> in the general direction of where the issue probably is. >>>>>> >>>>>> >>>>>> Thanks in advance for any information, >>>>>> >>>>>> Gabriel Reid >>>>>> _______________________________________________ >>>>>> 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 >>> >>> >>> >> -- >> 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 > > -- 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 Gabriel Reid
As I suspected, this problem was due to robustness issues in computing
mitred joins for almost parallel segments. I've commited a fix for this to CVS - it handles all the test cases that you provided. Let me know if you find any other issues. I'll look into building your test cases into the JTS Test Suite - it really needs some good testing for the various buffer styles. Martin Gabriel Reid wrote: > Hi Martin, > > I've got a few other failure cases here, showing what seems to be a few > different examples of this kind of behaviour: > > // Simple five-sided polygon that gets transformed into three triangles > POLYGON ((589300.089821923 4519627.577687806, 589296.6197410262 > 4519621.834087054, 589292.5450979208 4519615.089809029, > 589282.7894421419 4519620.983829066, 589289.8814929381 > 4519632.722288636, 589300.089821923 4519627.577687806)) > > // Another example of the same triangle behavior > POLYGON ((588978.2942617612 4519797.499233156, 588989.1612999197 > 4519792.050291001, 588982.5784094566 4519779.549041149, > 588962.0866377753 4519790.334848753, 588967.4026187821 > 4519802.960530801, 588978.2942617612 4519797.499233156)) > > // Resulting polygon has a single edge extending off one corner > POLYGON ((589099.8017397423 4518490.719003885, 589097.1198886324 > 4518486.20858194, 589090.9424687021 4518475.819013388, 589069.8993093553 > 4518487.1362185385, 589078.7377975255 4518502.093799692, > 589081.1515112884 4518509.334764771, 589103.7370954598 > 4518497.015419995, 589099.8017397423 4518490.719003885)) > > // Similar behaviour as the original case that was posted, this polygon > // has to points that are very close together > POLYGON ((587854.8616905196 4519121.941123185, 587863.6671614297 > 4519138.176489661, 587863.9386104685 4519138.676991724, > 587880.5408633598 4519129.672513268, 587871.463857397 > 4519112.9366913745, 587854.8616905196 4519121.941123185)) > > All of these examples can be demonstrated with the code that I posted > before (creating a mitred buffer with a magnitude of -5.0). > > Again, if you don't have time and/or motivation to look into this, I'd > be more than happy to attempt to assist in doing that, especially if you > have a good idea of where to look (I'm trying to have a look anyhow). > > > Thanks again for the assistance, > > Gabriel > > > >> -----Original Message----- >> From: [hidden email] [mailto:jts-devel- >> [hidden email]] On Behalf Of Martin Davis >> Sent: donderdag 26 februari 2009 17:50 >> To: JTS Topology Suite Development >> Subject: Re: [jts-devel] Odd behavior in negative mitred buffer >> >> Ok, Gabriel. It sounds like some progress, at least. >> >> Please post the other failure cases when you have isolated them. >> Perhaps the next problem will be as easy to solve as the last one... >> > 8^) > >> Gabriel Reid wrote: >> >>> Hi Martin, >>> >>> Thanks a lot for the quick support! >>> >>> I just tested this on the full dataset that I've been working with, >>> > and > >>> there are still some cases coming out; I'll try to isolate what the >>> situation is with those cases and see if there is a pattern (or if I >>> > can > >>> do something further with data cleaning). >>> >>> I'll keep you posted. >>> >>> >>> Gabriel >>> >>> >>> >>> >>>> -----Original Message----- >>>> From: [hidden email] [mailto:jts-devel- >>>> [hidden email]] On Behalf Of Martin Davis >>>> Sent: donderdag 26 februari 2009 2:22 >>>> To: JTS Topology Suite Development >>>> Subject: Re: [jts-devel] Odd behavior in negative mitred buffer >>>> >>>> Good news! I looked into this problem, and found a minor bug in >>>> > the > >>>> buffer input simplification algorithm. With this fix the situation >>>> >>>> >>> you >>> >>> >>>> provided is no longer a problem. >>>> >>>> This is commited to CVS. >>>> >>>> Can you try this out on to see if it solves the other problems you >>>> >>>> >>> have >>> >>> >>>> encountered? >>>> >>>> >>>> Martin Davis wrote: >>>> >>>> >>>>> This is probably due to some sort of limitation with the mitring >>>>> algorithm. However, I notice that the 7th and 8th points of your >>>>> geometry are almost identical. If I remove one of these, the >>>>> > mitred > >>>>> buffer looks fine. Can you clean the points of your geometries >>>>> somehow to avoid this situation? >>>>> >>>>> Gabriel Reid wrote: >>>>> >>>>> >>>>>> Hi, >>>>>> >>>>>> I'm trying to create a negative mitred buffer on a (simple) >>>>>> > polygon > >>>> with >>>> >>>> >>>>>> JTS 1.10, and I'm getting strange results very occasionally. For >>>>>> example, the following code gives me an output geometry that >>>>>> >>>>>> >>> actually >>> >>> >>>>>> extends outside the original geometry (even though a negative >>>>>> >>>>>> >>> buffer is >>> >>> >>>>>> used). >>>>>> >>>>>> WKTReader wktReader = new WKTReader(); >>>>>> String geom = "POLYGON ((588736.6028960398 4518922.914991864, >>>>>> > " > >>>>>> + "588736.1060708747 4518922.061957178, >>>>>> 588718.6830715544 " >>>>>> + "4518930.620699637, 588712.0102834741 >>>>>> 4518933.8985304395, " >>>>>> + "588722.7612465625 4518964.956739423, >>>>>> 588755.2073151038 " >>>>>> + "4518948.2420851765, 588750.2892019567 >>>>>> 4518938.490656119, " >>>>>> + "588750.2892047082 4518938.490654858, >>>>>> 588741.1098934844 " >>>>>> + "4518920.290260831, 588736.6028960398 >>>>>> 4518922.914991864))"; >>>>>> Geometry inputGeometry = wktReader.read(geom); >>>>>> >>>>>> BufferParameters bufferParameters = new BufferParameters(); >>>>>> bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); >>>>>> Geometry bufferedGeometry = BufferOp.bufferOp( >>>>>> inputGeometry, -5.0, >>>>>> bufferParameters); >>>>>> >>>>>> >>>>>> >>>>>> I've tried using a few different strategies in investigating >>>>>> > this, > >>> such >>> >>> >>>>>> as reducing the coordinate precision, offsetting the x and/or y >>>>>> coordinates by a constant offset, or iteratively buffering the >>>>>> >>>>>> >>> geometry >>> >>> >>>>>> (for example, buffering it five times by -1.0). All of these >>>>>> >>>>>> >>> strategies >>> >>> >>>>>> have had limited success, and none seem to work in all cases that >>>>>> >>>>>> >>> I'm >>> >>> >>>>>> encountering. >>>>>> >>>>>> Does this situation spring out to anyone, or is there any advice >>>>>> > on > >>> how >>> >>> >>>>>> to get around this (or is this the expected behaviour for some >>>>>> >>>>>> >>>> reason?). >>>> >>>> >>>>>> I would be happy to *attempt* to fix this in JTS if someone can >>>>>> >>>>>> >>> point >>> >>> >>>> me >>>> >>>> >>>>>> in the general direction of where the issue probably is. >>>>>> >>>>>> >>>>>> Thanks in advance for any information, >>>>>> >>>>>> Gabriel Reid >>>>>> _______________________________________________ >>>>>> 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 >>> >>> >>> >> -- >> 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 > > -- 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 |
Hi Martin,
I've run a few datasets through the latest code from CVS, and all appears to be ok. Thanks again for the quick support! If there's anything I can do to assist in building test cases, etc, please let me know. Regards, Gabriel > -----Original Message----- > From: [hidden email] [mailto:jts-devel- > [hidden email]] On Behalf Of Martin Davis > Sent: maandag 2 maart 2009 22:08 > To: JTS Topology Suite Development > Subject: Re: [jts-devel] Odd behavior in negative mitred buffer > > As I suspected, this problem was due to robustness issues in computing > mitred joins for almost parallel segments. I've commited a fix for this > to CVS - it handles all the test cases that you provided. > > Let me know if you find any other issues. > > I'll look into building your test cases into the JTS Test Suite - it > really needs some good testing for the various buffer styles. > > Martin > > Gabriel Reid wrote: > > Hi Martin, > > > > I've got a few other failure cases here, showing what seems to be a > > different examples of this kind of behaviour: > > > > // Simple five-sided polygon that gets transformed into three triangles > > POLYGON ((589300.089821923 4519627.577687806, 589296.6197410262 > > 4519621.834087054, 589292.5450979208 4519615.089809029, > > 589282.7894421419 4519620.983829066, 589289.8814929381 > > 4519632.722288636, 589300.089821923 4519627.577687806)) > > > > // Another example of the same triangle behavior > > POLYGON ((588978.2942617612 4519797.499233156, 588989.1612999197 > > 4519792.050291001, 588982.5784094566 4519779.549041149, > > 588962.0866377753 4519790.334848753, 588967.4026187821 > > 4519802.960530801, 588978.2942617612 4519797.499233156)) > > > > // Resulting polygon has a single edge extending off one corner > > POLYGON ((589099.8017397423 4518490.719003885, 589097.1198886324 > > 4518486.20858194, 589090.9424687021 4518475.819013388, > > 4518487.1362185385, 589078.7377975255 4518502.093799692, > > 589081.1515112884 4518509.334764771, 589103.7370954598 > > 4518497.015419995, 589099.8017397423 4518490.719003885)) > > > > // Similar behaviour as the original case that was posted, this polygon > > // has to points that are very close together > > POLYGON ((587854.8616905196 4519121.941123185, 587863.6671614297 > > 4519138.176489661, 587863.9386104685 4519138.676991724, > > 587880.5408633598 4519129.672513268, 587871.463857397 > > 4519112.9366913745, 587854.8616905196 4519121.941123185)) > > > > All of these examples can be demonstrated with the code that I posted > > before (creating a mitred buffer with a magnitude of -5.0). > > > > Again, if you don't have time and/or motivation to look into this, I'd > > be more than happy to attempt to assist in doing that, especially if you > > have a good idea of where to look (I'm trying to have a look anyhow). > > > > > > Thanks again for the assistance, > > > > Gabriel > > > > > > > >> -----Original Message----- > >> From: [hidden email] [mailto:jts-devel- > >> [hidden email]] On Behalf Of Martin Davis > >> Sent: donderdag 26 februari 2009 17:50 > >> To: JTS Topology Suite Development > >> Subject: Re: [jts-devel] Odd behavior in negative mitred buffer > >> > >> Ok, Gabriel. It sounds like some progress, at least. > >> > >> Please post the other failure cases when you have isolated them. > >> Perhaps the next problem will be as easy to solve as the last > >> > > 8^) > > > >> Gabriel Reid wrote: > >> > >>> Hi Martin, > >>> > >>> Thanks a lot for the quick support! > >>> > >>> I just tested this on the full dataset that I've been working > >>> > > and > > > >>> there are still some cases coming out; I'll try to isolate what the > >>> situation is with those cases and see if there is a pattern (or if I > >>> > > can > > > >>> do something further with data cleaning). > >>> > >>> I'll keep you posted. > >>> > >>> > >>> Gabriel > >>> > >>> > >>> > >>> > >>>> -----Original Message----- > >>>> From: [hidden email] [mailto:jts-devel- > >>>> [hidden email]] On Behalf Of Martin Davis > >>>> Sent: donderdag 26 februari 2009 2:22 > >>>> To: JTS Topology Suite Development > >>>> Subject: Re: [jts-devel] Odd behavior in negative mitred buffer > >>>> > >>>> Good news! I looked into this problem, and found a minor bug in > >>>> > > the > > > >>>> buffer input simplification algorithm. With this fix the > >>>> > >>>> > >>> you > >>> > >>> > >>>> provided is no longer a problem. > >>>> > >>>> This is commited to CVS. > >>>> > >>>> Can you try this out on to see if it solves the other problems > >>>> > >>>> > >>> have > >>> > >>> > >>>> encountered? > >>>> > >>>> > >>>> Martin Davis wrote: > >>>> > >>>> > >>>>> This is probably due to some sort of limitation with the mitring > >>>>> algorithm. However, I notice that the 7th and 8th points of > >>>>> geometry are almost identical. If I remove one of these, the > >>>>> > > mitred > > > >>>>> buffer looks fine. Can you clean the points of your geometries > >>>>> somehow to avoid this situation? > >>>>> > >>>>> Gabriel Reid wrote: > >>>>> > >>>>> > >>>>>> Hi, > >>>>>> > >>>>>> I'm trying to create a negative mitred buffer on a (simple) > >>>>>> > > polygon > > > >>>> with > >>>> > >>>> > >>>>>> JTS 1.10, and I'm getting strange results very occasionally. > >>>>>> example, the following code gives me an output geometry that > >>>>>> > >>>>>> > >>> actually > >>> > >>> > >>>>>> extends outside the original geometry (even though a negative > >>>>>> > >>>>>> > >>> buffer is > >>> > >>> > >>>>>> used). > >>>>>> > >>>>>> WKTReader wktReader = new WKTReader(); > >>>>>> String geom = "POLYGON ((588736.6028960398 > >>>>>> > > " > > > >>>>>> + "588736.1060708747 4518922.061957178, > >>>>>> 588718.6830715544 " > >>>>>> + "4518930.620699637, 588712.0102834741 > >>>>>> 4518933.8985304395, " > >>>>>> + "588722.7612465625 4518964.956739423, > >>>>>> 588755.2073151038 " > >>>>>> + "4518948.2420851765, 588750.2892019567 > >>>>>> 4518938.490656119, " > >>>>>> + "588750.2892047082 4518938.490654858, > >>>>>> 588741.1098934844 " > >>>>>> + "4518920.290260831, 588736.6028960398 > >>>>>> 4518922.914991864))"; > >>>>>> Geometry inputGeometry = wktReader.read(geom); > >>>>>> > >>>>>> BufferParameters bufferParameters = new BufferParameters(); > >>>>>> bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); > >>>>>> Geometry bufferedGeometry = BufferOp.bufferOp( > >>>>>> inputGeometry, -5.0, > >>>>>> bufferParameters); > >>>>>> > >>>>>> > >>>>>> > >>>>>> I've tried using a few different strategies in investigating > >>>>>> > > this, > > > >>> such > >>> > >>> > >>>>>> as reducing the coordinate precision, offsetting the x and/or y > >>>>>> coordinates by a constant offset, or iteratively buffering the > >>>>>> > >>>>>> > >>> geometry > >>> > >>> > >>>>>> (for example, buffering it five times by -1.0). All of these > >>>>>> > >>>>>> > >>> strategies > >>> > >>> > >>>>>> have had limited success, and none seem to work in all cases > >>>>>> > >>>>>> > >>> I'm > >>> > >>> > >>>>>> encountering. > >>>>>> > >>>>>> Does this situation spring out to anyone, or is there any advice > >>>>>> > > on > > > >>> how > >>> > >>> > >>>>>> to get around this (or is this the expected behaviour for some > >>>>>> > >>>>>> > >>>> reason?). > >>>> > >>>> > >>>>>> I would be happy to *attempt* to fix this in JTS if someone can > >>>>>> > >>>>>> > >>> point > >>> > >>> > >>>> me > >>>> > >>>> > >>>>>> in the general direction of where the issue probably is. > >>>>>> > >>>>>> > >>>>>> Thanks in advance for any information, > >>>>>> > >>>>>> Gabriel Reid > >>>>>> _______________________________________________ > >>>>>> 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 > >>> > >>> > >>> > >> -- > >> 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 > > > > > > -- > 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 |
In reply to this post by Martin Davis
Hi all -
I'm in the middle of trying to implement a shortest path routine using JTS 1.9. I looked into using some of JUMP's graph extension functions, but in the end I think it may be easier to use what's available in JTS. I've managed to work out a visibility algorithm based on Coordinates, Geometry obstacles and LineString paths, but now need to construct a graph so I can run a Dijkstra search (or A*). Essentially, I have a collection of Coordinates/Nodes, and LineStrings representing 'allowable' edges. What's the best way of creating a searchable graph from these objects? I looked at the PlanarGraph Class, and the LineMergeGraph subclass. I thought that LineMergeGraph was what I was after, but it seems to be missing the .add(Node) method that PlanarGraph has (even though it is supposed to extend PlanarGraph?). I need addNode, because it's possible to have a node with no connecting edges. Thanks in advance for your help with this, J _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Johnathan Kool wrote:
> I've managed to work out a visibility algorithm based on Coordinates, > Geometry obstacles and LineString paths, but now need to construct a graph > so I can run a Dijkstra search (or A*). Essentially, I have a collection of > Coordinates/Nodes, and LineStrings representing 'allowable' edges. What's > the best way of creating a searchable graph from these objects? Perhaps an external graph library is the best option. At least Jgrapht (http://www.jgrapht.org/) allows graphs with arbitrary edge and vertex classes. OTOH Jgrapht seems to only implement Dijkstra search - although I'm sure adding A* would be easy. _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
In reply to this post by Johnathan Kool
LineMergeGraph inherits the add(Node) method from PlanarGraph.
But I would look at using PlanarGraph, not LineMergeGraph. LMG is specifically intended for line merging, which is probably not what you're trying to do. If all you have is Coordinates and LineStrings, then you should be able to use PlanarGraph directly. If you have other data structures which model nodes and edges, you have two choices - implement a subclass of PlanarGraph to map the external structures into the inputs that PlanarGraph requires, or use the set/getUserData methods on LineString to "carry" your original objects. As for algorithms, have a look at ConnectedSubgraphFinder for an example of how to build an algorithm class. Johnathan Kool wrote: > Hi all - > > I'm in the middle of trying to implement a shortest path routine using JTS > 1.9. I looked into using some of JUMP's graph extension functions, but in > the end I think it may be easier to use what's available in JTS. > > I've managed to work out a visibility algorithm based on Coordinates, > Geometry obstacles and LineString paths, but now need to construct a graph > so I can run a Dijkstra search (or A*). Essentially, I have a collection of > Coordinates/Nodes, and LineStrings representing 'allowable' edges. What's > the best way of creating a searchable graph from these objects? > > I looked at the PlanarGraph Class, and the LineMergeGraph subclass. I > thought that LineMergeGraph was what I was after, but it seems to be missing > the .add(Node) method that PlanarGraph has (even though it is supposed to > extend PlanarGraph?). I need addNode, because it's possible to have a node > with no connecting edges. > > Thanks in advance for your help with this, > > J > > _______________________________________________ > 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 |