Calculate the area of points

Question

I was not able to find good answers in Google, or perhaps I am just missing the correct key words. Any help or suggetions are welcome!

My problem is the following: I want to calculate the area a certain point cloud covers (in 2D). I know that mathematically speaking the area is 0, but I am only able to take sample points out of the correct distribution. Additionally I do not have any information about the boundary of the point cloud, every shape is possible, including holes etc. So algorithms using the boundary of a manifold will not work?!.

Since the functions I am working with are smooth I can assume that the space in between points also belongs to the area I want to calculate.

At the moment I divide the space into a lot of small boxes and count how many boxes are populated with one or more points. The count multiplied with the box size gives me an area.

Is there a more elegant solution to this? Any ideas?

Thanks Thomas

---

EDIT:

What I do is projecting high dimensional points to a low dimensional embedding. I can determine the number of points in the high dimensional space and therefore also the number of points in the low dimensional space which form the area I want to calculate. If I increase the number of points it turns out that they are positionned between the "old" points, that is what I mean by smooth. Given a certain point I can assume that in some proximity around that point I will be able to find new points belonging to the area if I sample more dense.

Additionally I have a threshold value at which I can consider two points to be "equal", or in other words I know which resulution I want to achieve.

---

EDIT 2:

I use GPLVM's to do the mapping from high dimensional space to low dimensional space. So I think analysing that directly is two difficult/not possible. They are not very intuitive and I think in that case it is easier to work directly with the two dimensional points...

Answer 1

One option would be to find the convex hull of your set of points, that is, the convex polygon that contains all your points. Once you have the polygon, you can then find the area covered.

Of course, this won't handle the case where your underlying distribution has holes though, in which case I can't think of a better solution than your box-laying variant.

Answer 2

There is a simple statistical approach (see Tuomi and Larjavaara, QJR Meteorol. Soc. (2005) 131, p. 1191, Appendix). A representative area of a reasonably regular set of points (say lightning strikes under a thundercell) is A = 12 Sx Sy sqrt(1 - R2). The standard deviations Sx and Sy (times a constant) define a rectangle, and the correlation factor (R is the correlation coefficient) tells how large part of the rectangle is effectively covered by the points. This result is not high mathematics but works well in practice for, say, estimating the lightning flash density of a cell. - Tuomi

Answer 3

You need to give some more definition on what you mean by area here. If all the space between points is filled, then just sample the boundary points and calculate the polygon's area. However, if you can sample the full distribution and determine both whether a position is in a filled or an empty area, then your approach makes more sense.

I can't see how the underlying distribution varies smoothly - either a point is filled or not, it would seem. However, if you are sampling a density distribution, where there is a variable density at each position, then you are actually performing an area integral or quadrature, for which there are many ways of approximating the underlying distribution with an analytic function.

If the underlying distribution is not continuous (varying smoothly) but discrete, then you are effectively finding the area of a fractal. For that, you need to evaluate the area via your method several times for increasingly fine grids, until the value stops changing. For a fractal, the value never stops changing, but for a finite dataset it will stop eventually.