Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Right-click on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
|
From: Peter Hopfgartner <peter.hopfgartner@r3...> - 2011-10-05 20:14:44
|
The Shoelace algorithm is applied for area calculations. Further, coordinates are transformed, so that the first node is the new origin for the area calculation. This keeps the mantissa free from a constant offset. The attached examples show, that the algorithm keeps the error in area calculation very low even with a large number of nodes. Regards, Peter R3 GIS Srl - GmbH http://www.r3-gis.com |
|
From: Martin Davis <mtnclimb@te...> - 2011-10-05 21:24:41
Attachments:
Message as HTML
|
Thanks, Peter. This does look like a slicker and more accurate way to compute area. And with a Wikepedia entry as well! (Which, by the way, actually looks like it has a bug. I think the formula they give computes the negative area. To compute the positive area it's simply necessary to switch the order of the y values in the equation. This is confirmed by the provided reference #3, as well as my testing). I suppose to provide even more accuracy the largest x value (in absolute value) could be used as the constant offset. I'll update JTS with this improvement. Martin On 10/5/2011 12:54 PM, Peter Hopfgartner wrote: > The Shoelace algorithm is applied for area calculations. Further, coordinates are transformed, so that the first node is the new origin for the area calculation. This keeps the mantissa free from a constant offset. > > The attached examples show, that the algorithm keeps the error in area calculation very low even with a large number of nodes. > > > > Regards, > > > > Peter > > > > R3 GIS Srl - GmbH > > http://www.r3-gis.com > > > > ------------------------------------------------------------------------------ > All the data continuously generated in your IT infrastructure contains a > definitive record of customers, application performance, security > threats, fraudulent activity and more. Splunk takes this data and makes > sense of it. Business sense. IT sense. Common sense. > http://p.sf.net/sfu/splunk-d2dcopy1 > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > ----- > No virus found in this message. > Checked by AVG - http://www.avg.com > Version: 10.0.1410 / Virus Database: 1520/3939 - Release Date: 10/05/11 |
|
From: Peter Hopfgartner <peter.hopfgartner@r3...> - 2011-10-06 07:17:03
Attachments:
Message as HTML
|
On 10/05/2011 11:24 PM, Martin Davis wrote: > Thanks, Peter. This does look like a slicker and more accurate way to > compute area. And with a Wikepedia entry as well! (Which, by the > way, actually looks like it has a bug. I think the formula they give > computes the negative area. To compute the positive area it's simply > necessary to switch the order of the y values in the equation. This > is confirmed by the provided reference #3, as well as my testing). > Sorry, my fault. I always had some problems in orientation (maybe GIS is my therapy for this). > I suppose to provide even more accuracy the largest x value (in > absolute value) could be used as the constant offset. > From an heuristic POV I would guess, that the most accurate result could be calculated, when the origin is placed in the center of mass or center of the bounding box, since that would keep the coordinates as small as possible. As I understand it, that would require to first calculate that center estimate, which has at least the cost to loop through all coordinates. From the rather synthetic test case, which I used, it is difficult to have real numbers of the impact on the accuracy of the result on that. If you think that there might be some benefit, it might make sense to use real data, as in TIGER, and compare the result obtained with floating points to the result obtained with an arbitrary precision float library, like http://www.apfloat.org. Having the origin in the first coordinate allows to drop the first term, since x1 is zero. > I'll update JTS with this improvement. > > Martin > Peter On 10/5/2011 12:54 PM, Peter Hopfgartner wrote: >> The Shoelace algorithm is applied for area calculations. Further, coordinates are transformed, so that the first node is the new origin for the area calculation. This keeps the mantissa free from a constant offset. >> >> The attached examples show, that the algorithm keeps the error in area calculation very low even with a large number of nodes. >> >> >> >> Regards, >> >> >> >> Peter >> >> >> >> R3 GIS Srl - GmbH >> >> http://www.r3-gis.com >> >> >> >> ------------------------------------------------------------------------------ >> All the data continuously generated in your IT infrastructure contains a >> definitive record of customers, application performance, security >> threats, fraudulent activity and more. Splunk takes this data and makes >> sense of it. Business sense. IT sense. Common sense. >> http://p.sf.net/sfu/splunk-d2dcopy1 >> >> >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts-topo-suite-user@... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >> >> >> ----- >> No virus found in this message. >> Checked by AVG -www.avg.com >> Version: 10.0.1410 / Virus Database: 1520/3939 - Release Date: 10/05/11 > > > ------------------------------------------------------------------------------ > All the data continuously generated in your IT infrastructure contains a > definitive record of customers, application performance, security > threats, fraudulent activity and more. Splunk takes this data and makes > sense of it. Business sense. IT sense. Common sense. > http://p.sf.net/sfu/splunk-d2dcopy1 > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user |
|
From: Martin Davis <mtnclimb@te...> - 2011-10-07 16:55:22
Attachments:
Message as HTML
|
Yes, agreed, it would be good if this found it's way into GEOS and PostGIS. (cc-ing geos-devel so they can get on it!) On 10/6/2011 11:42 PM, Peter Hopfgartner wrote: > On 10/06/2011 06:33 PM, Martin Davis wrote: >> (...) >>>> I suppose to provide even more accuracy the largest x value (in >>>> absolute value) could be used as the constant offset. >>>> >>> From an heuristic POV I would guess, that the most accurate result >>> could be calculated, when the origin is placed in the center of mass >>> or center of the bounding box, since that would keep the coordinates >>> as small as possible. >>> As I understand it, that would require to first calculate that >>> center estimate, which has at least the cost to loop through all >>> coordinates. >>> From the rather synthetic test case, which I used, it is difficult >>> to have real numbers of the impact on the accuracy of the result on >>> that. If you think that there might be some benefit, it might make >>> sense to use real data, as in TIGER, and compare the result obtained >>> with floating points to the result obtained with an arbitrary >>> precision float library, like http://www.apfloat.org. >>> >>> Having the origin in the first coordinate allows to drop the first >>> term, since x1 is zero. >> As you say, it's probably not worth the effort to make this minor >> improvement in accuracy. >> >> I had thought about using higher-precision computation to check the >> area results. I would use the DD (DoubleDouble) class which is now >> in JTS - it provides 106 bits of precision. >> >> And as you say, more real-world examples would be better for >> testing. I might try and do this - although it doesn't seem like >> anyone should be relying on the area computation to be "perfectly" >> accurate. Or am I wrong on this? How did you come to notice that >> the area was not as accurate as it could be? >> > I agree that nobody should rely on exact area calculations. We had a > minor problem, when we did things like splitting polygons in PostGIS. > We compared the area of the parts to the area to the parent polygon > ane the difference was bigger then expected. Having a look at GEOS I > saw that it used the same algorithm as PostGIS (or vice versa) and > from there I decided to start from JTS. Now I like to apply tha same > on GEOS and PostGIS. > > http://postgis.refractions.net/pipermail/postgis-devel/2011-February/011715.htm > was a first version of this patch. > > Peter > > > ------------------------------------------------------------------------------ > All of the data generated in your IT infrastructure is seriously valuable. > Why? It contains a definitive record of application performance, security > threats, fraudulent activity, and more. Splunk takes this data and makes > sense of it. IT sense. And common sense. > http://p.sf.net/sfu/splunk-d2dcopy2 > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > No virus found in this message. > Checked by AVG - http://www.avg.com <http://www.avg.com>; > Version: 10.0.1410 / Virus Database: 1520/3941 - Release Date: 10/06/11 > |
|
From: Peter Hopfgartner <peter.hopfgartner@r3...> - 2011-10-18 08:06:13
Attachments:
Message as HTML
|
Done! http://trac.osgeo.org/postgis/ticket/810 http://trac.osgeo.org/geos/ticket/485 All tests pass. Peter On 10/07/2011 06:55 PM, Martin Davis wrote: > Yes, agreed, it would be good if this found it's way into GEOS and > PostGIS. > > (cc-ing geos-devel so they can get on it!) > > > On 10/6/2011 11:42 PM, Peter Hopfgartner wrote: >> On 10/06/2011 06:33 PM, Martin Davis wrote: >>> (...) >>>>> I suppose to provide even more accuracy the largest x value (in >>>>> absolute value) could be used as the constant offset. >>>>> >>>> From an heuristic POV I would guess, that the most accurate result >>>> could be calculated, when the origin is placed in the center of >>>> mass or center of the bounding box, since that would keep the >>>> coordinates as small as possible. >>>> As I understand it, that would require to first calculate that >>>> center estimate, which has at least the cost to loop through all >>>> coordinates. >>>> From the rather synthetic test case, which I used, it is difficult >>>> to have real numbers of the impact on the accuracy of the result on >>>> that. If you think that there might be some benefit, it might make >>>> sense to use real data, as in TIGER, and compare the result >>>> obtained with floating points to the result obtained with an >>>> arbitrary precision float library, like http://www.apfloat.org. >>>> >>>> Having the origin in the first coordinate allows to drop the first >>>> term, since x1 is zero. >>> As you say, it's probably not worth the effort to make this minor >>> improvement in accuracy. >>> >>> I had thought about using higher-precision computation to check the >>> area results. I would use the DD (DoubleDouble) class which is now >>> in JTS - it provides 106 bits of precision. >>> >>> And as you say, more real-world examples would be better for >>> testing. I might try and do this - although it doesn't seem like >>> anyone should be relying on the area computation to be "perfectly" >>> accurate. Or am I wrong on this? How did you come to notice that >>> the area was not as accurate as it could be? >>> >> I agree that nobody should rely on exact area calculations. We had a >> minor problem, when we did things like splitting polygons in PostGIS. >> We compared the area of the parts to the area to the parent polygon >> ane the difference was bigger then expected. Having a look at GEOS I >> saw that it used the same algorithm as PostGIS (or vice versa) and >> from there I decided to start from JTS. Now I like to apply tha same >> on GEOS and PostGIS. >> >> http://postgis.refractions.net/pipermail/postgis-devel/2011-February/011715.htm >> was a first version of this patch. >> >> Peter >> >> >> ------------------------------------------------------------------------------ >> All of the data generated in your IT infrastructure is seriously valuable. >> Why? It contains a definitive record of application performance, security >> threats, fraudulent activity, and more. Splunk takes this data and makes >> sense of it. IT sense. And common sense. >> http://p.sf.net/sfu/splunk-d2dcopy2 >> >> >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts-topo-suite-user@... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >> >> >> No virus found in this message. >> Checked by AVG - http://www.avg.com <http://www.avg.com>; >> Version: 10.0.1410 / Virus Database: 1520/3941 - Release Date: 10/06/11 >> > > ------------------------------------------------------------------------------ > All of the data generated in your IT infrastructure is seriously valuable. > Why? It contains a definitive record of application performance, security > threats, fraudulent activity, and more. Splunk takes this data and makes > sense of it. IT sense. And common sense. > http://p.sf.net/sfu/splunk-d2dcopy2 > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user -- Dott. Peter Hopfgartner R3 GIS Srl - GmbH Via Johann Kravogl-Str. 2 I-39012 Meran/Merano (BZ) web : http://www.r3-gis.com mail : peter.hopfgartner@... phone: +39 0473 494949 fax : +39 0473 069902 ATTENZIONE! Le informazioni contenute nella presente e-mail e nei documenti eventualmente allegati sono confidenziali. La loro diffusione, distribuzione e/o riproduzione da parte di terzi, senza autorizzazione del mittente è vietata e può violare il D. Lgs. 196/2003. In caso di ricezione per errore, Vogliate immediatamente informare il mittente del messaggio e distruggere la e-mail. ACHTUNG! Die in dieser Nachricht oder in den beigelegten Dokumenten beinhalteten Informationen sind streng vertraulich. Ihre Verbreitung und/oder ihre Wiedergabe durch Dritte ist ohne Erlaubnis des Absenders verboten und verstößt gegen das Legislativdekret 196/2003. Sollten Sie diese Mitteilung irrtümlicherweise erhalten haben, bitten wir Sie uns umgehend zu informieren und anschließend die Mitteilung zu vernichten. WARNING! This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorised copying, disclosure or distribution of the material in this e-mail is strictly forbidden and could be against the law (D. Lgs. 196/2003) |
|
From: Martin Davis <mtnclimb@te...> - 2011-10-06 16:34:23
Attachments:
Message as HTML
|
On 10/6/2011 12:16 AM, Peter Hopfgartner wrote: > On 10/05/2011 11:24 PM, Martin Davis wrote: >> Thanks, Peter. This does look like a slicker and more accurate way >> to compute area. And with a Wikepedia entry as well! (Which, by >> the way, actually looks like it has a bug. I think the formula they >> give computes the negative area. To compute the positive area it's >> simply necessary to switch the order of the y values in the >> equation. This is confirmed by the provided reference #3, as well as >> my testing). >> > Sorry, my fault. I always had some problems in orientation (maybe GIS > is my therapy for this). I think your code was right, it is the Wikipedia article that is wrong. >> I suppose to provide even more accuracy the largest x value (in >> absolute value) could be used as the constant offset. >> > From an heuristic POV I would guess, that the most accurate result > could be calculated, when the origin is placed in the center of mass > or center of the bounding box, since that would keep the coordinates > as small as possible. > As I understand it, that would require to first calculate that center > estimate, which has at least the cost to loop through all coordinates. > From the rather synthetic test case, which I used, it is difficult to > have real numbers of the impact on the accuracy of the result on that. > If you think that there might be some benefit, it might make sense to > use real data, as in TIGER, and compare the result obtained with > floating points to the result obtained with an arbitrary precision > float library, like http://www.apfloat.org. > > Having the origin in the first coordinate allows to drop the first > term, since x1 is zero. As you say, it's probably not worth the effort to make this minor improvement in accuracy. I had thought about using higher-precision computation to check the area results. I would use the DD (DoubleDouble) class which is now in JTS - it provides 106 bits of precision. And as you say, more real-world examples would be better for testing. I might try and do this - although it doesn't seem like anyone should be relying on the area computation to be "perfectly" accurate. Or am I wrong on this? How did you come to notice that the area was not as accurate as it could be? > >> I'll update JTS with this improvement. >> >> Martin >> > > Peter > > On 10/5/2011 12:54 PM, Peter Hopfgartner wrote: >>> The Shoelace algorithm is applied for area calculations. Further, coordinates are transformed, so that the first node is the new origin for the area calculation. This keeps the mantissa free from a constant offset. >>> >>> The attached examples show, that the algorithm keeps the error in area calculation very low even with a large number of nodes. >>> >>> >>> >>> Regards, >>> >>> >>> >>> Peter >>> >>> >>> >>> R3 GIS Srl - GmbH >>> >>> http://www.r3-gis.com >>> >>> >>> >>> ------------------------------------------------------------------------------ >>> All the data continuously generated in your IT infrastructure contains a >>> definitive record of customers, application performance, security >>> threats, fraudulent activity and more. Splunk takes this data and makes >>> sense of it. Business sense. IT sense. Common sense. >>> http://p.sf.net/sfu/splunk-d2dcopy1 >>> >>> >>> _______________________________________________ >>> Jts-topo-suite-user mailing list >>> Jts-topo-suite-user@... >>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >>> >>> >>> ----- >>> No virus found in this message. >>> Checked by AVG -www.avg.com >>> Version: 10.0.1410 / Virus Database: 1520/3939 - Release Date: 10/05/11 >> >> >> ------------------------------------------------------------------------------ >> All the data continuously generated in your IT infrastructure contains a >> definitive record of customers, application performance, security >> threats, fraudulent activity and more. Splunk takes this data and makes >> sense of it. Business sense. IT sense. Common sense. >> http://p.sf.net/sfu/splunk-d2dcopy1 >> >> >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts-topo-suite-user@... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > > ------------------------------------------------------------------------------ > All the data continuously generated in your IT infrastructure contains a > definitive record of customers, application performance, security > threats, fraudulent activity and more. Splunk takes this data and makes > sense of it. Business sense. IT sense. Common sense. > http://p.sf.net/sfu/splunk-d2dcopy1 > > > _______________________________________________ > Jts-topo-suite-user mailing list > Jts-topo-suite-user@... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > No virus found in this message. > Checked by AVG - http://www.avg.com <http://www.avg.com>; > Version: 10.0.1410 / Virus Database: 1520/3939 - Release Date: 10/05/11 > |
|
From: Michael Bedward <michael.bedward@gm...> - 2011-10-07 06:33:14
|
On 7 October 2011 03:33, Martin Davis <mtnclimb@...> wrote: > > As you say, it's probably not worth the effort to make this minor > improvement in accuracy. > > I had thought about using higher-precision computation to check the area > results. I would use the DD (DoubleDouble) class which is now in JTS - it > provides 106 bits of precision. > For large polygons, perhaps another option would be to partition them, with some max width / height constraint, and add up the areas of the parts. If you have a use case where accuracy is crucial you might be willing to put up with the computational cost. Michael |
|
From: Peter Hopfgartner <peter.hopfgartner@r3...> - 2011-10-07 06:43:28
Attachments:
Message as HTML
|
On 10/06/2011 06:33 PM, Martin Davis wrote: > (...) >>> I suppose to provide even more accuracy the largest x value (in >>> absolute value) could be used as the constant offset. >>> >> From an heuristic POV I would guess, that the most accurate result >> could be calculated, when the origin is placed in the center of mass >> or center of the bounding box, since that would keep the coordinates >> as small as possible. >> As I understand it, that would require to first calculate that center >> estimate, which has at least the cost to loop through all coordinates. >> From the rather synthetic test case, which I used, it is difficult to >> have real numbers of the impact on the accuracy of the result on >> that. If you think that there might be some benefit, it might make >> sense to use real data, as in TIGER, and compare the result obtained >> with floating points to the result obtained with an arbitrary >> precision float library, like http://www.apfloat.org. >> >> Having the origin in the first coordinate allows to drop the first >> term, since x1 is zero. > As you say, it's probably not worth the effort to make this minor > improvement in accuracy. > > I had thought about using higher-precision computation to check the > area results. I would use the DD (DoubleDouble) class which is now in > JTS - it provides 106 bits of precision. > > And as you say, more real-world examples would be better for testing. > I might try and do this - although it doesn't seem like anyone should > be relying on the area computation to be "perfectly" accurate. Or am > I wrong on this? How did you come to notice that the area was not as > accurate as it could be? > I agree that nobody should rely on exact area calculations. We had a minor problem, when we did things like splitting polygons in PostGIS. We compared the area of the parts to the area to the parent polygon ane the difference was bigger then expected. Having a look at GEOS I saw that it used the same algorithm as PostGIS (or vice versa) and from there I decided to start from JTS. Now I like to apply tha same on GEOS and PostGIS. http://postgis.refractions.net/pipermail/postgis-devel/2011-February/011715.htm was a first version of this patch. Peter |