1

We have thousands of points on a map. The points are measurements that are taking periodically as a person moves around, so the position of each point is random within a window, but when you look at the data you can see the paths taken. In order to render the data faster (its a slug right now), I want to convert the clustered points into polygons and draw those instead (I can deal with the lost detail by picking the right polygon detail for the zoom level).

Are there any good fast algorithms for doing such a thing?

michael
  • 2,577
  • 5
  • 39
  • 62
  • For future readers : similar question (with good answers) ==> https://stackoverflow.com/questions/18416861/how-to-find-convex-hull-in-a-3-dimensional-space – cppBeginner May 22 '19 at 02:59

3 Answers3

2

What do you want the polygon to represent? Do you mean a polygon as in a closed region covering the area of the moved path (i.e. the boundary only)? Or an exact polygon of line segments between all visited points? The latter would be no faster to draw than the points themselves, as it would be a polygon with as many corners as you have points.

If the person moves around in an area (such as a delivery driver covering a part of a city), then you could approximate his "covered area" by the convex hull of the points. This is a closed convex polygon with somewhere between 3 and N corners, if you have N points in the data set.

Definition

http://mathworld.wolfram.com/ConvexHull.html

Algorithms

http://en.wikipedia.org/wiki/Convex_hull_algorithms

If you want to make an approximation of the path rather than some covered area, you could always make a crude LOD algorithm by (say) drawing every 7 points, then every 5, then every 3 points when the user zooms in further. A more sophisticated LOD algorithm could start off with points p0 and p1, use the direction through those points and look at the distance from the direction line to p2. If p2 is close enough to the line it is skipped, and p3 is investigated. If there is a large enough change in direction of travel, mark the last two points as the current course and repeat. The allowed change in direction will be the LOD parameter determining how many points are drawn. This algorithm will try to approximate the "important" points on the path (where the direction changes).

Anders Forsgren
  • 10,827
  • 4
  • 40
  • 77
0

For clustered points you can use deck gls hexagon layer, from the docs -> The Hexagon Layer renders a hexagon heatmap based on an array of points. It takes the radius of hexagon bin, projects points into hexagon bins. The color and height of the hexagon is scaled by number of points it contains.

https://github.com/uber/deck.gl/blob/master/docs/layers/hexagon-layer.md

super cool example of this -> http://deck.gl/#/examples/core-layers/hexagon-layer

OluO
  • 94
  • 3
0

I think it's impossible to know the exact path that was taken, but it would be a fairly reasonable assumption to assume that the closest point to a given point is the next point on the path. I'm not sure what size polygons you're dealing with, but ultimately you would calculate which point on the map is closest to the current one, and that one would be the next point in the polygon. If your polygon is very very large, you would need to calculate the great circle distance between the points to ensure accuracy.

Jon Martin
  • 3,252
  • 5
  • 29
  • 45
  • hmmm. Read the question again. Its not quite what you are answering. I am asking if there is a fast algorithm for approximating a cluster of points with a polygon. – michael Aug 02 '11 at 18:51
  • Yeah but my answer gave you an algorithm. Whether it's fast or not is to be determined. – Jon Martin Aug 02 '11 at 18:52