Calculating the maximum diagonal distance in a given set of points | Hacker News Reader

Calculating the maximum diagonal distance in a given set of points

piotrjaworski.medium.com

58 pointspiotrjaw42 comments

If you have the points in order, you can do it using the rotating calipers method [1] in O(n). In the case from the article, you would have to remove the interior lines, but I guess this could also be done in O(n) as the points on interior lines are the points appearing more than once [2].

[1] https://en.wikipedia.org/wiki/Rotating_calipers

[2] At least almost, the first and last point of interior lines are also part of the outer line.

Indeed, but the convex hull approach also works for multiple sets of points, in any order.

As for [2], in the article the data is separated into 16 polygons, so the interior lines are actually shared between polygons. It's still possible to union the polygons, but it takes more time than calculating the convex hull.

We had to do this in 144 dimensions: https://blog.cloudflare.com/computing-euclidean-distance-on-...

Impressive, thank you for sharing!

Fun! For reasons related to my username, I am about to dip back into the current state-of-the-art algos for highly dimensional data.

I need to dig deep into highly optimized and perhaps distributed algorithms in this space - gotta deal with billions of high dimensionality items. The end result is probably going to be almost a survey from standard distance-based algos like hierarchical clustering headed into louvain methods. Anything "special" or maybe uncommon you like for this type of thing?

I was hoping this article was about mathematical methods. I was disappointed to see it was actually about a Javascript library.

Pretty much sums up the experience of working in tech.

Almost. He could have completely side stepped doing any problem solving or mathematical / logical reasoning by applying machine learning to it.

Hey, that was the idea for the next article...

Another optimization would be to compare square of distance instead of distance, saving "Math.sqrt" call each iteration.

Math.sqrt in a big loop is surprisingly slow. You learn this 0.2 seconds into game development, but I ran into it in a business context recently.

3% of a large cpu intensive runtime was sqrt.

Damn, this is a great point, thank you!

I've actually added this to the article, thank you again!

It would have been nice for the author to get into or link to a description of the convex hull algorithm since that was the speed up magic. Since they didn't: https://en.wikipedia.org/wiki/Convex_hull_algorithms

If we're looking at the hull story, J J Sylvester might be of tangential interest to some.

https://chalkdustmagazine.com/blog/sylvesters-convex-hull-pr...

Neat writeup, if missing the mathematical portion that speeds it up.

One callout if folks think about implementing something similar. Euclidean distance on a sphere has unintended consequences. Great circle distance would be more appropriate.

It's not even a correctly normalized Euclidean distance.

You're correct, this is just a synthetic value used to rank the distances.

It would be marginally slower to take the square root when all you need is rank

That is correct, but - as pointed in the article - we work on floor plans, which are flat, so I wanted to simplify this a bit to not create too much issues to solve in one article. That said, it was probably an oversimplification, since actual geographic data (and a map view) was used, point taken.

No worries whatsoever. It wasn't a critique of the general idea, simply to keep distance metrics in mind relative to scale.

Working on the a floor plan or proof of concept? Euclidean metric absolutely works.

Working on Mercator projections or legal type stuff? eh....

I wanted to use Turf but it doesn’t support a non-projected Cartesian space. It breaks if you try to tell it your world is flat.

GeoJSON’s spec specifically says it’s lat/lng in geographic space, but I’ve been using it for indoor robotics for almost a decade and it works amazing.

I wonder how hard it would be to add CRS.Simple support… maybe this is my holiday project.

Same here, we use GeoJSON for floor plans and it works great. Yeah, too bad that Turf is geographical only, but it still has some nice helpers that are agnostic to the shape of the plane.

This problem is traditionally known as finding the "diameter" of a set of points, e.g. https://stackoverflow.com/questions/27414060/find-the-diamet...

It's wrong by about 5%, you can see it if you just try to do it by hand or eye (mentally rotate that red line about the NW endpoint and it should sweep all of poland.)

https://imgur.com/a/NEwNxVl

Circle:

https://i.imgur.com/omKqty4.png

I don't think it's a latitude/distance vs Pythagoras thing because the two SE points are only about 1.25 degrees apart - you'd expect about 1 part in 72 difference. (You can get a lot of useful work done with Pythagoras and a lat/long if you assume that the equator to pole gore is a triangle rather than curved - linear variance rather than with the cosine, it works well wherever there are people/paid gis work.)

> without accounting for the curvature of the Earth) is 768 and a quarter

After accounting for the curvature of the Earth, the distance between (53.92085665, 14.2861684) and (49.0080789, 22.88022362) is 806 km, and the line is very different from what's shown in the article.

Do you think the curvature is why it's wrong or there's just a mistake/bug that the code skipped that point/pair? Distance is ~5% off but the latitude difference between the two SE candidates are only ~1/70th of a quarter circle.

A small latitude difference does not imply that you can ignore curvature.

I am just guessing, but perhaps your intuition is that the shortest path should lie along a line of latitude. An easy-to-see counterexample would be two points close to the north pole, but with 180 degrees of longitude separating them. In this case the shortest path actually goes through the north pole, rather than around it.

You can also generalize this say that within the northern hemisphere, the shortest path between two points will curve (when viewed on a flat map) towards the north pole.

cos(54 deg)/cos(49 deg) ~ 0.588/0.656 ~ 0.9, so a longitude degree in the north of the country is about 10% shorter than in the south.

Indeed, I added a couple of paragraphs in the end explaining the difference and the actual results. As a side note, I actually got slightly different numbers, but maybe that's because of the lower quality of data that I used.

Can you tell us what the both line solutions measure to using the first approach and the second approach? I'm curious about the effect of the curvature on the calculation. Thanks!

Sure! It's pretty straightforward actually.

The first approach (which is a simplification) uses the usual way to calculate a distance between two points on a FLAT plane, which using is the Pythagorean Theorem. So d = √((y1 - y2)^2 + (x1 - x2)^2).

The second approach uses the haversine formula: https://en.wikipedia.org/wiki/Haversine_formula which takes the curvature of the Earth into account, and also the fact that one degree in longitude is a different distance depending on the latitude.

Sorry, I was asking for the numeric answers, I'm genuinely curious about the distance values of the two pairs of numbers using the two formula.

The end result is still O(n^2) in the number of vertices in the convex hull...

If you didn't just slap together JS libs, but studied the literature, you'd find that the proper algorithm for this problem runs in O(n) time, and is called the "rotating calipers" algorithm.

Damn way to be a condescending dickhead.

Please consider editing out the D-word from your comment.

Some religious folks might find it a bit offensive. Thank you! (some alternatives: dang, darn, gosh, blimey, golly, etc.)

A condescending gollyhead? I think that might be worse.

Damn way to be a condescending blimey?

Why specifically mention religious folks?

Some specific religion that adheres to the church of the throbbing Cock, and want us not to take the Holy Dickhead into our mouths in vain?

We've banned this account for posting unsubstantive and flamebait comments.

Please don't create accounts to break HN's rules with. If you don't want to be banned, you're welcome to email hn@ycombinator.com and give us reason to believe that you'll follow them in the future. They're here: https://news.ycombinator.com/newsguidelines.html.

Please don't respond to a bad comment by breaking the site guidelines yourself. That only makes everything worse.

https://news.ycombinator.com/newsguidelines.html

Edit: it looks like you've been breaking the site guidelines in other places as well. We ban accounts that do that repeatedly, so please don't.

And even that isn't going to work correctly in all cases if you just ignore the Earth's curvature.

Reply on news.ycombinator.com