6 ms·
Calculating the maximum diagonal distance in a given set of points
- SquibblesRedux 4y agoI was hoping this article was about mathematical methods. I was disappointed to see it was actually about a Javascript library.
- misthop 4y agoIt 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 https://en.wikipedia.org/wiki/Convex_hull_algorithms
- defrost 4y agoIf we're looking at the hull story, J J Sylvester might be of tangential interest to some. https://chalkdustmagazine.com/blog/sylvesters-convex-hull-problem/ https://chalkdustmagazine.com/blog/sylvesters-convex-hull-pr...
- colgate_total 4y agoAnother optimization would be to compare square of distance instead of distance, saving "Math.sqrt" call each iteration.
- geraldwhen 4y agoMath.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.
- danbruc 4y agoIf 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 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 4y agoIndeed, 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.
- SuperFine 4y agoThe 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 4y agoDamn way to be a condescending dickhead.
- SuperFine 4y agoPlease 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.)
- twic 4y agoA condescending gollyhead? I think that might be worse.
- eddsh1994 4y agoDamn way to be a condescending blimey?
- helloooooooo 4y ago
- isoprophlex 4y agoWhy 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?
- dang 4y agoWe'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 https://news.ycombinator.com/newsguidelines.html.
- jgrahamc 4y agoWe had to do this in 144 dimensions: https://blog.cloudflare.com/computing-euclidean-distance-on-144-dimensions/ https://blog.cloudflare.com/computing-euclidean-distance-on-...
- piotrjaw 4y agoImpressive, thank you for sharing!
- clusterhacks 4y agoFun! 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?
- tomrod 4y agoNeat 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 4y agoIt's not even a correctly normalized Euclidean distance.
- piotrjaw 4y agoThat 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 4y agoNo 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....
- bunabhucan 4y agoIt'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 https://imgur.com/a/NEwNxVl Circle: https://i.imgur.com/omKqty4.png 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 4y ago> 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 4y agoDo 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.
- hakuseki 4y agoA 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.
- sobriquet9 4y agocos(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.
- piotrjaw 4y agoIndeed, 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.
- bunabhucan 4y agoCan 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!
- bumbledraven 4y agoThis problem is traditionally known as finding the "diameter" of a set of points, e.g. https://stackoverflow.com/questions/27414060/find-the-diameter-of-a-set-of-n-points-in-d-dimensional-space https://stackoverflow.com/questions/27414060/find-the-diamet...
- Waterluvian 4y agoI 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.
- piotrjaw 4y agoSame 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.