Calculating the maximum diagonal distance in a given set of points(piotrjaworski.medium.com)
piotrjaworski.medium.com
Calculating the maximum diagonal distance in a given set of points
https://piotrjaworski.medium.com/calculating-the-maximum-diagonal-distance-in-a-given-collection-of-geojson-features-using-turf-js-ff1a2654c7e7
43 comments
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.
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-...
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 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?
Impressive, thank you for sharing!
I was hoping this article was about mathematical methods. I was disappointed to see it was actually about a Javascript library.
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.
3% of a large cpu intensive runtime was sqrt.
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...
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.
One callout if folks think about implementing something similar. Euclidean distance on a sphere has unintended consequences. Great circle distance would be more appropriate.
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....
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.
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.)
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.
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.
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.
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.
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.
And even that isn't going to work correctly in all cases if you just ignore the Earth's curvature.
Damn way to be a condescending dickhead.
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.
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.
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.)
Some religious folks might find it a bit offensive. Thank you! (some alternatives: dang, darn, gosh, blimey, golly, etc.)
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 [email protected] 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 create accounts to break HN's rules with. If you don't want to be banned, you're welcome to email [email protected] and give us reason to believe that you'll follow them in the future. They're here: https://news.ycombinator.com/newsguidelines.html.
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?
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?
A condescending gollyhead? I think that might be worse.
Damn way to be a condescending blimey?
[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.