Re: [boost] [geometry] area, length, centroid, behavior

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-02-25 17:00:26

Thanks for all your answers!

> I have a collection of objects in a 2-d space.  Some do not have a 
> measurable extent so they are modeled as points.  Some have a 
> measurable extent only in a single dimension so that are modeled as 
> oriented line segments.  I want the centroid of the system.  I also 
> want the center of mass where mass is proportional to substance, i.e., 
> area.  Here points and line segments have an area of zero and hence a 
> mass of zero.  I could handle this, of course, by adding code that 
> extends the concept of area so that by explicit test the area+ is 
> equal to the area of a polygon and  equal to 0 for a line-segment a 
> polyline or a point, but that is just saying that the model is 
> inadequate for this purpose and I would need to write special code to 
> extend it in this quite reasonable way.
>
> If I go to the trouble of declaring things so that points and 
> line-segments and polylines and polygons can all be used "together" 
> then I probably want to treat them this way.  If I don't, then I 
> should have to eliminate that case explicitly by testing -- just as I 
> would if I wanted to exclude the use of area of a concave or 
> self-intersecting polygon.
>
I agree with this completely. I have a layer, templated by geometry 
object, so layer<G>. Inside it has a geometry collection, e.g. 
std::vector<G>. I have a selection dialog where users can define 
expressions such as area > 0. The displayed functions/properties might 
be hidden for certain geometry types. However, if area is not defined at 
all, the system will not compile and as a library user I would have to 
invent tricks such as the area+ or templatizing all the list of 
functions/properties. This is not a hypothetical use case, I have a 
layer like this and a dialog like this.

> Shapes, volumes, etc. are sets of points. Various sets have a null 
> area. This is perfectly valid and is not a logic error
I am glad with this definition because this is also the way we use it. 
We have modelled our library by Egenhofer/OGC mathematical concepts, so 
also relations like intersection/union/intersects/overlaps are all 
"Point-Set Topological Spatial Relations". So null area makes sense.
> If you consider a point a 0-dimensional object placed in the n-dimensional space you're working with, it doesn't
> have an extent over any number of dimensions. If, however, you consider it an n-dimensional object with an extent of 0 along every dimension, it
> does have length, area, volume, and whatever you want to call hyper-volumes in more than 3 dimensions, all of them being 0.
>   
"Formally" we have a point defined as an object with topological 
dimension of 0 (so a 0-dimensional object, there are many types of 
dimensions around)

> I also think it is a bad idea to provide a catchall default area() function that returns zero for every concept that doesn't have an override area() function.
You can make a default which does returns area of zero for any geometry, 
and a separate specialization which gives a compilation error for any 
non-defined type.

> Do you provide an is_closed, or is_overlapped, or things of that nature for checking the validity of a
> polygon?  Is a valid polygon a precondition of all functions that work on polygons, or do you intend to check for validity in every function?
is_closed will be provided. is_valid will be provided. is_simple 
(meaning there are no self-intersections and self-tangencies) will be 
provided. There is also a "correct" algorithm which will close the 
polygon and correct its winding direction.

> it is also unreasonable to assume a winding direction convention.  If your polygon concept requires these three conditions (not empty, closed and CC winding) you are excluding 7/8 legacy data types if we assume each decision is made arbitrarily.
We assume closed polygons with specific windings in our algorithms. For 
Legacy-polygons we provide the "correct" algorithm.

> An invalid polygon shouldn't be allowed in the first place. Ideally, 
> that should be prevented by the type system.
> One option is to prohibit invalid polygons, i.e. to make it impossible 
> to construct one with too few points.  I suspect that this would lead 
> to other problems though

I do not think that is possible, we handle polygons from 4 to millions 
of points, it is a runtime collection.

> A point is a 0-simplex. It has no units (dimensionless) in content 
> space. A line segment is a 1-simplex. It has units of length in 
> content space. The 2-simplex (triangle) has units of area. A 3-simplex 
> has units of volume and so forth with increasing dimension.
Topological_dimensions are indeed a very useful meta-function with which 
we templatize some dispatch structures.

> On the other hand, I would say that the "length" of a polygon is too 
> ambiguous -- some degeneracy needs to be available to disambiguate.
I think most if not all people considered the length for a polygon for 
its perimeter a bad idea. Zero then? Because there still is the usecase 
for the generic collection and my selection dialog having the length 
function/property as well. So it should compile. We still have the 
exception to be thrown, nobody reacted on that. In this specific case it 
might be a compromise: it compiles, providing generic collections, but 
should not be called.

We want to provide a library which is mathematically correct and at the 
same time offers enough flexibility. The general idea is that the 
results should be has "homogeneous" as possible from one geometry to 
another, so the particular case of a point shouldn't break the whole 
machine. Therefore I'm glad that there is a mathematical viewpoint which 
says that it is perfectly valid to consider a point having an area of 
zero, a polygon being a pointset.

So if I may summarize/propose:
- area: defined for all, returning 0 for point/linestrings, area for 
polygons, exception for polyhedrons or DIM>3
- length: defined for all, returning length for linestrings, 0 for the 
rest of them, exception for polygon
- centroid: defined for all

other relevant functions mentioned here:
- topological_dimension
- correct
- is_valid
- is_closed
- is_simple
- volume, returning 0 for all objects with topological dimension < 3, 
exception for > 3
- perimeter, returning 0 for all except polygon

and finally we might define:
- content, returning 0 for a point, the length of a linestring, area of 
a polygon, volume of a polyhedron, hypervolume of a polytope

With as explanation a quote (off-list) of my co-author Bruno:
> All this can be seen as a conceptual approximation as we force ourself to view every dimension as a
> particular case here. Really generic would state that the length of a linestring, the area of a polygon and the volume
> of a polyhedron are conceptually exactly the same thing, that is: the quantity of space units inside a geometry. 

Regards, Barend