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 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].
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.
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.
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.
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?
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.
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.
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.)
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.
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!
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.
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.
43 comments
[ 5.4 ms ] story [ 50.4 ms ] threadhttps://chalkdustmagazine.com/blog/sylvesters-convex-hull-pr...
3% of a large cpu intensive runtime was sqrt.
[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.
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.
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.
Some religious folks might find it a bit offensive. Thank you! (some alternatives: dang, darn, gosh, blimey, golly, etc.)
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?
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
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.
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?
One callout if folks think about implementing something similar. Euclidean distance on a sphere has unintended consequences. Great circle distance would be more appropriate.
Working on the a floor plan or proof of concept? Euclidean metric absolutely works.
Working on Mercator projections or legal type stuff? eh....
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.)
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.
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.
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.
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.