<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 14 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><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;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
code
{mso-style-priority:99;
font-family:"Courier New";}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Arial","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
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-GB" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">Thanks for the replies, interesting stuff.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">I ended up using
<i>ST_ConvexHull(st_collect(geom))</i> in PostGIS (nice and fast) to create a polygon covering all the points, and then I used FME to measure the distance between all the vertices of that hull and the greatest distance was my answer. The hull being a much smaller
dataset, it was much faster than it would have been had I tried to measure the billions of potential distances between millions of points.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">I suspect the later part can be done in PostGIS too, but I needed to do some other bits in FME with the data, and as I know it much better than PostGIS, that
seemed like the expedient option, ST_LongestLine in particular from the responses I saw here.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D">Jonathan<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> postgis-users-bounces@lists.osgeo.org [mailto:postgis-users-bounces@lists.osgeo.org]
<b>On Behalf Of </b>Rémi Cura<br>
<b>Sent:</b> Tuesday, June 30, 2015 8:11 AM<br>
<b>To:</b> PostGIS Users Discussion<br>
<b>Subject:</b> Re: [postgis-users] Distance between two furthest points of a group<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">Maybe you can even reduce this with cte :<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""><br>
with collected_geom AS (<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">select st_collect(geom) as geoms<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">from your_points<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">SELECT ST_LonguestLine(t1.geoms,t2.geoms)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-family:"Courier New"">FROM collected_geom AS t1, collected_geom AS t2<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">Cheers,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">Rémi-C<o:p></o:p></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">2015-06-30 8:48 GMT+02:00 Nick Ves <<a href="mailto:vesnikos@gmail.com" target="_blank">vesnikos@gmail.com</a>>:<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">Didn't know about st_LongestLine.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif""><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">Just tried and it amazed me!<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif""><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">on a dataset of 220k points (on a projected crs) it took ~ 1.5 secs to answer the querry :<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">select 1 as id, ST_LongestLine(st_collect(geom),st_collect(geom)) geom from points ;</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">N</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif""><o:p> </o:p></span></p>
</div>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Sat, Jun 27, 2015 at 2:41 PM, Nicklas Avén <<a href="mailto:nicklas.aven@jordogskog.no" target="_blank">nicklas.aven@jordogskog.no</a>> wrote:<o:p></o:p></p>
<p>Hallo<o:p></o:p></p>
<p>I haven't followed the whole conversation. <o:p></o:p></p>
<p>But one way is to collect alk points and usr ST_maxdistance on the colnections. or st_longestline. longestline will return a line where the end points is the two points furthest from eath other. Those functions is quite fast.<o:p></o:p></p>
<p style="margin-bottom:12.0pt">/Nicklas<br>
<br>
<o:p></o:p></p>
<p>Sent from my Cat® phone.<o:p></o:p></p>
<div>
<div>
<div>
<p class="MsoNormal">Den 27 jun 2015 13:25 skrev Rémi Cura <<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a>>:<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">Maybe I'm wrong, but your 2 farthest points should be on the boundary of the maximum bounding circle (feels right but couldn't prove it).<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-family:"Courier New"">Thus you would compute this circle, then filter points not too far from it, then take the points with the max distance using an inner join (same as Nick, but you can save
half the computation because dist(A,B)=dist(B,A), so simply add a condition <a href="http://a.id" target="_blank">
a.id</a><<a href="http://b.id" target="_blank">b.id</a>)).<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">Another solution is to use bbox n nearest neighbour, which is indexed.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">You wouldn't car too much about using bbox, because for points it only reduce precision to float instead of double.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">This would be like :<br>
<br>
</span><span style="font-family:"Tahoma","sans-serif"">SELECT <a href="http://a.id" target="_blank">
a.id</a>,<a href="http://b.id" target="_blank">b.id</a>, st_distance(a.geom,b.geom) AS d
<br>
FROM my_points AS a </span><span style="font-family:"Courier New"">, my_points AS b</span><span style="font-size:10.0pt;font-family:"Courier New""><br>
<code>ORDER BY a.geom <-> </code></span><span style="font-family:"Courier New"">b.geom DESC<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-family:"Courier New"">LIMIT 1<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">This is the probably the better easiness/speed ratio.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">Cheers,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">Rémi-C<o:p></o:p></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">2015-06-26 22:06 GMT+02:00 Nick Ves <<a href="mailto:vesnikos@gmail.com" target="_blank">vesnikos@gmail.com</a>>:<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">You can cross join to create the cartesian product of them and use it to calculate the distance of each with regards to the other: </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">select <a href="http://a.id" target="_blank">
a.id</a>,<a href="http://b.id" target="_blank">b.id</a>, st_distance(a.geom,b.geom) d from points a cross join points b order by d desc limit 1;</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">ofc that will take forever because it will have to create an m x n table (800 secs and counting...)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">As I see it the two points with the furthest distance between them should touch the borders of you datasets convexhull. So you can filter out those inside the boundaries and do the calculations
with the remaining points along the borders :</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">with f as <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">( <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">select a.geom,<a href="http://a.id" target="_blank">a.id</a> from <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">points foo,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">(select ST_ExteriorRing (st_convexhull(st_collect(geom))) geom from points) bar <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">where st_Dwithin(foo.geom,bar.geom,0.00000001)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">select <a href="http://a.id" target="_blank">
a.id</a>,<a href="http://b.id" target="_blank">b.id</a>, st_distance(a.geom,b.geom) d from f a cross join f b order by d desc limit 1;<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif""><o:p> </o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Tahoma","sans-serif"">should give you the id of your targets and the distance between them<o:p></o:p></span></p>
</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>
<p class="MsoNormal">On Fri, Jun 26, 2015 at 2:54 PM, Jonathan Moules <<a href="mailto:J.Moules@hrwallingford.com" target="_blank">J.Moules@hrwallingford.com</a>> wrote:<o:p></o:p></p>
</div>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C">Hi List,</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C">I have sets of points (up to 250,000 in a set) and I want to get the furthest distance between any
of them.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C">In theory the simplest way is to use ST_MinimumBoundingCircle(ST_Collect(geography) and then get the
diameter of that.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C">The problem is – I don’t seem to be able to get the diameter of that circle (which would give me the
distance I want).</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C">Does anyone have any thoughts on this? Is there a good way to get the diameter? Or some other way of
getting the distance I desire.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C"> </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C">Thanks,</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#3C3C3C">Jonathan</span><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="100%" align="center">
</div>
<p><b><span style="font-size:8.0pt;font-family:"Arial","sans-serif"">HR Wallingford and its subsidiaries</span></b><span style="font-size:8.0pt;font-family:"Arial","sans-serif""> uses faxes and emails for confidential and legally privileged business communications.
They do not of themselves create legal commitments. Disclosure to parties other than addressees requires our specific consent. We are not liable for unauthorised disclosures nor reliance upon them.
<br>
If you have received this message in error please advise us immediately and destroy all copies of it.
<br>
<br>
HR Wallingford Limited<br>
Howbery Park, Wallingford, Oxfordshire, OX10 8BA, United Kingdom<br>
Registered in England No. 02562099<o:p></o:p></span></p>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="100%" align="center">
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<p class="MsoNormal">_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<p class="MsoNormal"><br>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><br>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
<p class="MsoNormal"><br>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><o:p> </o:p></p>
<p align="center" style="text-align:center"><span style="background:white">This message has been scanned for viruses by
</span><a href="http://www.mailcontrol.com/"><span style="background:white">MailControl</span></a><span style="background:white">, a service from BlackSpider Technology</span><o:p></o:p></p>
<p><span style="font-size:10.0pt">Click <a href="https://www.mailcontrol.com/sr/8wU+ANsngJbGX2PQPOmvUtzroFmuoUEujA1tmRx6QBJ9hPG3sWmR7sOI52Ay98QASuwfZeMf7FcAXoNDtAu6BA==">
here</a> to report this email as spam.<o:p></o:p></span></p>
<p align="center" style="text-align:center"><o:p> </o:p></p>
</div>
<br>
<hr>
<p style="font-family:arial;font-color:grey;font-size:8pt"><b>HR Wallingford and its subsidiaries</b> uses faxes and emails for confidential and legally privileged business communications. They do not of themselves create legal commitments. Disclosure to parties
other than addressees requires our specific consent. We are not liable for unauthorised disclosures nor reliance upon them.
<br>
If you have received this message in error please advise us immediately and destroy all copies of it.
<br>
<br>
HR Wallingford Limited<br>
Howbery Park, Wallingford, Oxfordshire, OX10 8BA, United Kingdom<br>
Registered in England No. 02562099<br>
</p>
<p></p>
<hr>
<p></p>
</body>
</html>