[HN Gopher] Calculating the maximum diagonal distance in a given...
___________________________________________________________________
Calculating the maximum diagonal distance in a given set of points
Author : piotrjaw
Score : 47 points
Date : 2022-12-16 13:15 UTC (9 hours ago)
(HTM) web link (piotrjaworski.medium.com)
(TXT) w3m dump (piotrjaworski.medium.com)
| tomrod wrote:
| 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.
| wikfwikf wrote:
| It's not even a correctly normalized Euclidean distance.
| tomrod wrote:
| It would be marginally slower to take the square root when
| all you need is rank
| piotrjaw wrote:
| You're correct, this is just a synthetic value used to rank
| the distances.
| piotrjaw wrote:
| 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.
| tomrod wrote:
| 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....
| jgrahamc wrote:
| We had to do this in 144 dimensions:
| https://blog.cloudflare.com/computing-euclidean-distance-on-...
| piotrjaw wrote:
| Impressive, thank you for sharing!
| clusterhacks wrote:
| 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?
| SuperFine wrote:
| 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.
| helloooooooo wrote:
| Damn way to be a condescending dickhead.
| dang wrote:
| 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.
| SuperFine wrote:
| 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.)
| dang wrote:
| 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.
| isoprophlex wrote:
| 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?
| twic wrote:
| A condescending gollyhead? I think that might be worse.
| eddsh1994 wrote:
| Damn way to be a condescending blimey?
| helloooooooo wrote:
| Scarblac wrote:
| And even that isn't going to work correctly in all cases if you
| just ignore the Earth's curvature.
| misthop wrote:
| 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
| defrost wrote:
| 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...
| colgate_total wrote:
| Another optimization would be to compare square of distance
| instead of distance, saving "Math.sqrt" call each iteration.
| geraldwhen wrote:
| 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.
| piotrjaw wrote:
| Damn, this is a great point, thank you!
| piotrjaw wrote:
| I've actually added this to the article, thank you again!
| bunabhucan wrote:
| 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.)
| sobriquet9 wrote:
| > 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.
| bunabhucan wrote:
| 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.
| sobriquet9 wrote:
| 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.
| hakuseki wrote:
| 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.
| danbruc wrote:
| 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.
| piotrjaw wrote:
| 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.
| bumbledraven wrote:
| This problem is traditionally known as finding the "diameter" of
| a set of points, e.g.
| https://stackoverflow.com/questions/27414060/find-the-diamet...
| SquibblesRedux wrote:
| I was hoping this article was about mathematical methods. I was
| disappointed to see it was actually about a Javascript library.
| brookst wrote:
| Pretty much sums up the experience of working in tech.
| NoToP wrote:
| Almost. He could have completely side stepped doing any
| problem solving or mathematical / logical reasoning by
| applying machine learning to it.
___________________________________________________________________
(page generated 2022-12-16 23:01 UTC)