Odd behavior in negative mitred buffer

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

Odd behavior in negative mitred buffer

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

Re: Odd behavior in negative mitred buffer

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

RE: Odd behavior in negative mitred buffer

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

Re: Odd behavior in negative mitred buffer

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

Re: Odd behavior in negative mitred buffer

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

RE: Odd behavior in negative mitred buffer

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

Re: Odd behavior in negative mitred buffer

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

RE: Odd behavior in negative mitred buffer

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

Re: Odd behavior in negative mitred buffer

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

Re: Re: Odd behavior in negative mitred buffer

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

Re: Odd behavior in negative mitred buffer

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

Re: Odd behavior in negative mitred buffer

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

RE: Odd behavior in negative mitred buffer

Gabriel Reid
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
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
_______________________________________________
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

Proper construction of a search graph from geometric objects

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

Re: Proper construction of a search graph from geometric objects

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

Re: Proper construction of a search graph from geometric objects

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