## jts-topo-suite-user — JTS Users and Developers

You can subscribe to this list here.

 2009 2010 2011 2012 2013 2014 2015 2016 Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov (3) Dec Jan (30) Feb (41) Mar (69) Apr (131) May (67) Jun (24) Jul (28) Aug (52) Sep (9) Oct (24) Nov (36) Dec (24) Jan (20) Feb (53) Mar (31) Apr (74) May (71) Jun (51) Jul (28) Aug (91) Sep (72) Oct (46) Nov (90) Dec (38) Jan (80) Feb (77) Mar (98) Apr (78) May (56) Jun (85) Jul (53) Aug (87) Sep (74) Oct (67) Nov (85) Dec (66) Jan (50) Feb (34) Mar (45) Apr (36) May (22) Jun (10) Jul (30) Aug (39) Sep (25) Oct (11) Nov (64) Dec (42) Jan (27) Feb (6) Mar (10) Apr (14) May (25) Jun (6) Jul (25) Aug (3) Sep (22) Oct (12) Nov (34) Dec (15) Jan (24) Feb (20) Mar (11) Apr May (37) Jun (24) Jul (17) Aug (10) Sep (3) Oct (15) Nov (21) Dec (20) Jan (30) Feb (15) Mar Apr May Jun (1) Jul (20) Aug Sep (12) Oct (1) Nov (4) Dec
S M T W T F S

1
(3)
2
(2)
3

4

5

6

7

8
(6)
9
(7)
10
(3)
11
(3)
12

13
(4)
14
(2)
15
(1)
16
(3)
17
(4)
18
(4)
19

20

21

22
(6)
23
(3)
24
(2)
25

26

27

28

29

30
(2)
31
(1)

Showing results of 56

