you can try this (did this in QGIS 2.16)
- fixed distance buffer each point by 250m (this is half the required distance between points)
- then dissolve all on the result of that
- then use multipart to singlepart to split each cluster into its own feature
- add a field (using the expression @row_number) to assign a unique ID to each cluster.
you then get something like this...
Now use join attributes by location on your points layer to find out which cluster each point falls inside (using 'within'/'take attributes of first selected feature').
Finally the Concave hull plugin. Sadly this doesn't appear to support "by field" concave hulls like the Convex hull functionality. So you'll need to select and export each cluster yourself and run Concave Hull on each one separately. Here's what cluster #1 looks like as a concave hull...
So each point within that cluster is within 500m of another point in that cluster.
Note that a point with no neighbours within 500m will probably have a concave hull which collapses to a point. And one with only one neighbour will probably have a concave hull which is a line. I haven't tested these, though.
Tip - 800k is a lot of points. For your own productivity and to avoid
frustration, I suggest you try this on a small region, or a small
random selection of your data first. It's easy to get an option wrong,
and this could take some time on a set that large ;) This might be done faster with postgis