<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Forgot about the area and length tests I think that is what I settled on on some tests in PostGIS where the answers truly were different but different in a unmeaningful way, by that I mean they both achieved satisfactory answers.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>This was done for GDAL as well cause GDAL in 3.2 changed their polygonise algorithms which broke one of our raster tests and the results even after normalize were different.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><div style='border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt'><div><div style='border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in'><p class=MsoNormal><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> geos-devel [mailto:geos-devel-bounces@lists.osgeo.org] <b>On Behalf Of </b>Martin Davis<br><b>Sent:</b> Thursday, October 15, 2020 4:57 PM<br><b>To:</b> GEOS Development List <geos-devel@lists.osgeo.org><br><b>Subject:</b> [geos-devel] Unit testing Overlay operations<o:p></o:p></span></p></div></div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>As noted in a recent thread, it's tricky to create unit tests for overlay operations. One reason for this is that the order of the result components and coordinates is undefined, and so can vary between diifferent algorithms and even different library releases. (The lack of well-defined ordering is deliberate, since introducing ordering would reduce performance).<o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>The solution to this is to normalize the actual result (and possibly the expected value, to ensure it is stable). This imposes a well-defined ordering. It works well for cases which are hand-crafted to test overlay functionality.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>But overlay results can vary in other ways as well, due to the use of different algorithms, different handling of numerical precision, and the heuristics used to ensure robustness. This is much harder to handle. In GEOS we deal with this in a limited way by testing area and length of the result, rather than the actual result geometry. This is obviously a fairly weak test, and it's used mostly for checking robustness (which tends to produce either grossly wrong results or outright failure).<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>A further option would be to use some kind of similarity metric. JTS has used Area of Symmetric Difference and Hausdorff distance to unit test the buffer operation (which has this problem as well). I've also experimented with a "pinhole" method, involving generating points within a given distance of the input and result linework.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>To keep things simple, it's easiest to use relatively simple geometry to test functionality, and cruder comparisons to test robustness.<o:p></o:p></p></div><div><p class=MsoNormal> <o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> <o:p></o:p></p></div></div></div></div></body></html>