guidelines for getting consistent results

[michael-ts]

I'm looking for guidelines for getting consistent results.

I started off with a data set of around 250k GPS points. I got great results, but as I add more points I am seeing inconsistency. For instance, initially it took around 20 seconds to run, but after adding points, suddenly it dropped to around 2 seconds despite there being more points! It also seems to sometimes improperly gap across points on the map instead of following the concave shape, even in areas nowhere near where new points were added.

I thought to fix this problem by taking the resulting set of points from a good run with concaveman and then adding the new points and rerunning the algorithm. This worked fine the first time, but the second time it seems to have become intractible, running over 20 minutes before I interrupted the process, with only 26.3k points in the input, of which 21.6k were from the previously found results.

I'm mostly using the default concavity of 2, except occasionally I have pushed it as low as 1.3 when I find the output has weird jumps where it shouldn't. There seems to be some kind of threshold where as I lower the number it takes about the same amount of time and then suddenly it becomes intractible again. In the latest case, I found that if concavity was 2.4491023 or above, it would consistently take between 2.0 and 2.2s to complete, but at 2.4491022 and below it would never seem to finish. Upping the length threshold has no effect. However, the results in this case are unacceptable as there are several cases where I see what appear to be lines drawn between distance points on the perimeter, as well as spots where the results aren't concave enough.

Are there any guidelines as to how I can get better results? Should I sort the points by some criteria? Am I expected to sort the output (could this be why I sometimes see lines between distance points when I plot the coordinates on a map)? Is there a limit on how many points I should try to pass? Should I format the numbers differently, e.g. could GPS coordinates with 8 or nine digits after the decimal place run into precision issues or something?

[district10]

Any testing data on this?

I released a python pip package: concave hull based on this. I may spare some time having a look.

GPS points are in WGS84, it's not cartesian coords (lon:lat != 1:1). Though it may not be a serious problem (still linear in lon/lat direction).

[michael-ts]

I can confirm these are WGS84 coordinates. An additional data point - for a while now the algorithm has been mostly behaved, only producing a gap in one area where there is a bit of an "exclave" of points just outside the boundary. I'm attaching a screenshot to illustrate - the green circles are the generated concave hull; the bluish colors are from the actual data:

However, recently the entire bottom of my general well behave semi-rectangular area had the entire bottom go missing after adding a bunch of point from a different location in the world. I'm not sure if maybe I should filter out those points first, or if it is a larger symptom of the same problem with the above exclave.

[michael-ts]

I realize this isn't enough data to do much with, but I'm not sure of a good way to share the actual data ... I would rather not make most of the dataset public, and even shared privately it's a lot of data: currently at 2,115,758 points (25,796 points in the concave hull). Let me know what would work best for you even if it's to go away and not bother you. ;-)

[district10]

the green circles are the generated concave hull; the bluish colors are from the actual data

I'm confused. @michael-ts

---

I use concaveman to generate ground boundary for a local map (geojson format, in WGS84) and it works pretty well:

In my processing of this these ground features (e.g. lane line of geometry=LineString), there are several key points:

1. convert WGS84 to local cartesian coordinates (I'm using ENU converted by mapbox/cheap-ruler), so metric system (distance between points, point to line segment) used by concaveman is correct
2. densify input polylines (my map data may already douglas simplified and it sparse, that's bad for concaveman) to avoid narrow 'tunnel's (see picture below); or you may even buffer your input polylines

(should cluster data into three parts, then use concaveman)

So tips could be:

• If your gps points are actually gps tracks/trajectories and are quite sparse, you may need densify it first
• If your data contains some kind of 'tunnel' between clusters, you need to cluster your data then use concaveman for each cluster instead of feeding them all in once

(Finally, you may add some bias to your data (transform them into another country) to share part of them.)

[michael-ts]

It seems in my case it doesn't even create the tunnels for some reason.

In my original problem I did run into the issue of sparseness when I tried to make things "easier" on concaveman by using its previous output. I stopped doing that and do get better results. :-)

For now all the data I'm interested in finding the perimeter boundary of is within a nice well defined rectangle only a few miles on a side, so I have added a filter to remove points outside this rectangle before passing to concaveman. This works nicely. The only weird hiccup left is the one I screenshotted where the "exclave" as I call it, where the boundary skips some space, is actually only two or three hundred feet west and I can live with it until points are added which properly close the boundary.

I'll see if I can transform at some point when I get a chance or come up with some kind of test case that fails, but they very closely follow a pretty complete street map of several square miles making the location identifiable to anybody familiar enough with the area even if superimposed on the wrong location. :-)