1 2 3 > >> (Page 1 of 3)
 [Jts-topo-suite-user] Bounding rectangle From: Brian Sanjeewa Rupasinghe - 2012-05-31 05:24:09 Attachments: Message as HTML ```Hi, I have an irregular polygon for which i need to calculate the bounding rectangle based on the orientation of the longest line. In other words, two orientation directions that are perpendicular to each other are known. Is there any simple logic to calculate this may be the logic similar to create Minimum Bounding rectangle? The method i thought is to draw two perpendicular lines on the orientation of longest line and its perpendicular on each vertex of the polygon and retain only the lines that do not intersect polygon. Then using line intersection, i will be able to calculate four corners of the bounding rectangle. Cheers, Brian. ```
 Re: [Jts-topo-suite-user] Union From: Sandro Santilli - 2012-05-30 10:45:49 ```On Wed, May 30, 2012 at 12:05:49PM +0200, Michael Kussmaul wrote: > Hi > > For my GIS application I union certain areas: E.g. riverbanks and lakes, so I can produce nice looking borders around water areas. But for this union process I loose information, because now riverbanks and lakes are merged and therefore only one entity. > > What I would like to do is: I want to find the intersecting lines and mark them special ("do not draw border") but so far I have not found an elegant way (except by doing an intersection and then manually go through each node of this intersection and look if I find it on the either of the two original polygons. if not found add the point to both polygons and mark it as well) > > Is there a better/easier way to do something like this? If draw oriented, why not drawing twice: first the union with no borders, and then only the borders of the original ? -- () Free GIS & Flash consultant/developer /\ http://strk.keybit.net/services.html -- what comes below this line is just spam, dont bother scrolling... still here ? ```
 [Jts-topo-suite-user] Union From: Michael Kussmaul - 2012-05-30 10:32:39 ```Hi For my GIS application I union certain areas: E.g. riverbanks and lakes, so I can produce nice looking borders around water areas. But for this union process I loose information, because now riverbanks and lakes are merged and therefore only one entity. What I would like to do is: I want to find the intersecting lines and mark them special ("do not draw border") but so far I have not found an elegant way (except by doing an intersection and then manually go through each node of this intersection and look if I find it on the either of the two original polygons. if not found add the point to both polygons and mark it as well) Is there a better/easier way to do something like this? ```
 Re: [Jts-topo-suite-user] Serialization of Prepared geometry? From: Martin Davis - 2012-05-24 04:50:04 ```Mark, Haven't had time to think about this. It shouldn't be hard to make PreparedGeometry serializable, though. Stay tuned! Martin On Wed, May 23, 2012 at 8:06 PM, Mark Coletti wrote: > On Thu, May 10, 2012 at 12:18 AM, Mark Coletti wrote: >> >> Are there plans afoot to make the various Prepared geometries >> Serializable?  I see via SVN that there's been some progress made on the >> Serialization front, so I'm hoping it's just a matter of time before these, >> too, are Serializable? > > > So that's a 'no', then?  :( > > Cheers! > > Mark > -- > mcoletti@... > > > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > ```
 Re: [Jts-topo-suite-user] Serialization of Prepared geometry? From: Mark Coletti - 2012-05-24 03:06:25 Attachments: Message as HTML ```On Thu, May 10, 2012 at 12:18 AM, Mark Coletti wrote: > Are there plans afoot to make the various Prepared geometries > Serializable? I see via SVN that there's been some progress made on the > Serialization front, so I'm hoping it's just a matter of time before these, > too, are Serializable? > So that's a 'no', then? :( Cheers! Mark -- mcoletti@... ```
 Re: [Jts-topo-suite-user] Polygon touch From: Martin Davis - 2012-05-23 20:21:16 ```The semantics of "touches" are explained in the JTS Javadoc: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/geom/Geometry.html#touches(com.vividsolutions.jts.geom.Geometry) In your case, the reason for the false result is that the interiors intersect. It depends what you mean by "touching" polygons. If you want to get a true result for the case you present, "intersects" will suffice. On Wed, May 23, 2012 at 11:54 AM, Brian Sanjeewa Rupasinghe wrote: > Hi, > > I have two polygons that touch each other by one point having (0,0) > as shown below. However, poly2 is inside poly1 > > Geometry poly1 = reader.read("POLYGON((0 0, 20 0, 20 10, 0 10, 0 0))"); > Geometry poly2 = reader.read("POLYGON((0 0, 10 2, 7 8, 2 8, 0 0))"); > > When i use boolean value poly1.touches(poly2), it gives false, could you > explain why? Any other method to catch touching polygons? > ```
 [Jts-topo-suite-user] Polygon touch From: Brian Sanjeewa Rupasinghe - 2012-05-23 18:54:44 Attachments: Message as HTML ```Hi, I have two polygons that touch each other by one point having (0,0) as shown below. However, poly2 is inside poly1 Geometry poly1 = reader.read("POLYGON((0 0, 20 0, 20 10, 0 10, 0 0))"); Geometry poly2 = reader.read("POLYGON((0 0, 10 2, 7 8, 2 8, 0 0))"); When i use boolean value *poly1.touches(poly2)*, it gives *false*, could you explain why? Any other method to catch touching polygons? Cheers Brian. ```
 Re: [Jts-topo-suite-user] Fwd: Point inside polygon (geo fence) From: Simon Greener - 2012-05-23 00:04:38 ```See Contains/Within for SpatiaLite at http://www.gaia-gis.it/gaia-sins/spatialite-sql-3.0.0.html#p12 S On Wed, 23 May 2012 05:07:07 +1000, Stefan Steiniger wrote: > well, then you should look for "SpatialLite" and what they have for > descriptions/guides. > > http://www.gaia-gis.it/gaia-sins/ > > A JTS guide comes also when you download it from: > http://sourceforge.net/projects/jts-topo-suite/files/jts/ > > hope that helps a bit. So I guess you need time to study that stuff > first. Maybe, on Spatiallite you could also find some blog entries etc. > > stefan > > Am 22.05.12 11:06, schrieb Imóveis Nacionais: >> Hi >> >> My database is SQLite. >> >> I am thinking to use JTS as a library. >> >> Like this: There is a thread listen to GSM modem. When a new SMS arrives >> the SMS contains a point in meters units. Then the thread call the JTS >> lib supplying a poligon and the point and the lib tells me in the point >> is inside or outside. Then the thread stores the pont in table of points >> and the inside/outside in other database table. It is just this. >> >> >> >> Please, tell me just how to create an JTS java object configured for >> coordinates in meters or degrees (the earth) and How do I use it passing >> a polygon and a point to find out if point is in or out polygon. >> >> Thanks a lot >> >> Alex >> >> >> >> ---------- Forwarded message ---------- >> From: *Imóveis Nacionais* > > >> Date: Tue, May 22, 2012 at 8:56 AM >> Subject: Re: Point inside polygon (geo fence) >> To: jts-topo-suite-user@... >> >> >> >> Hi, and thank you >> >> Data (polygons) is stored in a database. Points are comming/arriving >> through SMS or GPRS and I would like to test each point that ariives to >> the server to see if any point is outside fence (poligon) or not. If so, >> I fire an alarm (store it also in database) and user will see alarms >> when it access server (servlets) using browser >> >> Alex >> >> >> >> >> On Tue, May 22, 2012 at 1:00 AM, Imóveis Nacionais >> > wrote: >> >> I all, my first contact with JTS Topology Suite >> Please, I would like to execute the following client side code with >> similar code at server side, probably using JTS Topology Suite. >> Please, can you help me on this? My server side technology is servlets. >> >> I have a polygon and a point. I would like to find out if point is >> inside polygon or not. >> >> Here is the client side (openlayers) code: >> var lat=1.852; //in meters >> var longi=111.120 //in meters >> var p = new OpenLayers.Geometry.Point(longi, lat); >> ... >> if(map.layers[1].features[0].geometry.containsPoint && >> map.layers[1].features[0].geometry.containsPoint(p)) >> { >> alert('yes, point contained'); >> } >> else >> { >> alert('no, point not contained or containsPoint-method not defined'); >> } >> >> How to do the same with JTS Topology Suite? >> >> Thanks a lot >> Alex >> >> >> >> >> >> ------------------------------------------------------------------------------ >> Live Security Virtual Conference >> Exclusive live event will cover all the ways today's security and >> threat landscape has changed and how IT managers can respond. Discussions >> will include endpoint security, mobile security and the latest in malware >> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >> >> >> >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts-topo-suite-user@... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > -- Holder of "2011 Oracle Spatial Excellence Award for Education and Research." SpatialDB Advice and Design, Solutions Architecture and Programming, Oracle Database 10g Administrator Certified Associate; Oracle Database 10g SQL Certified Professional Oracle Spatial, SQL Server, PostGIS, MySQL, ArcSDE, Manifold GIS, FME, Radius Topology and Studio Specialist. 39 Cliff View Drive, Allens Rivulet, 7150, Tasmania, Australia. Website: http://www.spatialdbadvisor.com Email: simon@... Voice: +61 362 396397 Mobile: +61 418 396391 Skype: sggreener Longitude: 147.20515 (147° 12' 18" E) Latitude: -43.01530 (43° 00' 55" S) GeoHash: r22em9r98wg NAC:W80CK 7SWP3 ```
 Re: [Jts-topo-suite-user] Fwd: Point inside polygon (geo fence) From: Stefan Steiniger - 2012-05-22 19:07:36 ```well, then you should look for "SpatialLite" and what they have for descriptions/guides. http://www.gaia-gis.it/gaia-sins/ A JTS guide comes also when you download it from: http://sourceforge.net/projects/jts-topo-suite/files/jts/ hope that helps a bit. So I guess you need time to study that stuff first. Maybe, on Spatiallite you could also find some blog entries etc. stefan Am 22.05.12 11:06, schrieb Imóveis Nacionais: > Hi > > My database is SQLite. > > I am thinking to use JTS as a library. > > Like this: There is a thread listen to GSM modem. When a new SMS arrives > the SMS contains a point in meters units. Then the thread call the JTS > lib supplying a poligon and the point and the lib tells me in the point > is inside or outside. Then the thread stores the pont in table of points > and the inside/outside in other database table. It is just this. > > > > Please, tell me just how to create an JTS java object configured for > coordinates in meters or degrees (the earth) and How do I use it passing > a polygon and a point to find out if point is in or out polygon. > > Thanks a lot > > Alex > > > > ---------- Forwarded message ---------- > From: *Imóveis Nacionais* > > Date: Tue, May 22, 2012 at 8:56 AM > Subject: Re: Point inside polygon (geo fence) > To: jts-topo-suite-user@... > > > > Hi, and thank you > > Data (polygons) is stored in a database. Points are comming/arriving > through SMS or GPRS and I would like to test each point that ariives to > the server to see if any point is outside fence (poligon) or not. If so, > I fire an alarm (store it also in database) and user will see alarms > when it access server (servlets) using browser > > Alex > > > > > On Tue, May 22, 2012 at 1:00 AM, Imóveis Nacionais > > wrote: > > I all, my first contact with JTS Topology Suite > Please, I would like to execute the following client side code with > similar code at server side, probably using JTS Topology Suite. > Please, can you help me on this? My server side technology is servlets. > > I have a polygon and a point. I would like to find out if point is > inside polygon or not. > > Here is the client side (openlayers) code: > var lat=1.852; //in meters > var longi=111.120 //in meters > var p = new OpenLayers.Geometry.Point(longi, lat); > ... > if(map.layers[1].features[0].geometry.containsPoint && > map.layers[1].features[0].geometry.containsPoint(p)) > { > alert('yes, point contained'); > } > else > { > alert('no, point not contained or containsPoint-method not defined'); > } > > How to do the same with JTS Topology Suite? > > Thanks a lot > Alex > > > > > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user ```
 [Jts-topo-suite-user] Fwd: Point inside polygon (geo fence) From: Imóveis Nacionais - 2012-05-22 15:07:05 Attachments: Message as HTML ```Hi My database is SQLite. I am thinking to use JTS as a library. Like this: There is a thread listen to GSM modem. When a new SMS arrives the SMS contains a point in meters units. Then the thread call the JTS lib supplying a poligon and the point and the lib tells me in the point is inside or outside. Then the thread stores the pont in table of points and the inside/outside in other database table. It is just this. Please, tell me just how to create an JTS java object configured for coordinates in meters or degrees (the earth) and How do I use it passing a polygon and a point to find out if point is in or out polygon. Thanks a lot Alex ---------- Forwarded message ---------- From: Imóveis Nacionais Date: Tue, May 22, 2012 at 8:56 AM Subject: Re: Point inside polygon (geo fence) To: jts-topo-suite-user@... Hi, and thank you Data (polygons) is stored in a database. Points are comming/arriving through SMS or GPRS and I would like to test each point that ariives to the server to see if any point is outside fence (poligon) or not. If so, I fire an alarm (store it also in database) and user will see alarms when it access server (servlets) using browser Alex On Tue, May 22, 2012 at 1:00 AM, Imóveis Nacionais < imoveisnacionais@...> wrote: > I all, my first contact with JTS Topology Suite > Please, I would like to execute the following client side code with > similar code at server side, probably using JTS Topology Suite. Please, > can you help me on this? My server side technology is servlets. > > I have a polygon and a point. I would like to find out if point is inside > polygon or not. > > Here is the client side (openlayers) code: > var lat=1.852; //in meters > var longi=111.120 //in meters > var p = new OpenLayers.Geometry.Point(longi, lat); > ... > if(map.layers[1].features[0].geometry.containsPoint && > map.layers[1].features[0].geometry.containsPoint(p)) > { > alert('yes, point contained'); > } > else > { > alert('no, point not contained or containsPoint-method not defined'); > } > > How to do the same with JTS Topology Suite? > > Thanks a lot > Alex > ```
 Re: [Jts-topo-suite-user] Point inside polygon (geo fence) From: Stefan Steiniger - 2012-05-22 14:49:32 ```Hi Imóveis, sounds like you would do that directly in your database? in that case the question is, what is your databases and does your database support spatial functions. MySQL and PostGreSQL can do that, for instance. So you would need to look at how to do that in your database. Other options are possible too. But as Martin said your data handling (loading, storing, etc.) is out of Scope of JTS. JTS is only for processing (spatial) data, i.e. it is a library and not a program. I am not sure how complex your application is, but your short description sounds a bit like what is called a Sensor Service? So you could maybe look into Deegree or GeoServer or on the N52 North page - I think they both have support for sensor service standards now. cheers, stefan Am 22.05.12 03:56, schrieb Imóveis Nacionais: > Hi, and thank you > > Data (polygons) is stored in a database. Points are comming/arriving > through SMS or GPRS and I would like to test each point that ariives to > the server to see if any point is outside fence (poligon) or not. If so, > I fire an alarm (store it also in database) and user will see alarms > when it access server (servlets) using browser > > Alex > > > > > On Tue, May 22, 2012 at 1:00 AM, Imóveis Nacionais > > wrote: > > I all, my first contact with JTS Topology Suite > Please, I would like to execute the following client side code with > similar code at server side, probably using JTS Topology Suite. > Please, can you help me on this? My server side technology is servlets. > > I have a polygon and a point. I would like to find out if point is > inside polygon or not. > > Here is the client side (openlayers) code: > var lat=1.852; //in meters > var longi=111.120 //in meters > var p = new OpenLayers.Geometry.Point(longi, lat); > ... > if(map.layers[1].features[0].geometry.containsPoint && > map.layers[1].features[0].geometry.containsPoint(p)) > { > alert('yes, point contained'); > } > else > { > alert('no, point not contained or containsPoint-method not defined'); > } > > How to do the same with JTS Topology Suite? > > Thanks a lot > Alex > > > > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user ```
 Re: [Jts-topo-suite-user] Point inside polygon (geo fence) From: Imóveis Nacionais - 2012-05-22 07:56:17 Attachments: Message as HTML ```Hi, and thank you Data (polygons) is stored in a database. Points are comming/arriving through SMS or GPRS and I would like to test each point that ariives to the server to see if any point is outside fence (poligon) or not. If so, I fire an alarm (store it also in database) and user will see alarms when it access server (servlets) using browser Alex On Tue, May 22, 2012 at 1:00 AM, Imóveis Nacionais < imoveisnacionais@...> wrote: > I all, my first contact with JTS Topology Suite > Please, I would like to execute the following client side code with > similar code at server side, probably using JTS Topology Suite. Please, > can you help me on this? My server side technology is servlets. > > I have a polygon and a point. I would like to find out if point is inside > polygon or not. > > Here is the client side (openlayers) code: > var lat=1.852; //in meters > var longi=111.120 //in meters > var p = new OpenLayers.Geometry.Point(longi, lat); > ... > if(map.layers[1].features[0].geometry.containsPoint && > map.layers[1].features[0].geometry.containsPoint(p)) > { > alert('yes, point contained'); > } > else > { > alert('no, point not contained or containsPoint-method not defined'); > } > > How to do the same with JTS Topology Suite? > > Thanks a lot > Alex > ```
 Re: [Jts-topo-suite-user] Point inside polygon (geo fence) From: Martin Davis - 2012-05-22 03:52:23 Attachments: Message as HTML ```The simple part of the answer is the JTS part. If you have a Point and a Polygon, then all you have to do to test containment is: if (poly.contains(point)) { ... } If you are looking for advice on a complete solution, then that's more complex, since it depends on where you are obtaining your data. Without knowing more about this it's hard to give advice - and in any case, this is really out of the scope of JTS. On 5/21/2012 5:00 PM, Imóveis Nacionais wrote: > I all, my first contact with JTS Topology Suite > Please, I would like to execute the following client side code with > similar code at server side, probably using JTS Topology Suite. > Please, can you help me on this? My server side technology is servlets. > > I have a polygon and a point. I would like to find out if point is > inside polygon or not. > > Here is the client side (openlayers) code: > var lat=1.852; //in meters > var longi=111.120 //in meters > var p = new OpenLayers.Geometry.Point(longi, lat); > ... > if(map.layers[1].features[0].geometry.containsPoint && > map.layers[1].features[0].geometry.containsPoint(p)) > { > alert('yes, point contained'); > } > else > { > alert('no, point not contained or containsPoint-method not defined'); > } > > How to do the same with JTS Topology Suite? > ```
 [Jts-topo-suite-user] Point inside polygon (geo fence) From: Imóveis Nacionais - 2012-05-22 00:00:11 Attachments: Message as HTML ```I all, my first contact with JTS Topology Suite Please, I would like to execute the following client side code with similar code at server side, probably using JTS Topology Suite. Please, can you help me on this? My server side technology is servlets. I have a polygon and a point. I would like to find out if point is inside polygon or not. Here is the client side (openlayers) code: var lat=1.852; //in meters var longi=111.120 //in meters var p = new OpenLayers.Geometry.Point(longi, lat); ... if(map.layers[1].features[0].geometry.containsPoint && map.layers[1].features[0].geometry.containsPoint(p)) { alert('yes, point contained'); } else { alert('no, point not contained or containsPoint-method not defined'); } How to do the same with JTS Topology Suite? Thanks a lot Alex ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Martin Davis - 2012-05-18 16:43:59 ```On Fri, May 18, 2012 at 6:16 AM, Tomas Fa wrote: > > > On Thu, May 17, 2012 at 6:44 PM, Martin Davis wrote: >> >> I'm aware of his work, but have no experience with implementing it or >> using it.  It looks like it might be a bit complex to implement in >> Java. >> >> >> I did some experimenting with implementing an orientation test >> combining a fast filter with a fallback of the DD orientation code. >> It worked for all my current failure cases - but not for your simple >> case!  Or at least, the fast, direct double-precision code returned a >> value of 0 for your case, whereas the DD code returned 1 (not >> collinear). >> >> Now, what's puzzling is that if you treat the provided numbers as true >> reals, 0 is the correct result! (as can be seen by scaling the numbers >> by 10, to make them exact).   My only explanation for why the DD and >> RD code return something else (with varying results in the case of the >> RD code) is that they are working with an exact 64=bit unrounded >> representation of the real numbers (which are only approximations to >> the true value).  Whereas the simple FP code is using rounding, which >> in this case is the right thing to do. > > > Your explanation sounds reasonable to me. >> >> >> >> My takeaway from this is that your suggestion of using rounding in >> situations where a fixed precision is being used is a good approach. >> In the case of snap-rounding, this should not be an issue, because as >> long as a node is within the precision tolerance of a segment (ie the >> segment intersects a hot pixel), the segment should be noded.  So >> really I think there is a bug in the GeometryNoder code - it should >> not be so affected by discrepancies at such high-precision. > > > Interesting. I will try to look deeper into this. That would be great if you can identify where the problem is. My hunch is that it should be fairly easy to fix, since it is really how snap-rounding is intended to work. > >> >> >> This still doesn't provide a solution for computing accurate >> orientation values when using a FLOATING precision model (when the >> issues discussed above are still effect).  In fact, there may be no >> real solution to this, since it depends on how the binary >> representation of decimal numbers is interpreted.  This is one more >> example that reinforces my hypothesis that the only way to get fully >> robust operations is to use snap-rounding (and thus some >> fixed-precision model). > > > Yes, I have recently come to the same conclusion.  I wonder why no one > teached me that at school... There are many things they don't teach us at school... 8^) ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Martin Davis - 2012-05-18 16:07:53 ```I don't know that this is the case for Java. AFAIK it is still Java standard that it uses IEEE-754 across all platforms. Thank goodness - it's hard enough debugging numerical issues without standing in a swamp as well... On Fri, May 18, 2012 at 12:41 AM, Sandro Santilli wrote: > On Thu, May 17, 2012 at 04:42:17PM -0400, Stefan Steiniger wrote: >> Not that I really contribution to the fact nor fully understand what it >> is about, but I just want to link to that paper by Ince et al. (Nature, >> 2o11): The case for open computer programs [1] >> >> its section: "Errors exist within ‘perfect’ descriptions" >> >> and the quote (from Monniaux): >> >> ‘‘More subtly, on some platforms, the exact same expression, with the >> same values in the same variables, and the same compiler, can be >> evaluated to different results, depending on seemingly irrelevant >> statements (print- ing debugging information or other constructs that do >> not openly change the values of variables).’’ > > Hey, I know this very very well, experiencing it a lot with GEOS, but dunno > why I was convinced this wasn't true for JAVA ? > It'll feel less lonely if it is :) > ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Tomas Fa - 2012-05-18 13:16:36 Attachments: Message as HTML ```On Thu, May 17, 2012 at 6:44 PM, Martin Davis wrote: > I'm aware of his work, but have no experience with implementing it or > using it. It looks like it might be a bit complex to implement in > Java. > I did some experimenting with implementing an orientation test > combining a fast filter with a fallback of the DD orientation code. > It worked for all my current failure cases - but not for your simple > case! Or at least, the fast, direct double-precision code returned a > value of 0 for your case, whereas the DD code returned 1 (not > collinear). > > Now, what's puzzling is that if you treat the provided numbers as true > reals, 0 is the correct result! (as can be seen by scaling the numbers > by 10, to make them exact). My only explanation for why the DD and > RD code return something else (with varying results in the case of the > RD code) is that they are working with an exact 64=bit unrounded > representation of the real numbers (which are only approximations to > the true value). Whereas the simple FP code is using rounding, which > in this case is the right thing to do. > Your explanation sounds reasonable to me. > > My takeaway from this is that your suggestion of using rounding in > situations where a fixed precision is being used is a good approach. > In the case of snap-rounding, this should not be an issue, because as > long as a node is within the precision tolerance of a segment (ie the > segment intersects a hot pixel), the segment should be noded. So > really I think there is a bug in the GeometryNoder code - it should > not be so affected by discrepancies at such high-precision. > Interesting. I will try to look deeper into this. > > This still doesn't provide a solution for computing accurate > orientation values when using a FLOATING precision model (when the > issues discussed above are still effect). In fact, there may be no > real solution to this, since it depends on how the binary > representation of decimal numbers is interpreted. This is one more > example that reinforces my hypothesis that the only way to get fully > robust operations is to use snap-rounding (and thus some > fixed-precision model). > Yes, I have recently come to the same conclusion. I wonder why no one teached me that at school... /Tomas > > On Thu, May 17, 2012 at 12:29 AM, Tomas Fa wrote: > > Thanks. > > Do you have experience of, or opinions about, Shewchuks algorithm for > robust > > sign of determinants? (http://www.cs.cmu.edu/~quake/robust.html) > > > > /Tomas > > > > On Wed, May 16, 2012 at 10:53 PM, Martin Davis > wrote: > >> > >> Yes, it looks like you've run into a robustness failure with the > >> (supposedly) RobustDeterminant algorithm. There's a few of those that > have > >> cropped up - although none with as low precision as your case. Clearly > >> the RobustDeterminant code is not in fact 100% robust, contrary to the > >> advertising! > >> > >> > >> > http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup > >> > >> I'm reluctant to go in and mess with the RobustDeterminant algorithm, > >> since it's pretty complex and obviously critical to get right. The > idea of > >> rounding might work for your case, but the other failure cases occur > with > >> full FP precision, so it's not going to fix them. > >> > >> Another possibility is to use another method for computing determinant > >> sign. The DoubleDouble arithmetic now in JTS seems to provide enough > >> precision to handle this, but it's slow. Combining it with a fast > filter > >> might be the way to go. It might even be possible to compute the filter > >> using a combination of basic double-precision determinant evaluations, > which > >> would be as faster or faster than the current algorithm. > >> > >> This is going to take some careful experimentation, however - there is a > >> large risk for getting this wrong. > >> > >> > >> On Tue, May 15, 2012 at 5:40 AM, Tomas Fa wrote: > >>> > >>> I think that the problem lies in the RobustDeterminant. I think that > the > >>> RobustDeterminant would be more > >>> robust if it was using a fixed PrecisionModel (in a context where a > fixed > >>> precision is used). Currently, it is > >>> impossible, as far as I know ,to specify a precisionModel for > >>> CGAlgorithms, but I think it would be desirable. > >>> You can provide a MCIndexSnapRounder with a PrecisionModel, but it > >>> doesn't use it when CGAlgorithms > >>> gets involved (which it gets because of the line intersection > >>> operations). In the following program > >>> CGAlgorithms fails to behave consistently: > >>> > >> > >> > >> > ------------------------------------------------------------------------------ > >> Live Security Virtual Conference > >> Exclusive live event will cover all the ways today's security and > >> threat landscape has changed and how IT managers can respond. > Discussions > >> will include endpoint security, mobile security and the latest in > malware > >> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > >> _______________________________________________ > >> Jts-topo-suite-user mailing list > >> Jts-topo-suite-user@... > >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > >> > > > ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Sandro Santilli - 2012-05-18 07:41:59 ```On Thu, May 17, 2012 at 04:42:17PM -0400, Stefan Steiniger wrote: > Not that I really contribution to the fact nor fully understand what it > is about, but I just want to link to that paper by Ince et al. (Nature, > 2o11): The case for open computer programs [1] > > its section: "Errors exist within ‘perfect’ descriptions" > > and the quote (from Monniaux): > > ‘‘More subtly, on some platforms, the exact same expression, with the > same values in the same variables, and the same compiler, can be > evaluated to different results, depending on seemingly irrelevant > statements (print- ing debugging information or other constructs that do > not openly change the values of variables).’’ Hey, I know this very very well, experiencing it a lot with GEOS, but dunno why I was convinced this wasn't true for JAVA ? It'll feel less lonely if it is :) -- () Free GIS & Flash consultant/developer /\ http://strk.keybit.net/services.html -- what comes below this line is just spam, dont bother scrolling... still here ? ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Martin Davis - 2012-05-17 21:23:09 ```Great reference, Stefan! I'm not sure it offers much guidance on the robust orientation problem, but it sure makes me feel good about being part of the open source software world! Martin On Thu, May 17, 2012 at 1:42 PM, Stefan Steiniger wrote: > Not that I really contribution to the fact nor fully understand what it > is about, but I just want to link to that paper by Ince et al. (Nature, > 2o11): The case for open computer programs [1] > > its section: "Errors exist within ‘perfect’ descriptions" > > and the quote (from Monniaux): > > ‘‘More subtly, on some platforms, the exact same expression, with the > same values in the same variables, and the same compiler, can be > evaluated to different results, depending on seemingly irrelevant > statements (print- ing debugging information or other constructs that do > not openly change the values of variables).’’ > > (by Monniaux,D. The pitfalls of verifying floating-point computations. > ACM Trans. Programming Languages Systems 30 (3), 1–41 (2008). > > read this was really enlightening.. (at least I can blame someone ;) > cheers, > stefan > > [1] one of the links should work for download: > http://scholar.google.ca/scholar?cluster=6783031770567216058&hl=en&as_sdt=0,5 > e.g.: http://www.runmycode.org/data/MetaSite/upload/nature10836.pdf > > PS: how about implementing 3/4 versions and picking the "majority" > result? (which of course doesn't make it fast) > > Am 17.05.12 12:44, schrieb Martin Davis: >> I'm aware of his work, but have no experience with implementing it or >> using it.  It looks like it might be a bit complex to implement in >> Java. >> >> I did some experimenting with implementing an orientation test >> combining a fast filter with a fallback of the DD orientation code. >> It worked for all my current failure cases - but not for your simple >> case!  Or at least, the fast, direct double-precision code returned a >> value of 0 for your case, whereas the DD code returned 1 (not >> collinear). >> >> Now, what's puzzling is that if you treat the provided numbers as true >> reals, 0 is the correct result! (as can be seen by scaling the numbers >> by 10, to make them exact).   My only explanation for why the DD and >> RD code return something else (with varying results in the case of the >> RD code) is that they are working with an exact 64=bit unrounded >> representation of the real numbers (which are only approximations to >> the true value).  Whereas the simple FP code is using rounding, which >> in this case is the right thing to do. >> >> My takeaway from this is that your suggestion of using rounding in >> situations where a fixed precision is being used is a good approach. >> In the case of snap-rounding, this should not be an issue, because as >> long as a node is within the precision tolerance of a segment (ie the >> segment intersects a hot pixel), the segment should be noded.  So >> really I think there is a bug in the GeometryNoder code - it should >> not be so affected by discrepancies at such high-precision. >> >> This still doesn't provide a solution for computing accurate >> orientation values when using a FLOATING precision model (when the >> issues discussed above are still effect).  In fact, there may be no >> real solution to this, since it depends on how the binary >> representation of decimal numbers is interpreted.  This is one more >> example that reinforces my hypothesis that the only way to get fully >> robust operations is to use snap-rounding (and thus some >> fixed-precision model). >> >> On Thu, May 17, 2012 at 12:29 AM, Tomas Fa  wrote: >>> Thanks. >>> Do you have experience of, or opinions about, Shewchuks algorithm for robust >>> sign of determinants? (http://www.cs.cmu.edu/~quake/robust.html) >>> >>> /Tomas >>> >>> On Wed, May 16, 2012 at 10:53 PM, Martin Davis  wrote: >>>> >>>> Yes, it looks like you've run into a robustness failure with the >>>> (supposedly) RobustDeterminant algorithm.  There's a few of those that have >>>> cropped up - although none with as low precision as your case.  Clearly >>>> the RobustDeterminant code is not in fact 100% robust, contrary to the >>>> advertising! >>>> >>>> >>>> http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup >>>> >>>> I'm reluctant to go in and mess with the RobustDeterminant algorithm, >>>> since it's pretty complex and obviously critical to get right.  The idea of >>>> rounding might work for your case, but the other failure cases occur with >>>> full FP precision, so it's not going to fix them. >>>> >>>> Another possibility is to use another method for computing determinant >>>> sign.  The DoubleDouble arithmetic now in JTS seems to provide enough >>>> precision to handle this, but it's slow.  Combining it with a fast filter >>>> might be the way to go. It might even be possible to compute the filter >>>> using a combination of basic double-precision determinant evaluations, which >>>> would be as faster or faster than the current algorithm. >>>> >>>> This is going to take some careful experimentation, however - there is a >>>> large risk for getting this wrong. >>>> >>>> >>>> On Tue, May 15, 2012 at 5:40 AM, Tomas Fa  wrote: >>>>> >>>>> I think that the problem lies in the RobustDeterminant. I think that the >>>>> RobustDeterminant would be more >>>>> robust if it was using a fixed PrecisionModel (in a context where a fixed >>>>> precision is used). Currently, it is >>>>> impossible, as far as I know ,to specify a precisionModel for >>>>> CGAlgorithms, but I think it would be desirable. >>>>> You can provide a MCIndexSnapRounder with a PrecisionModel, but it >>>>> doesn't use it when CGAlgorithms >>>>> gets involved (which it gets because of the line intersection >>>>> operations). In the following program >>>>> CGAlgorithms fails to behave consistently: >>>>> >>>> >>>> >>>> ------------------------------------------------------------------------------ >>>> Live Security Virtual Conference >>>> Exclusive live event will cover all the ways today's security and >>>> threat landscape has changed and how IT managers can respond. Discussions >>>> will include endpoint security, mobile security and the latest in malware >>>> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >>>> _______________________________________________ >>>> Jts-topo-suite-user mailing list >>>> Jts-topo-suite-user@... >>>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >>>> >>> >> >> ------------------------------------------------------------------------------ >> Live Security Virtual Conference >> Exclusive live event will cover all the ways today's security and >> threat landscape has changed and how IT managers can respond. Discussions >> will include endpoint security, mobile security and the latest in malware >> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts-topo-suite-user@... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Stefan Steiniger - 2012-05-17 20:42:40 ```Not that I really contribution to the fact nor fully understand what it is about, but I just want to link to that paper by Ince et al. (Nature, 2o11): The case for open computer programs [1] its section: "Errors exist within ‘perfect’ descriptions" and the quote (from Monniaux): ‘‘More subtly, on some platforms, the exact same expression, with the same values in the same variables, and the same compiler, can be evaluated to different results, depending on seemingly irrelevant statements (print- ing debugging information or other constructs that do not openly change the values of variables).’’ (by Monniaux,D. The pitfalls of verifying floating-point computations. ACM Trans. Programming Languages Systems 30 (3), 1–41 (2008). read this was really enlightening.. (at least I can blame someone ;) cheers, stefan [1] one of the links should work for download: http://scholar.google.ca/scholar?cluster=6783031770567216058&hl=en&as_sdt=0,5 e.g.: http://www.runmycode.org/data/MetaSite/upload/nature10836.pdf PS: how about implementing 3/4 versions and picking the "majority" result? (which of course doesn't make it fast) Am 17.05.12 12:44, schrieb Martin Davis: > I'm aware of his work, but have no experience with implementing it or > using it. It looks like it might be a bit complex to implement in > Java. > > I did some experimenting with implementing an orientation test > combining a fast filter with a fallback of the DD orientation code. > It worked for all my current failure cases - but not for your simple > case! Or at least, the fast, direct double-precision code returned a > value of 0 for your case, whereas the DD code returned 1 (not > collinear). > > Now, what's puzzling is that if you treat the provided numbers as true > reals, 0 is the correct result! (as can be seen by scaling the numbers > by 10, to make them exact). My only explanation for why the DD and > RD code return something else (with varying results in the case of the > RD code) is that they are working with an exact 64=bit unrounded > representation of the real numbers (which are only approximations to > the true value). Whereas the simple FP code is using rounding, which > in this case is the right thing to do. > > My takeaway from this is that your suggestion of using rounding in > situations where a fixed precision is being used is a good approach. > In the case of snap-rounding, this should not be an issue, because as > long as a node is within the precision tolerance of a segment (ie the > segment intersects a hot pixel), the segment should be noded. So > really I think there is a bug in the GeometryNoder code - it should > not be so affected by discrepancies at such high-precision. > > This still doesn't provide a solution for computing accurate > orientation values when using a FLOATING precision model (when the > issues discussed above are still effect). In fact, there may be no > real solution to this, since it depends on how the binary > representation of decimal numbers is interpreted. This is one more > example that reinforces my hypothesis that the only way to get fully > robust operations is to use snap-rounding (and thus some > fixed-precision model). > > On Thu, May 17, 2012 at 12:29 AM, Tomas Fa wrote: >> Thanks. >> Do you have experience of, or opinions about, Shewchuks algorithm for robust >> sign of determinants? (http://www.cs.cmu.edu/~quake/robust.html) >> >> /Tomas >> >> On Wed, May 16, 2012 at 10:53 PM, Martin Davis wrote: >>> >>> Yes, it looks like you've run into a robustness failure with the >>> (supposedly) RobustDeterminant algorithm. There's a few of those that have >>> cropped up - although none with as low precision as your case. Clearly >>> the RobustDeterminant code is not in fact 100% robust, contrary to the >>> advertising! >>> >>> >>> http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup >>> >>> I'm reluctant to go in and mess with the RobustDeterminant algorithm, >>> since it's pretty complex and obviously critical to get right. The idea of >>> rounding might work for your case, but the other failure cases occur with >>> full FP precision, so it's not going to fix them. >>> >>> Another possibility is to use another method for computing determinant >>> sign. The DoubleDouble arithmetic now in JTS seems to provide enough >>> precision to handle this, but it's slow. Combining it with a fast filter >>> might be the way to go. It might even be possible to compute the filter >>> using a combination of basic double-precision determinant evaluations, which >>> would be as faster or faster than the current algorithm. >>> >>> This is going to take some careful experimentation, however - there is a >>> large risk for getting this wrong. >>> >>> >>> On Tue, May 15, 2012 at 5:40 AM, Tomas Fa wrote: >>>> >>>> I think that the problem lies in the RobustDeterminant. I think that the >>>> RobustDeterminant would be more >>>> robust if it was using a fixed PrecisionModel (in a context where a fixed >>>> precision is used). Currently, it is >>>> impossible, as far as I know ,to specify a precisionModel for >>>> CGAlgorithms, but I think it would be desirable. >>>> You can provide a MCIndexSnapRounder with a PrecisionModel, but it >>>> doesn't use it when CGAlgorithms >>>> gets involved (which it gets because of the line intersection >>>> operations). In the following program >>>> CGAlgorithms fails to behave consistently: >>>> >>> >>> >>> ------------------------------------------------------------------------------ >>> Live Security Virtual Conference >>> Exclusive live event will cover all the ways today's security and >>> threat landscape has changed and how IT managers can respond. Discussions >>> will include endpoint security, mobile security and the latest in malware >>> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >>> _______________________________________________ >>> Jts-topo-suite-user mailing list >>> Jts-topo-suite-user@... >>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >>> >> > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Martin Davis - 2012-05-17 16:44:52 ```I'm aware of his work, but have no experience with implementing it or using it. It looks like it might be a bit complex to implement in Java. I did some experimenting with implementing an orientation test combining a fast filter with a fallback of the DD orientation code. It worked for all my current failure cases - but not for your simple case! Or at least, the fast, direct double-precision code returned a value of 0 for your case, whereas the DD code returned 1 (not collinear). Now, what's puzzling is that if you treat the provided numbers as true reals, 0 is the correct result! (as can be seen by scaling the numbers by 10, to make them exact). My only explanation for why the DD and RD code return something else (with varying results in the case of the RD code) is that they are working with an exact 64=bit unrounded representation of the real numbers (which are only approximations to the true value). Whereas the simple FP code is using rounding, which in this case is the right thing to do. My takeaway from this is that your suggestion of using rounding in situations where a fixed precision is being used is a good approach. In the case of snap-rounding, this should not be an issue, because as long as a node is within the precision tolerance of a segment (ie the segment intersects a hot pixel), the segment should be noded. So really I think there is a bug in the GeometryNoder code - it should not be so affected by discrepancies at such high-precision. This still doesn't provide a solution for computing accurate orientation values when using a FLOATING precision model (when the issues discussed above are still effect). In fact, there may be no real solution to this, since it depends on how the binary representation of decimal numbers is interpreted. This is one more example that reinforces my hypothesis that the only way to get fully robust operations is to use snap-rounding (and thus some fixed-precision model). On Thu, May 17, 2012 at 12:29 AM, Tomas Fa wrote: > Thanks. > Do you have experience of, or opinions about, Shewchuks algorithm for robust > sign of determinants? (http://www.cs.cmu.edu/~quake/robust.html) > > /Tomas > > On Wed, May 16, 2012 at 10:53 PM, Martin Davis wrote: >> >> Yes, it looks like you've run into a robustness failure with the >> (supposedly) RobustDeterminant algorithm.  There's a few of those that have >> cropped up - although none with as low precision as your case.  Clearly >> the RobustDeterminant code is not in fact 100% robust, contrary to the >> advertising! >> >> >> http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup >> >> I'm reluctant to go in and mess with the RobustDeterminant algorithm, >> since it's pretty complex and obviously critical to get right.  The idea of >> rounding might work for your case, but the other failure cases occur with >> full FP precision, so it's not going to fix them. >> >> Another possibility is to use another method for computing determinant >> sign.  The DoubleDouble arithmetic now in JTS seems to provide enough >> precision to handle this, but it's slow.  Combining it with a fast filter >> might be the way to go. It might even be possible to compute the filter >> using a combination of basic double-precision determinant evaluations, which >> would be as faster or faster than the current algorithm. >> >> This is going to take some careful experimentation, however - there is a >> large risk for getting this wrong. >> >> >> On Tue, May 15, 2012 at 5:40 AM, Tomas Fa wrote: >>> >>> I think that the problem lies in the RobustDeterminant. I think that the >>> RobustDeterminant would be more >>> robust if it was using a fixed PrecisionModel (in a context where a fixed >>> precision is used). Currently, it is >>> impossible, as far as I know ,to specify a precisionModel for >>> CGAlgorithms, but I think it would be desirable. >>> You can provide a MCIndexSnapRounder with a PrecisionModel, but it >>> doesn't use it when CGAlgorithms >>> gets involved (which it gets because of the line intersection >>> operations). In the following program >>> CGAlgorithms fails to behave consistently: >>> >> >> >> ------------------------------------------------------------------------------ >> Live Security Virtual Conference >> Exclusive live event will cover all the ways today's security and >> threat landscape has changed and how IT managers can respond. Discussions >> will include endpoint security, mobile security and the latest in malware >> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts-topo-suite-user@... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >> > ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Tomas Fa - 2012-05-17 07:30:03 Attachments: Message as HTML ```Thanks. Do you have experience of, or opinions about, Shewchuks algorithm for robust sign of determinants? (http://www.cs.cmu.edu/~quake/robust.html) /Tomas On Wed, May 16, 2012 at 10:53 PM, Martin Davis wrote: > Yes, it looks like you've run into a robustness failure with the > (supposedly) RobustDeterminant algorithm. There's a few of those that have > cropped up - although none with as low precision as your case. Clearly > the RobustDeterminant code is not in fact 100% robust, contrary to the > advertising! > > > http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup > > I'm reluctant to go in and mess with the RobustDeterminant algorithm, > since it's pretty complex and obviously critical to get right. The idea of > rounding might work for your case, but the other failure cases occur with > full FP precision, so it's not going to fix them. > > Another possibility is to use another method for computing determinant > sign. The DoubleDouble arithmetic now in JTS seems to provide enough > precision to handle this, but it's slow. Combining it with a fast filter > might be the way to go. It might even be possible to compute the filter > using a combination of basic double-precision determinant evaluations, > which would be as faster or faster than the current algorithm. > > This is going to take some careful experimentation, however - there is a > large risk for getting this wrong. > > > On Tue, May 15, 2012 at 5:40 AM, Tomas Fa wrote: > >> I think that the problem lies in the RobustDeterminant. I think that the >> RobustDeterminant would be more >> robust if it was using a fixed PrecisionModel (in a context where a fixed >> precision is used). Currently, it is >> impossible, as far as I know ,to specify a precisionModel for >> CGAlgorithms, but I think it would be desirable. >> You can provide a MCIndexSnapRounder with a PrecisionModel, but it >> doesn't use it when CGAlgorithms >> gets involved (which it gets because of the line intersection >> operations). In the following program >> CGAlgorithms fails to behave consistently: >> >> > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Martin Davis - 2012-05-16 22:37:27 ```Thanks, Francisco. It looks to me like the Algebra class uses regular double-precision FP for evaluation. This isn't going to be robust enough for use in JTS (that's why the RobustDeterminant algorithm was included originally, and why it's not such an easy thing to replace it). On Wed, May 16, 2012 at 3:21 PM, Francisco José Peñarrubia wrote: > Hi Martin. > > I don't know if this link may help (I haven't tested Colt or > RobustDeterminant algorithm), but at firts glance, it looks like the class > Algebra can do determinants with Doubles. > > http://acs.lbl.gov/software/colt/api/cern/colt/matrix/linalg/Algebra.html > > > Colt is a library used in CERN, and should be well tested and powerful. > > http://acs.lbl.gov/software/colt/ > > There is also a mutithreaded version of Colt: > > https://sites.google.com/site/piotrwendykier/software/parallelcolt > > Hope it helps, and sorry if not ;-) > > Best regards! > > Fran. > > El 16/05/2012 22:53, Martin Davis escribió: > > Yes, it looks like you've run into a robustness failure with the > (supposedly) RobustDeterminant algorithm.  There's a few of those that have > cropped up - although none with as low precision as your case.  Clearly > the RobustDeterminant code is not in fact 100% robust, contrary to the > advertising! > > http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup > > I'm reluctant to go in and mess with the RobustDeterminant algorithm, since > it's pretty complex and obviously critical to get right.  The idea of > rounding might work for your case, but the other failure cases occur with > full FP precision, so it's not going to fix them. > > Another possibility is to use another method for computing determinant sign. >  The DoubleDouble arithmetic now in JTS seems to provide enough precision to > handle this, but it's slow.  Combining it with a fast filter might be the > way to go. It might even be possible to compute the filter using a > combination of basic double-precision determinant evaluations, which would > be as faster or faster than the current algorithm. > > This is going to take some careful experimentation, however - there is a > large risk for getting this wrong. > > On Tue, May 15, 2012 at 5:40 AM, Tomas Fa wrote: >> >> I think that the problem lies in the RobustDeterminant. I think that the >> RobustDeterminant would be more >> robust if it was using a fixed PrecisionModel (in a context where a fixed >> precision is used). Currently, it is >> impossible, as far as I know ,to specify a precisionModel for >> CGAlgorithms, but I think it would be desirable. >> You can provide a MCIndexSnapRounder with a PrecisionModel, but it doesn't >> use it when CGAlgorithms >> gets involved (which it gets because of the line intersection operations). >> In the following program >> CGAlgorithms fails to behave consistently: >> > > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > -- > Fran Peñarrubia > Scolab > http://www.scolab.es > > Asociación gvSIG > http://www.gvsig.com > > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Francisco José Peñarrubia - 2012-05-16 22:21:26 Attachments: Message as HTML ```Hi Martin. I don't know if this link may help (I haven't tested Colt or RobustDeterminant algorithm), but at firts glance, it looks like the class Algebra can do determinants with Doubles. http://acs.lbl.gov/software/colt/api/cern/colt/matrix/linalg/Algebra.html Colt is a library used in CERN, and should be well tested and powerful. http://acs.lbl.gov/software/colt/ There is also a mutithreaded version of Colt: https://sites.google.com/site/piotrwendykier/software/parallelcolt Hope it helps, and sorry if not ;-) Best regards! Fran. El 16/05/2012 22:53, Martin Davis escribió: > Yes, it looks like you've run into a robustness failure with the > (supposedly) RobustDeterminant algorithm. There's a few of those that > have cropped up - although none with as low precision as your case. > Clearly the RobustDeterminant code is not in fact 100% robust, > contrary to the advertising! > > http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup > ; > > I'm reluctant to go in and mess with the RobustDeterminant algorithm, > since it's pretty complex and obviously critical to get right. The > idea of rounding might work for your case, but the other failure cases > occur with full FP precision, so it's not going to fix them. > > Another possibility is to use another method for computing determinant > sign. The DoubleDouble arithmetic now in JTS seems to provide enough > precision to handle this, but it's slow. Combining it with a fast > filter might be the way to go. It might even be possible to compute > the filter using a combination of basic double-precision determinant > evaluations, which would be as faster or faster than the current > algorithm. > > This is going to take some careful experimentation, however - there is > a large risk for getting this wrong. > > On Tue, May 15, 2012 at 5:40 AM, Tomas Fa > wrote: > > I think that the problem lies in the RobustDeterminant. I think > that the RobustDeterminant would be more > robust if it was using a fixed PrecisionModel (in a context where > a fixed precision is used). Currently, it is > impossible, as far as I know ,to specify a precisionModel for > CGAlgorithms, but I think it would be desirable. > You can provide a MCIndexSnapRounder with a PrecisionModel, but it > doesn't use it when CGAlgorithms > gets involved (which it gets because of the line intersection > operations). In the following program > CGAlgorithms fails to behave consistently: > > > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user -- Fran Peñarrubia Scolab http://www.scolab.es Asociación gvSIG http://www.gvsig.com ```
 Re: [Jts-topo-suite-user] strange case for the GeometryNoder From: Martin Davis - 2012-05-16 20:53:12 Attachments: Message as HTML ```Yes, it looks like you've run into a robustness failure with the (supposedly) RobustDeterminant algorithm. There's a few of those that have cropped up - although none with as low precision as your case. Clearly the RobustDeterminant code is not in fact 100% robust, contrary to the advertising! http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/test/test/jts/junit/algorithm/OrientationIndexFailureTest.java?revision=597&view=markup I'm reluctant to go in and mess with the RobustDeterminant algorithm, since it's pretty complex and obviously critical to get right. The idea of rounding might work for your case, but the other failure cases occur with full FP precision, so it's not going to fix them. Another possibility is to use another method for computing determinant sign. The DoubleDouble arithmetic now in JTS seems to provide enough precision to handle this, but it's slow. Combining it with a fast filter might be the way to go. It might even be possible to compute the filter using a combination of basic double-precision determinant evaluations, which would be as faster or faster than the current algorithm. This is going to take some careful experimentation, however - there is a large risk for getting this wrong. On Tue, May 15, 2012 at 5:40 AM, Tomas Fa wrote: > I think that the problem lies in the RobustDeterminant. I think that the > RobustDeterminant would be more > robust if it was using a fixed PrecisionModel (in a context where a fixed > precision is used). Currently, it is > impossible, as far as I know ,to specify a precisionModel for > CGAlgorithms, but I think it would be desirable. > You can provide a MCIndexSnapRounder with a PrecisionModel, but it doesn't > use it when CGAlgorithms > gets involved (which it gets because of the line intersection operations). > In the following program > CGAlgorithms fails to behave consistently: > > ```

Showing results of 56

1 2 3 > >> (Page 1 of 3)