headers
Mathias Gaunard | 8 Oct 00:51

Geometry and spatial indexes, my opinion

Hi,

Wanting to code a simple 3D virtual world, I looked into the recent 
spatial indexes SOC work, which depends on the proposed geometry library.

I have to admit I was fairly disappointed.
So I'm going to put some critics, some quite harsh maybe, along with 
some ramblings about what I would have liked to have.
Note that I am no geometry or space indexing expert, so what I say may 
be perfectly silly.

For starters, I think those libraries should be dimension agnostic and 
generic. Geometry not only has a strong 2D bias, but the documentation 
also says geometry::box only works with point_xy (and point_ll).
Since it is used everywhere in spatial index, that means it's unusable 
on 3D.

The geometry documentation doesn't clearly state what a geometry::box 
is. Is it (assuming 2D) any rectangle or only axis-aligned rectangles?
In case it is just any rectangle, it mind be interesting to introduce a 
new type for axis-aligned ones, which can always be defined from two 
points whatever the dimension (well, at least it seems enough for 3D, 
I'm not good at projecting in other dimensions to see if that'd work).
I suppose the spatial index interface expects axis-aligned boxes, so 
it's fairly important to clarify what we're talking about.

Apart from that, there is also lots of point_xy-dependent code in 
spatial indexes. Also the quadtree implementation isn't dimension 
agnostic in particular (it should have 2^n children nodes, and not 4).
I don't really get why it uses shared_ptr everywhere either (is it
(Continue reading)

Permalink | Reply |
headers
Brandon Kohn | 8 Oct 01:36
Favicon

Re: Geometry and spatial indexes, my opinion

--------------------------------------------------
From: "Mathias Gaunard" <mathias.gaunard <at> ens-lyon.org>
Sent: Tuesday, October 07, 2008 5:52 PM
To: <boost <at> lists.boost.org>
Subject: [boost] Geometry and spatial indexes, my opinion

> Hi,
>
> Wanting to code a simple 3D virtual world, I looked into the recent 
> spatial indexes SOC work, which depends on the proposed geometry library.
>
> I have to admit I was fairly disappointed.
> So I'm going to put some critics, some quite harsh maybe, along with some 
> ramblings about what I would have liked to have.
> Note that I am no geometry or space indexing expert, so what I say may be 
> perfectly silly.
>
> For starters, I think those libraries should be dimension agnostic and 
> generic. Geometry not only has a strong 2D bias, but the documentation 
> also says geometry::box only works with point_xy (and point_ll).
> Since it is used everywhere in spatial index, that means it's unusable on 
> 3D.
>

Hi Mathias,

I just wanted to say something here about dimensional agnosticism. I don't 
think this is necessarily the way to go. There are a couple of reasons that 
I say this. The more trivial point is that higher than 3D geometry isn't 
likely to be supported and isn't of much practical use anyway. The second
(Continue reading)

Permalink | Reply |
headers
Patrick Mihelich | 8 Oct 10:37

Re: Geometry and spatial indexes, my opinion

Hi Brandon,

Hi Mathias,
>
> I just wanted to say something here about dimensional agnosticism. I don't
> think this is necessarily the way to go. There are a couple of reasons that
> I say this. The more trivial point is that higher than 3D geometry isn't
> likely to be supported and isn't of much practical use anyway.

Strongly disagree! Spatial index structures are very commonly used to
accelerate nearest neighbor search, an important operation in numerous
fields. There is a nice listing at
http://en.wikipedia.org/wiki/Nearest_neighbor_search#Applications. The
search space in such applications may have hundreds of dimensions. In
computer vision we use nearest neighbor search for keypoint matching, which
in turn is fundamental to content-based image retrieval, visual odometry,
wide-baseline stereo, simultaneous localization and mapping, panorama
stitching, and the list goes on.... Computational geometry has many, many
applications beyond the obvious ones (e.g. collision detection), and
restricting yourself to 3 dimensions or fewer is rather crippling.

In my opinion, a Boost geometry library must have at least basic support for
n-dimensional computational geometry. Let's start with able to handle points
of arbitrary dimension and calculate distances between them (given some
metric). This is easy to do and already sufficient to implement many useful
spatial indices. I have not looked at Barend's geometry library in detail,
but on the surface it looks generic enough to support this.

The second point is on the basis of coordinate frameworks. While I agree
> that any library shouldn't necessarily be limited to 2D, I don't think that
(Continue reading)

Permalink | Reply |
headers
Bruno Lalande | 8 Oct 10:57

Re: Geometry and spatial indexes, my opinion

Hello

> In my opinion, a Boost geometry library must have at least basic support for
> n-dimensional computational geometry. Let's start with able to handle points
> of arbitrary dimension and calculate distances between them (given some
> metric). This is easy to do and already sufficient to implement many useful
> spatial indices. I have not looked at Barend's geometry library in detail,
> but on the surface it looks generic enough to support this.

This is already done. Making the distance algorithm dimension-agnostic
is the first thing I did with Barend after the preview 2, when I
joined the project. And the iteration between dimensions is obviously
made at compile-time.

Looks like we *really* have to show the preview 3 as soon as possible :-)

Regards
Bruno
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Brandon Kohn | 8 Oct 16:51
Favicon

Re: Geometry and spatial indexes, my opinion

Hi Patrick,

:)
--------------------------------------------------
From: "Patrick Mihelich" <patrick.mihelich <at> gmail.com>
Sent: Wednesday, October 08, 2008 3:37 AM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

> Hi Brandon,
>
> Hi Mathias,
>>
>> I just wanted to say something here about dimensional agnosticism. I 
>> don't
>> think this is necessarily the way to go. There are a couple of reasons 
>> that
>> I say this. The more trivial point is that higher than 3D geometry isn't
>> likely to be supported and isn't of much practical use anyway.
>
>
> Strongly disagree! Spatial index structures are very commonly used to
> accelerate nearest neighbor search, an important operation in numerous
> fields. There is a nice listing at
> http://en.wikipedia.org/wiki/Nearest_neighbor_search#Applications. The
> search space in such applications may have hundreds of dimensions. In
> computer vision we use nearest neighbor search for keypoint matching, 
> which
> in turn is fundamental to content-based image retrieval, visual odometry,
> wide-baseline stereo, simultaneous localization and mapping, panorama
(Continue reading)

Permalink | Reply |
headers
Patrick Mihelich | 8 Oct 23:33

Re: Geometry and spatial indexes, my opinion

On Wed, Oct 8, 2008 at 7:51 AM, Brandon Kohn <blkohn <at> hotmail.com> wrote:

> Ok, I take your point. I wasn't suggesting that a library not be able to
> handle more than 3 dimensions. Rather I would suggest that the population of
> developers who have such requirements must be very small. Considering that
> generalization on dimension is not trivial for many algorithms, this leads
> me to the conclusion that the specific algorithms will decide the
> requirements on their inputs. This is why I chose a traits based interface
> for the geometry library I've been implementing. There's nothing to stop one
> from creating a multi-dimensional Cartesian/polar/parametric access traits
> interface for any algorithm which requires it. So I suppose I agree, the
> geometry library should not constrain on the number of dimensions. But I
> don't agree with full agnosticism (to mean agnosticism of coordinate frame
> as well.) There should be a way to differentiate points further to align
> with the concrete traits of the dimension they describe.

This sounds reasonable. Certainly there are many 2D/3D algorithms for which
there is little point in generalizing to higher dimensions.

> Yes, I have taken a slightly different route than the other libs I have
> found in the vault. In my library the algorithms require inputs conform to a
> specific access traits concept. I have been using get_x, get_y, get_z as the
> general interface for cartesian (and would have used get_r, get_theta,
> get_phi for the others.. if I had gotten to that), but I think now that I'm
> fairly well persuaded to investigate a compile time indexed mechanism like
> boost::tuple. Has anyone done a performance test on using such a mechanism
> in practical settings? While I'm sure it's constant, how big is that
> constant in practice? Is it worth paying in cases where an algorithm
> requires a constrained dimensionality? I'm guessing nobody has really
> addressed these questions... so perhaps I'll take a gander and see if it's
(Continue reading)

Permalink | Reply |
headers
Michael Fawcett | 8 Oct 23:53

Re: Geometry and spatial indexes, my opinion

On Wed, Oct 8, 2008 at 5:33 PM, Patrick Mihelich
<patrick.mihelich <at> gmail.com> wrote:
>
> Cool, compile time indexing is very useful. But, I'm not sure I see the need
> for using tuples. I can't offhand think of a use case where the dimensions
> are of heterogeneous type, so wouldn't a simple array work?

Sure a simple array should work.  The point of a generic library is
that a simple array would work, so would a tuple, and so would your
custom point class.

As for the heterogeneous types, think of huge (GBs worth) digital
elevation models in meter units where altitude is in a range from 0 -
20,000m.  In that case, my point type would be something like
vector3<int, short, int> instead of a vector3<int>.

With a 1024x1024 file, that would result in a savings of only 2MB of
memory, but extrapolate that out to a 16384x16384 file, and the
savings is 500MB.

--Michael Fawcett
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Patrick Mihelich | 9 Oct 01:23

Re: Geometry and spatial indexes, my opinion

On Wed, Oct 8, 2008 at 2:53 PM, Michael Fawcett
<michael.fawcett <at> gmail.com>wrote:

> On Wed, Oct 8, 2008 at 5:33 PM, Patrick Mihelich
> <patrick.mihelich <at> gmail.com> wrote:
> >
> > Cool, compile time indexing is very useful. But, I'm not sure I see the
> need
> > for using tuples. I can't offhand think of a use case where the
> dimensions
> > are of heterogeneous type, so wouldn't a simple array work?
>
> Sure a simple array should work.  The point of a generic library is
> that a simple array would work, so would a tuple, and so would your
> custom point class.
>
> As for the heterogeneous types, think of huge (GBs worth) digital
> elevation models in meter units where altitude is in a range from 0 -
> 20,000m.  In that case, my point type would be something like
> vector3<int, short, int> instead of a vector3<int>.
>
> With a 1024x1024 file, that would result in a savings of only 2MB of
> memory, but extrapolate that out to a 16384x16384 file, and the
> savings is 500MB.

OK, yes, I'm convinced. Support for heterogeneous types has its uses. But I
will still ask, why use a tuple to store the data in the basic (Cartesian)
point class? Barend and Bruno's library uses an array instead, which I think
should be preferred for two reasons. (1) I would still think the homogeneous
case to be much more common the heterogeneous case. (2) Using a tuple makes
(Continue reading)

Permalink | Reply |
headers
Bruno Lalande | 9 Oct 10:48

Re: Geometry and spatial indexes, my opinion

Hi,

>> > Cool, compile time indexing is very useful. But, I'm not sure I see the
>> need
>> > for using tuples. I can't offhand think of a use case where the
>> dimensions
>> > are of heterogeneous type, so wouldn't a simple array work?
>>
>> Sure a simple array should work.  The point of a generic library is
>> that a simple array would work, so would a tuple, and so would your
>> custom point class.
>>
>> As for the heterogeneous types, think of huge (GBs worth) digital
>> elevation models in meter units where altitude is in a range from 0 -
>> 20,000m.  In that case, my point type would be something like
>> vector3<int, short, int> instead of a vector3<int>.
>>
>> With a 1024x1024 file, that would result in a savings of only 2MB of
>> memory, but extrapolate that out to a 16384x16384 file, and the
>> savings is 500MB.
>
>
> OK, yes, I'm convinced. Support for heterogeneous types has its uses. But I
> will still ask, why use a tuple to store the data in the basic (Cartesian)
> point class? Barend and Bruno's library uses an array instead, which I think
> should be preferred for two reasons. (1) I would still think the homogeneous
> case to be much more common the heterogeneous case. (2) Using a tuple makes
> it difficult or impossible to use the generic point class in high
> dimensions. Consider
(Continue reading)

Permalink | Reply |
headers
Patrick Mihelich | 9 Oct 13:23

Re: Geometry and spatial indexes, my opinion

On Thu, Oct 9, 2008 at 1:48 AM, Bruno Lalande <bruno.lalande <at> gmail.com>wrote:

> Stop me if I'm wrong but what you're discussing now is how to
> implement the point class provided by an ideal geometry library,
> right? If so, I think it's not the most important concern since, as
> I've already said, the primary goal is not to provide a point class
> but to define how points are accessed and defined in general. I think
> that, by talking about tuples, Brandon was rather pointing out that
> points should be accessible the same way as tuples: get<N>(p). Which
> is quite a general consensus now, IMO.

OK, perhaps I misinterpreted Brandon's comment. I have been getting caught
up on the March discussions, so apologies if I rehash old debates. If he was
simply advocating compile-time indexing via get<N>(p) or similar syntax,
then I completely agree. This should be required by the Point concept (or
Coordinate concept? I do not quite understand the distinction).

On the other hand, I'm worried to see that the geometry::point
implementation (at least the version included with SpatialIndexes) supports
only compile-time indexing. I think we must also have a RuntimeIndexable
concept, to which a particular point type may or may not conform.
RuntimeIndexable would require an indexing operator[], so it can only be
modeled by homogeneous points. Iterators via begin() and end() could be
useful as well. I have a couple of reasons for wanting this, as usual
motivated by high dimensional spaces...

First, some algorithms require runtime indexing. kd-trees are an interesting
example. When constructing a kd-tree over a data set, we need some heuristic
to decide which dimension to split on at each tree node. In 2 or 3
dimensions, usually you simply cycle through the dimensions in order, for
(Continue reading)

Permalink | Reply |
headers
Brandon Kohn | 9 Oct 16:25
Favicon

Re: Geometry and spatial indexes, my opinion

--------------------------------------------------
From: "Patrick Mihelich" <patrick.mihelich <at> gmail.com>
Sent: Thursday, October 09, 2008 6:23 AM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

> On Thu, Oct 9, 2008 at 1:48 AM, Bruno Lalande 
> <bruno.lalande <at> gmail.com>wrote:
>
>> Stop me if I'm wrong but what you're discussing now is how to
>> implement the point class provided by an ideal geometry library,
>> right? If so, I think it's not the most important concern since, as
>> I've already said, the primary goal is not to provide a point class
>> but to define how points are accessed and defined in general. I think
>> that, by talking about tuples, Brandon was rather pointing out that
>> points should be accessible the same way as tuples: get<N>(p). Which
>> is quite a general consensus now, IMO.
>
>
> OK, perhaps I misinterpreted Brandon's comment. I have been getting caught
> up on the March discussions, so apologies if I rehash old debates. If he 
> was
> simply advocating compile-time indexing via get<N>(p) or similar syntax,
> then I completely agree. This should be required by the Point concept (or
> Coordinate concept? I do not quite understand the distinction).
>
> On the other hand, I'm worried to see that the geometry::point
> implementation (at least the version included with SpatialIndexes) 
> supports
> only compile-time indexing. I think we must also have a RuntimeIndexable
(Continue reading)

Permalink | Reply |
headers
Bruno Lalande | 9 Oct 16:51

Re: Geometry and spatial indexes, my opinion

> Actually in the library I've been working on the definition of the point
> type is of lesser importance. All of my algorithms are designed to access
> point coordinates via a traits specialization which details how the point's
> coordinates are accessed. It works like this (please excuse email formatting
> :)

As said several times by several people including me, it's exactly
what everybody out there is doing. There's nothing fundamentally new
in what you propose and in the code you just pasted.

That's precisely why I've just said (like you) that the definition of
a point type in not really important.

Bruno
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Brandon Kohn | 9 Oct 17:10
Favicon

Re: Geometry and spatial indexes, my opinion


--------------------------------------------------
From: "Bruno Lalande" <bruno.lalande <at> gmail.com>
Sent: Thursday, October 09, 2008 9:51 AM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

>> Actually in the library I've been working on the definition of the point
>> type is of lesser importance. All of my algorithms are designed to access
>> point coordinates via a traits specialization which details how the 
>> point's
>> coordinates are accessed. It works like this (please excuse email 
>> formatting
>> :)
>
> As said several times by several people including me, it's exactly
> what everybody out there is doing. There's nothing fundamentally new
> in what you propose and in the code you just pasted.
>

The library I've written is the only one in the vault which uses this 
mechanism. Your library in the vault directly accesses the interfaces for 
the underlying points, segments and polygons:

Point: (from intersection_linestring.hpp)

bool clip_segment( const box<PB>& b,
                               segment<PS>& s,
                               bool& sp1_clipped,
                               bool& sp2_clipped) const
(Continue reading)

Permalink | Reply |
headers
Barend Gehrels | 9 Oct 17:39
Favicon

Re: Geometry and spatial indexes, my opinion

Hi Brandon,

Brandon Kohn wrote:
>
> The library I've written is the only one in the vault which uses this 
> mechanism. Your library in the vault directly accesses the interfaces 
> for the underlying points, segments and polygons:

Our library, as it is currently in the boost vault folder, is uploaded 
by Federico for his GSoC project (to create a compiling source code 
set). It is not managed by Bruno and me. You're looking at a random 
piece of code of an intermediary stage, something soon after preview 2. 
The new version will be published very soon.

It generally refers to points as Bruno has mentioned, in the tuple way. 
However, there is also support for xy-points and latlong-points.
Some algorithms might (still) refer to those types of points.

Regards, Barend

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Brandon Kohn | 9 Oct 19:09
Favicon

Re: Geometry and spatial indexes, my opinion

--------------------------------------------------
From: "Barend Gehrels" <barend <at> geodan.nl>
Sent: Thursday, October 09, 2008 10:39 AM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

> Hi Brandon,
>
>
> Brandon Kohn wrote:
>>
>> The library I've written is the only one in the vault which uses this 
>> mechanism. Your library in the vault directly accesses the interfaces for 
>> the underlying points, segments and polygons:
>
> Our library, as it is currently in the boost vault folder, is uploaded by 
> Federico for his GSoC project (to create a compiling source code set). It 
> is not managed by Bruno and me. You're looking at a random piece of code 
> of an intermediary stage, something soon after preview 2. The new version 
> will be published very soon.
>
> It generally refers to points as Bruno has mentioned, in the tuple way. 
> However, there is also support for xy-points and latlong-points.
> Some algorithms might (still) refer to those types of points.
>
> Regards, Barend
>
>
>
> _______________________________________________
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 20:00
Favicon

Re: Geometry and spatial indexes, my opinion

Brandon wrote:
>I posted this to clarify how I implemented the ideas for Patrick or
anyone 
>else who was confused by my post. I think it is relevant because a)
there 
>are many long threads in the archive on geometry which are difficult to

>follow (so the points may be hard to uncover.)  and b) I couldn't find
any 
>where someone has committed to this exact mechanism.

You have access to the boost svn sandbox, which has my recent code.  My
library in the vault is fairly out of date.  Below I am registering
legacy point and polygon classes with my geometry library so that I know
their conceptual type for tag dispatching purposes:

  template <>
  struct geometry_concept<CCGCoordPoint> {
    typedef point_concept type;
  };

  template <>
  struct geometry_concept<CPolygonQuery> {
    typedef polygon_concept type;
  };

And here I specify the traits of the legacy point type such that I know
what coordinate type it uses and how to access its data.  I have runtime
accessor instead of compile time because we like to use orientation as
runtime data instead of compile time constant in our code.  Construct is
(Continue reading)

Permalink | Reply |
headers
Brandon Kohn | 9 Oct 21:12
Favicon

Re: Geometry and spatial indexes, my opinion

--------------------------------------------------
From: "Simonson, Lucanus J" <lucanus.j.simonson <at> intel.com>
Sent: Thursday, October 09, 2008 1:00 PM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

> Brandon wrote:
>>I posted this to clarify how I implemented the ideas for Patrick or
> anyone
>>else who was confused by my post. I think it is relevant because a)
> there
>>are many long threads in the archive on geometry which are difficult to
>
>>follow (so the points may be hard to uncover.)  and b) I couldn't find
> any
>>where someone has committed to this exact mechanism.
>
> You have access to the boost svn sandbox, which has my recent code.  My
> library in the vault is fairly out of date.  Below I am registering
> legacy point and polygon classes with my geometry library so that I know
> their conceptual type for tag dispatching purposes:
>
>  template <>
>  struct geometry_concept<CCGCoordPoint> {
>    typedef point_concept type;
>  };
>
>  template <>
>  struct geometry_concept<CPolygonQuery> {
>    typedef polygon_concept type;
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 21:30
Favicon

Re: Geometry and spatial indexes, my opinion

Brandon wrote:
>I agree that this is certainly similar to what I have and that it is
very 
>good. There is however a distinction in that the access traits in my
design 
>are separate from the general point traits. I think that this is an 
>important distinction. When you strip a basic point in N dimensions
from >any 
>nomenclature, you essentially have a data structure that can be
describing >a 
>location in any coordinate frame of dimension N. It is only through
>choosing 
>a coordinate frame that the dimensions of the point takes on meaning
(well, 
>strictly speaking this isn't true... I have a text that speaks quite
highly 
>of coordinate free geometry..). This is why I have created access
traits 
>which are aligned with a particular coordinate frame. It gives me the
means 
>to have a legacy point type (which uses a particular framework, polar 
>coordinates) which can then automatically work in an algorithm which 
>requires Cartesian coordinates. By specializing an access traits type
for 
>the legacy point, I can make all required transformations from r, theta
to 
>x,y without doing any explicit translations to the underlying point
type. 
>The result is that I can put my polar points in and still use all these
(Continue reading)

Permalink | Reply |
headers
Bruno Lalande | 9 Oct 17:41

Re: Geometry and spatial indexes, my opinion

> The library I've written is the only one in the vault which uses this
> mechanism. Your library in the vault directly accesses the interfaces for
> the underlying points, segments and polygons:

But as we said, this version of the library is deprecated by the
incoming one. You'll have a very good idea of the work made in the
meanwhile by browsing the archives, as Luke suggested.

Bruno
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Mathias Gaunard | 9 Oct 18:19

Re: Geometry and spatial indexes, my opinion

Brandon Kohn wrote:
> //! Function to find the cross product between two vectors formed by the 
> specified three points which share an endpoint at A.
> template <typename Point>
> point_traits<Point>::coordinate_type cross_product( const Point& A,
>                                                                             
>       const Point& B,
>                                                                             
>       const Point& C )

Isn't the result of the cross product a vector/point?

> {
>   typedef cartesian_access_traits<Point > access_traits;
>   boost::function_requires<Point2DConcept<Point> >();

Isn't the cross product 3D-only?
Anyway, wouldn't it be better to use SFINAE so that you can overload the 
algorithm to make it work with other concepts?

> When I was talking about access like tuple, I meant using compile time 
> indexing via the access traits. One of the main goals of my library is 
> to facilitate use with legacy geometry code (proprietary in my case) 
> simply by specializing access traits. Using access traits results in 
> little constraint on the interface of the underlying point type.

Are you aware of the Fusion sequence concepts?
Any type can be made into a fusion sequence non-intrusively.

So there is no need to recreate the get<N> machinery.
(Continue reading)

Permalink | Reply |
headers
Brandon Kohn | 9 Oct 18:44
Favicon

Re: Geometry and spatial indexes, my opinion

--------------------------------------------------
From: "Mathias Gaunard" <mathias.gaunard <at> ens-lyon.org>
Sent: Thursday, October 09, 2008 11:19 AM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

> Brandon Kohn wrote:
>> //! Function to find the cross product between two vectors formed by the 
>> specified three points which share an endpoint at A.
>> template <typename Point>
>> point_traits<Point>::coordinate_type cross_product( const Point& A,
>> 
>> const Point& B,
>> 
>> const Point& C )
>
> Isn't the result of the cross product a vector/point?
>
>> {
>>   typedef cartesian_access_traits<Point > access_traits;
>>   boost::function_requires<Point2DConcept<Point> >();
>
> Isn't the cross product 3D-only?

No the cross product is not 3D only. It can be used to calculate the signed 
area of the parallelogram formed by 2D vectors (the length of the vector 
which *is* normal to the 2D plane has this value.) This is how it is used 
here to calculate the orientation using right hand rule convention. This 
particular implementation is just a 2D specialized version. I have another 
version for 3D. Higher dimensions could be written using an indexed access
(Continue reading)

Permalink | Reply |
headers
Johan Råde | 9 Oct 18:49
Favicon

Re: Geometry and spatial indexes, my opinion

> Isn't the cross product 3D-only?

The 3-dimensional cross product can be extended to n-dimensions.
The n-dimensional cross-product takes (n-1) n-vectors as arguments
and returns an n-vector.
If the argument vectors are linearly dependent, then the return vector is 0.
If the argument vectors are linearly independent,
then the return vector is the unique n-vector such that
1. it is perpendicular to all the argument vectors
2. its length is equal the (n-1)-dimensional volume
of the parallellepiped spanned by the argument vectors
3. the argument vectors and the return vector form a positively oriented system.

--Johan

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Patrick Mihelich | 11 Oct 05:55

Re: Geometry and spatial indexes, my opinion

On Thu, Oct 9, 2008 at 7:25 AM, Brandon Kohn <blkohn <at> hotmail.com> wrote:

> Second, there are efficiency and code size concerns. Consider the Euclidean
>> distance function. For 2D/3D points, it is nice to use compile-time
>> indexing
>> and metaprogramming to guarantee tight, loop-less code. For high
>> dimensional
>> points, however, beyond some dimension
>> (BOOST_GEOMETRY_MAX_UNROLL_DIMENSION?) unrolling the loop is no longer
>> desirable, and we would rather just do the runtime iteration. If the
>> points
>> are RuntimeIndexable, we can choose an appropriate distance algorithm at
>> compile time depending on the points' dimensionality.
>>
>>
> I presume the reason one would not want loop-less code at high dimensions
> is due to bloat? I do not understand why runtime looping would be faster in
> this case. It would seem that even in the largest cases the bloat would
> still be small compared to memory sizes today. Runtime indexing can
> certainly be accommodated using a tag dispatch on the access traits. I think
> more research needs to be done to quantify the differences between the two
> to see if it is worth the maintenance overhead.

Sure, I need to back up my claim. The fundamental problem with loop-less
code at high dimensions is bloat, yes. Remember that bloat also affects
efficiency. Suppose we're calculating distances from one point to a set of
other points. If the size of the distance function makes the inner loop code
larger than the L1 instruction cache, we take a performance hit.

I'm attaching a simple benchmark that calculates the distance between two
(Continue reading)

Permalink | Reply |
headers
Brandon Kohn | 11 Oct 15:47
Favicon

Re: Geometry and spatial indexes, my opinion

--------------------------------------------------
From: "Patrick Mihelich" <patrick.mihelich <at> gmail.com>
Sent: Friday, October 10, 2008 10:55 PM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

> On Thu, Oct 9, 2008 at 7:25 AM, Brandon Kohn <blkohn <at> hotmail.com> wrote:
>
>> Second, there are efficiency and code size concerns. Consider the 
>> Euclidean
>>> distance function. For 2D/3D points, it is nice to use compile-time
>>> indexing
>>> and metaprogramming to guarantee tight, loop-less code. For high
>>> dimensional
>>> points, however, beyond some dimension
>>> (BOOST_GEOMETRY_MAX_UNROLL_DIMENSION?) unrolling the loop is no longer
>>> desirable, and we would rather just do the runtime iteration. If the
>>> points
>>> are RuntimeIndexable, we can choose an appropriate distance algorithm at
>>> compile time depending on the points' dimensionality.
>>>
>>>
>> I presume the reason one would not want loop-less code at high dimensions
>> is due to bloat? I do not understand why runtime looping would be faster 
>> in
>> this case. It would seem that even in the largest cases the bloat would
>> still be small compared to memory sizes today. Runtime indexing can
>> certainly be accommodated using a tag dispatch on the access traits. I 
>> think
>> more research needs to be done to quantify the differences between the
(Continue reading)

Permalink | Reply |
headers
Mathias Gaunard | 11 Oct 18:10

Re: Geometry and spatial indexes, my opinion

Brandon Kohn wote:

> If so, how does direct iteration compare with index
> operator accesses? I've noticed in my own tests on measuring std::vector 
> accesses that iteration is significantly faster than operator [ ] when 
> you are iterating over the container (presumably due to bounds checking).

operator[] doesn't do bounds checking, unless you have the debug/secure 
mode of your standard library enabled (which is on by default on MSVC).

While access by index is theoretically slower than pointer increments, 
I'm pretty sure any compiler optimizes the former to the latter.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Michael Marcin | 13 Oct 18:12

Re: Geometry and spatial indexes, my opinion

Mathias Gaunard wrote:
> Brandon Kohn wote:
> 
>> If so, how does direct iteration compare with index
>> operator accesses? I've noticed in my own tests on measuring 
>> std::vector accesses that iteration is significantly faster than 
>> operator [ ] when you are iterating over the container (presumably due 
>> to bounds checking).
> 
> operator[] doesn't do bounds checking, unless you have the debug/secure 
> mode of your standard library enabled (which is on by default on MSVC).
> 
> While access by index is theoretically slower than pointer increments, 
> I'm pretty sure any compiler optimizes the former to the latter.
> 

At least with MSVC9 they aren't exactly equivalent.

http://lists.boost.org/Archives/boost/2008/09/142657.php

--

-- 
Michael Marcin

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Mathias Gaunard | 11 Oct 18:12

Re: Geometry and spatial indexes, my opinion

Patrick Mihelich wrote:
> Let's also add in a
> partially unrolled runtime access version that operates 4 elements at a time
> (ideally the compiler would take care of this).

Isn't GCC supposed to implement loop vectorization?
Did you add in there SIMD instructions or not?

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Joel Falcou | 11 Oct 18:24
Gravatar

Re: Geometry and spatial indexes, my opinion

Mathias Gaunard a écrit :
> Isn't GCC supposed to implement loop vectorization?
> Did you add in there SIMD instructions or not?

"Supposed" is the keyword. gcc 4.4 has a -Ox optimization that tries to 
SIMD code but
when the basic block starts to get too long or too complex, it stops. 
For loop unrolling, it should be
done automagically if loop bounds are statically known, if not, do it 
yourself.

--

-- 
___________________________________________
Joel Falcou - Assistant Professor
PARALL Team - LRI - Universite Paris Sud XI
Tel : (+33)1 69 15 66 35

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Mathias Gaunard | 11 Oct 18:39

Re: Geometry and spatial indexes, my opinion

Joel Falcou wrote:

> For loop unrolling, it should be
> done automagically if loop bounds are statically known, if not, do it 
> yourself.

If the loops are fully unrolled, I don't see the difference between 
"static" and "dynamic" indexing.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Joel Falcou | 11 Oct 18:45
Gravatar

Re: Geometry and spatial indexes, my opinion

Mathias Gaunard a écrit :
> If the loops are fully unrolled, I don't see the difference between 
> "static" and "dynamic" indexing.
>
What I mean is that it seems from experimental results that :
for(int i=0;i<16;++i) // code is more often unrolled than for(int i = 
foo();i<bar();++i) // code

Concerning your remark :
"While access by index is theoretically slower than pointer increments, 
I'm pretty sure any compiler optimizes the former to the latter. "
you're perfectly right.

--

-- 
___________________________________________
Joel Falcou - Assistant Professor
PARALL Team - LRI - Universite Paris Sud XI
Tel : (+33)1 69 15 66 35

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 21:46
Favicon

Re: Geometry and spatial indexes, my opinion

-- Patrick Mihelich wrote:
>On the other hand, I'm worried to see that the geometry::point
>implementation (at least the version included with SpatialIndexes)
supports
>only compile-time indexing. I think we must also have a
RuntimeIndexable
>concept, to which a particular point type may or may not conform.
>RuntimeIndexable would require an indexing operator[], so it can only
be
>modeled by homogeneous points. Iterators via begin() and end() could be
>useful as well. I have a couple of reasons for wanting this, as usual
>motivated by high dimensional spaces...

I personally believe that runtime indexable is preferable to compile
time only.  It is like defining an array that is only allowed to take
compile time constants as indexes.  How useful is that array?  I don't
believe that when a compile time constant is specified as the runtime
index into a point that the compiler will be challenged to inline the
accessor function and convert the index directly to an offset within the
point data type when it is optimizing the code.  I rely heavily on the
compiler to inline and optimize in these cases to eliminate the runtime
overhead of the abstractions I want to create, and the compiler
generally doesn't disappoint me and is improving all the time.

Luke
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Steven Watanabe | 9 Oct 22:05

Re: Geometry and spatial indexes, my opinion

AMDG

Simonson, Lucanus J wrote:
> I personally believe that runtime indexable is preferable to compile
> time only.  It is like defining an array that is only allowed to take
> compile time constants as indexes.  How useful is that array?
>   

Here's my take on the matter:

An algorithm that uses only compile-time indexing is preferable because
it can work with an arbitrary point class more easily.

A point class that supports runtime indexing is preferable because
it works easily with more algorithms.

In Christ,
Steven Watanabe

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 22:37
Favicon

Re: Geometry and spatial indexes, my opinion

Steven Watanabe wrote:
>An algorithm that uses only compile-time indexing is preferable because
>it can work with an arbitrary point class more easily.

>A point class that supports runtime indexing is preferable because
>it works easily with more algorithms.

Most legacy point types don't provide runtime indexing, but that isn't
much of an obstacle to providing runtime indexing accessors to them.

template <>
coord get(point& p, int i) {
	if(i == 0) return p.x();
	return p.y();
}

On the other hand, algorithms that don't take runtime parameters have to
be instantiated for all possible values.  As the number of the
dimensions in the systems goes up it becomes less reasonable to
enumerate dimensions and more likely that the data types are runtime
indexable.

if(i == 0) {
	do_something_algorithmic<0>(point);
} else {
	do_something_algorithmic<1>(point);
}

Even in two dimensions where it is just a matter of where you push the
wrinkle in the carpet, the key difference is that the former goes in one
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 01:32
Favicon

Re: Geometry and spatial indexes, my opinion

Michael Fawcett wrote:
>As for the heterogeneous types, think of huge (GBs worth) digital
>elevation models in meter units where altitude is in a range from 0 -
>20,000m.  In that case, my point type would be something like
>vector3<int, short, int> instead of a vector3<int>.

Phil Endecott wrote:
>In GPS data, I store altitude to the nearest metre in an int16_t, and 
>altitude and longitude in degrees in 32-bit fixed-point types.  
>Although longitude needs one more bit than latitude I tend to use the 
>same type for both, so my 2d algorithms are homogeneous.  But anything 
>that also involves altitude needs to be heterogeneous.

In VLSI layout we sometimes represent the layer as the z axis of a 3D
coordinate system.  Because there are only tens of layers we can use
something smaller than int to store it.  However, the compiler will
often pad it back to word aligned addressing and insert padding bytes
into a data structure, reducing the memory savings.  Also, internally,
all arithmetic is 32 bit or greater, so there is no advantage in using
smaller data types for local operations.  I think it is perfectly
reasonable to allow point classes to have heterogeneous coordinate
types, but require them to cast to and from a homogeneous coordinate
type at the interface between that object and the geometry library.  In
all three examples, we would make the coordinate type of the interface
between the point and the library int and allow the 16 bit value to cast
up to 32 bits when it is read into an algorithm and back down to 16 bits
when it is written out.

Luke
_______________________________________________
(Continue reading)

Permalink | Reply |
headers
Michael Fawcett | 9 Oct 04:29

Re: Geometry and spatial indexes, my opinion

On Wed, Oct 8, 2008 at 7:32 PM, Simonson, Lucanus J
<lucanus.j.simonson <at> intel.com> wrote:
> Michael Fawcett wrote:
>>As for the heterogeneous types, think of huge (GBs worth) digital
>>elevation models in meter units where altitude is in a range from 0 -
>>20,000m.  In that case, my point type would be something like
>>vector3<int, short, int> instead of a vector3<int>.
>
> Phil Endecott wrote:
>>In GPS data, I store altitude to the nearest metre in an int16_t, and
>>altitude and longitude in degrees in 32-bit fixed-point types.
>>Although longitude needs one more bit than latitude I tend to use the
>>same type for both, so my 2d algorithms are homogeneous.  But anything
>>that also involves altitude needs to be heterogeneous.
>
> In VLSI layout we sometimes represent the layer as the z axis of a 3D
> coordinate system.  Because there are only tens of layers we can use
> something smaller than int to store it.  However, the compiler will
> often pad it back to word aligned addressing and insert padding bytes
> into a data structure, reducing the memory savings.  Also, internally,
> all arithmetic is 32 bit or greater, so there is no advantage in using
> smaller data types for local operations.  I think it is perfectly
> reasonable to allow point classes to have heterogeneous coordinate
> types, but require them to cast to and from a homogeneous coordinate
> type at the interface between that object and the geometry library.  In
> all three examples, we would make the coordinate type of the interface
> between the point and the library int and allow the 16 bit value to cast
> up to 32 bits when it is read into an algorithm and back down to 16 bits
> when it is written out.
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 20:06
Favicon

Re: Geometry and spatial indexes, my opinion

>> In VLSI layout we sometimes represent the layer as the z axis of a 3D
>> coordinate system.  Because there are only tens of layers we can use
>> something smaller than int to store it.  However, the compiler will
>> often pad it back to word aligned addressing and insert padding bytes
>> into a data structure, reducing the memory savings.  Also,
internally,
>> all arithmetic is 32 bit or greater, so there is no advantage in
using
>> smaller data types for local operations.  I think it is perfectly
>> reasonable to allow point classes to have heterogeneous coordinate
>> types, but require them to cast to and from a homogeneous coordinate
>> type at the interface between that object and the geometry library.
In
>> all three examples, we would make the coordinate type of the
interface
>> between the point and the library int and allow the 16 bit value to
cast
>> up to 32 bits when it is read into an algorithm and back down to 16
bits
>> when it is written out.

--Michael Fawcett wrote:
>I don't understand why the interface or algorithm cares whether it's
>homogeneous or heterogeneous.

The interface or the algorithm must necessarily be much more complex to
accommodate heterogeneous coordinates.  Moreover, you have a real
problem with casting when you do arithmetic between heterogeneous
coordinates in an algorithm.
(Continue reading)

Permalink | Reply |
headers
Michael Fawcett | 9 Oct 20:25

Re: Geometry and spatial indexes, my opinion

On Thu, Oct 9, 2008 at 2:06 PM, Simonson, Lucanus J
<lucanus.j.simonson <at> intel.com> wrote:
>>> In VLSI layout we sometimes represent the layer as the z axis of a 3D
>>> coordinate system.  Because there are only tens of layers we can use
>>> something smaller than int to store it.  However, the compiler will
>>> often pad it back to word aligned addressing and insert padding bytes
>>> into a data structure, reducing the memory savings.  Also,
> internally,
>>> all arithmetic is 32 bit or greater, so there is no advantage in
> using
>>> smaller data types for local operations.  I think it is perfectly
>>> reasonable to allow point classes to have heterogeneous coordinate
>>> types, but require them to cast to and from a homogeneous coordinate
>>> type at the interface between that object and the geometry library.
> In
>>> all three examples, we would make the coordinate type of the
> interface
>>> between the point and the library int and allow the 16 bit value to
> cast
>>> up to 32 bits when it is read into an algorithm and back down to 16
> bits
>>> when it is written out.
>
> --Michael Fawcett wrote:
>>I don't understand why the interface or algorithm cares whether it's
>>homogeneous or heterogeneous.
>
> The interface or the algorithm must necessarily be much more complex to
> accommodate heterogeneous coordinates.  Moreover, you have a real
> problem with casting when you do arithmetic between heterogeneous
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 21:36
Favicon

Re: Geometry and spatial indexes, my opinion

--Michael Fawcett
>Boost.Typeof.  Boost.Units also handles this gracefully, but I'm not
>sure how they ended up solving it.  Regardless, this is not something
>the end-user cares how it works, just that it works.  It's doable by
>the library writer, so should be done.
...
>This type of conversion is handled automatically by the compiler in
>much simpler expressions:

First off, relying on auto casting is a great way to write template code
that only works when the template parameters are built-in types and
doesn't even compile when user defined data types are used instead.
Moreover, compiler always auto-casts built-in to user defined regardless
of what your intention, and believe me, the user does care.  The
compiler doesn't always do the right thing by default.

The rationale that something is possible, therefore it should be done is
no rationale at all.  Heterogeneous coordinates in the interfaces and
internals of algorithms is incompatible with runtime accessors to
coordinates and high order constructs.  I don't see any value in
carrying the individual coordinate data types through the interface into
the algorithms.  Why not cast them up front in the user-provided
accessor functions and let the user who knows and cares what casting
they want to get control that.  Having one coordinate data type within
the algorithms *does* make the implementation of those algorithms
simpler and simpler is usually something worth pursuing.

Luke
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
(Continue reading)

Permalink | Reply |
headers
Brandon Kohn | 9 Oct 21:45
Favicon

Re: Geometry and spatial indexes, my opinion


--------------------------------------------------
From: "Simonson, Lucanus J" <lucanus.j.simonson <at> intel.com>
Sent: Thursday, October 09, 2008 2:36 PM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

> --Michael Fawcett
>>Boost.Typeof.  Boost.Units also handles this gracefully, but I'm not
>>sure how they ended up solving it.  Regardless, this is not something
>>the end-user cares how it works, just that it works.  It's doable by
>>the library writer, so should be done.
> ...
>>This type of conversion is handled automatically by the compiler in
>>much simpler expressions:
>
> First off, relying on auto casting is a great way to write template code
> that only works when the template parameters are built-in types and
> doesn't even compile when user defined data types are used instead.
> Moreover, compiler always auto-casts built-in to user defined regardless
> of what your intention, and believe me, the user does care.  The
> compiler doesn't always do the right thing by default.
>
> The rationale that something is possible, therefore it should be done is
> no rationale at all.  Heterogeneous coordinates in the interfaces and
> internals of algorithms is incompatible with runtime accessors to
> coordinates and high order constructs.  I don't see any value in
> carrying the individual coordinate data types through the interface into
> the algorithms.  Why not cast them up front in the user-provided
> accessor functions and let the user who knows and cares what casting
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 21:59
Favicon

Re: Geometry and spatial indexes, my opinion

Brandon wrote:
>As for the general 
>case, there is already enough on the plate to have algorithms which
support 
>both floating point and integral coordinate types :).

That's for darn sure.  That is the one thing about your library that
really intrigues me.  I'm pretty much integer only, Barend is pretty
much floating point exclusively.  Joel suggested early on that generic
programming could resolve the issue easily, but you are the first person
to take that issue on.  How do you do it?

Luke
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Brandon Kohn | 9 Oct 22:51
Favicon

Re: Geometry and spatial indexes, my opinion

--------------------------------------------------
From: "Simonson, Lucanus J" <lucanus.j.simonson <at> intel.com>
Sent: Thursday, October 09, 2008 2:59 PM
To: <boost <at> lists.boost.org>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

> Brandon wrote:
>>As for the general
>>case, there is already enough on the plate to have algorithms which
> support
>>both floating point and integral coordinate types :).
>
> That's for darn sure.  That is the one thing about your library that
> really intrigues me.  I'm pretty much integer only, Barend is pretty
> much floating point exclusively.  Joel suggested early on that generic
> programming could resolve the issue easily, but you are the first person
> to take that issue on.  How do you do it?
>
> Luke

Well, the jury is still out as to how effective the *real* solution will be. 
I start by adding the ability to perform type dispatch based on the number 
type of the coordinate. I manage that by again using a traits class (for the 
coordinates):

//! Default point traits struct.
//! NOTE: must be specialized for user types.
template <typename Coordinate>
struct coordinate_traits
{
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 23:33
Favicon

Re: Geometry and spatial indexes, my opinion

Brandon wrote:
>Well, the jury is still out as to how effective the *real* solution
will >be. 
>I start by adding the ability to perform type dispatch based on the
number 
>type of the coordinate. I manage that by again using a traits class
(for >the 
>coordinates):

Interesting, I have coordinate_traits and register the coordinate type
for tag dispatching purposes.  My coordinate traits register related
data types such as area data type.  For 32 bit integer coordinates I use
a 64 bit integer to compute and return area values, and I register it
through the 32 bit integer coordinate traits.

>Then I can do a dispatch on the traits. The only issue I've tackled so
far 
>is for comparing segments on a sweepline. I did this by using 
>boost::rational ( so overflow may still be a problem in some cases ). 

I use mpq_class because some cases is way to many cases for me.  I
compute the y as a mpq_class at a given x, which allows me exact,
overflow proof comparison, but I don't store the mpq_class value in the
sweepline data structure.  I compute it on the fly as needed.

>The 
>other issue I have yet to tackle is intersection between two segments
for 
>integers. I have an implementation that uses O'Rourke's method from 
>Computational Geometry in C. In his method the segments are first
(Continue reading)

Permalink | Reply |
headers
Michael Fawcett | 9 Oct 21:47

Re: Geometry and spatial indexes, my opinion

On Thu, Oct 9, 2008 at 3:36 PM, Simonson, Lucanus J
<lucanus.j.simonson <at> intel.com> wrote:
> --Michael Fawcett
>>Boost.Typeof.  Boost.Units also handles this gracefully, but I'm not
>>sure how they ended up solving it.  Regardless, this is not something
>>the end-user cares how it works, just that it works.  It's doable by
>>the library writer, so should be done.
> ...
>>This type of conversion is handled automatically by the compiler in
>>much simpler expressions:
>
> First off, relying on auto casting is a great way to write template code
> that only works when the template parameters are built-in types and
> doesn't even compile when user defined data types are used instead.
> Moreover, compiler always auto-casts built-in to user defined regardless
> of what your intention, and believe me, the user does care.  The
> compiler doesn't always do the right thing by default.

No, it doesn't only work with built-in types.  It works with any type
that has the correct operators defined.  If the user does care, he can
cast obviously.  The algorithm shouldn't do the casting or require it
though.

> The rationale that something is possible, therefore it should be done is
> no rationale at all.

This is a gross misrepresentation of what I said.  I said the end-user
cares, *and* it's doable, so it should be done.  You only took half of
what I said.
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 22:17
Favicon

Re: Geometry and spatial indexes, my opinion

>> The rationale that something is possible, therefore it should be done
is
>> no rationale at all.

--Michael Fawcett wrote:
>This is a gross misrepresentation of what I said.  I said the end-user
>cares, *and* it's doable, so it should be done.  You only took half of
>what I said.

You are right, I apologize.

>> Heterogeneous coordinates in the interfaces and
>> internals of algorithms is incompatible with runtime accessors to
>> coordinates and high order constructs.

>Algorithms that need runtime indexing should require that concept.

All of my algorithms use runtime indexing, so that might slant my point
of view slightly here.

>> I don't see any value in
>> carrying the individual coordinate data types through the interface
into
>> the algorithms.

>They're already present at compile-time.  No extra work required.

Well, yes and no.  If I want to have a

template <int axis>
(Continue reading)

Permalink | Reply |
headers
Steven Watanabe | 9 Oct 22:38

Re: Geometry and spatial indexes, my opinion

AMDG

Simonson, Lucanus J wrote:
> You will have to cast at some point to use the value, why is it more
> expensive to cast up front rather than at the last possible moment.
>   

This only applies to built in types.  For user defined types, it may not 
be necessary to
cast in order to operate on objects of two different types.

> Assuming the value is going to be used more than once by the algorithm
> it will be cast more than once.  Better to factor that to the front.  A
> smart compiler would actually do that for you.

That's fine for built in types.  What about user-defined types?

>   Futhermore, there has to
> be a teomporary at the interface because as I've just discussed with
> Brandon, there is the clear need to make things like polar points
> conform to Cartesian interfaces, which is incompatible with direct
> access to the data members.  Since we already have to make a temporary
> we should cast at that point instead of having yet another temoporary
> and cast later on.
>   

Maybe I'm misunderstanding something, but it seems to me that an 
algorithm that works
with Cartesian coordinates will tend to be very inefficient if it has to 
convert
(Continue reading)

Permalink | Reply |
headers
Barend Gehrels | 9 Oct 22:47
Favicon

Re: Geometry and spatial indexes, my opinion

Steven Watanabe wrote:
> Simonson, Lucanus J wrote:
>
>>  Futhermore, there has to
>> be a teomporary at the interface because as I've just discussed with
>> Brandon, there is the clear need to make things like polar points
>> conform to Cartesian interfaces, which is incompatible with direct
>> access to the data members.  Since we already have to make a temporary
>> we should cast at that point instead of having yet another temoporary
>> and cast later on.
>>   
>
> Maybe I'm misunderstanding something, but it seems to me that an 
> algorithm that works
> with Cartesian coordinates will tend to be very inefficient if it has 
> to convert
> to and from polar coordinates on the fly at every access.
I agree, that is too inefficient. And it is not necessary.

We (Bruno and I) are now about to publish the new preview 3 of the 
"geometry library" of which preview 2 was last March.

But for now, in short. There is a point concept. The algorithms can take 
any point type which fulfils the point concept. Per point type a 
strategy can be registered using a traits class. That strategy will do 
the primitive calculations, such as distance from point to point, or 
distance from point to segment.

An algorithm (e.g. simplify) will use the registered strategy and will 
do no casts or  conversions, will calculate distances where necessary
(Continue reading)

Permalink | Reply |
headers
Matthias Schabel | 9 Oct 22:53

Re: Geometry and spatial indexes, my opinion

>> be a teomporary at the interface because as I've just discussed with
>> Brandon, there is the clear need to make things like polar points
>> conform to Cartesian interfaces, which is incompatible with direct
>> access to the data members.  Since we already have to make a  
>> temporary
>> we should cast at that point instead of having yet another temoporary
>> and cast later on.
>>
>
> Maybe I'm misunderstanding something, but it seems to me that an  
> algorithm that works
> with Cartesian coordinates will tend to be very inefficient if it  
> has to convert
> to and from polar coordinates on the fly at every access.

Just to further this point : if we want to do geometry in spherical  
coordinates, then the
point type cannot be homogeneous, especially if we wanted, e.g., to  
enforce dimensional
correctness a la Boost.Units :

cartesianPoint<si::length,si::length,si::length>

vs.

sphericalPoint<si::length,si::radians,si::radians>

I understand that for most of the applications that people are  
considering, cartesian
coordinates are dominant, but I can easily imagine a really cool game
(Continue reading)

Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 23:11
Favicon

Re: Geometry and spatial indexes, my opinion

Matthias wrote:
>Just to further this point : if we want to do geometry in spherical  
>coordinates, then the
>point type cannot be homogeneous, especially if we wanted, e.g., to  
>enforce dimensional
>correctness a la Boost.Units :
>
>cartesianPoint<si::length,si::length,si::length>
>
>vs.
>
>sphericalPoint<si::length,si::radians,si::radians>

You are right, obviously for a spherical coordinate or polar coordinate
concept we would use different types.  That is one reason why Cartesian
point would be a different concept and use different accessors than
polar or spherical point.  There is no need to have one point concept
and set of traits that applies to all 2D, 3D and ND coordinate systems.

Luke
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Simonson, Lucanus J | 9 Oct 23:03
Favicon

Re: Geometry and spatial indexes, my opinion

Simonson, Lucanus J wrote:
>> You will have to cast at some point to use the value, why is it more
>> expensive to cast up front rather than at the last possible moment.

Steven Watanabe
>This only applies to built in types.  For user defined types, it may
not 
>be necessary to
>cast in order to operate on objects of two different types.
...
>Maybe I'm misunderstanding something, but it seems to me that an 
>algorithm that works
>with Cartesian coordinates will tend to be very inefficient if it has
to 
>convert
>to and from polar coordinates on the fly at every access.

User defined mixed type arithmetic operators seems like a fairly
unlikely circumstance.  I'm not sure introducing complexity of keeping
track of the different data types into the algorithms is warranted by
such a use case.

The interface is more likely to be used between modules rather than
internally.  For instance, imagine one legacy module operates on and
produces its output in the form of polar coordinate points.  A generic
geometry library module consumes Cartesian coordinate points.  Rather
than iterate over polar points and convert them to Cartesian points that
are fed into the generic library they can be converted on the fly
through the generic interface.  Rather than use the user point type for
internal computation I use my own point type because I know it is fast.
(Continue reading)

Permalink | Reply |
headers
Michael Fawcett | 10 Oct 23:09

Re: Geometry and spatial indexes, my opinion

On Thu, Oct 9, 2008 at 4:17 PM, Simonson, Lucanus J
<lucanus.j.simonson <at> intel.com> wrote:
>
>>> I don't see any value in
>>> carrying the individual coordinate data types through the interface
> into
>>> the algorithms.
>
>>They're already present at compile-time.  No extra work required.
>
> Well, yes and no.  If I want to have a
>
> template <int axis>
> coordinate_type get(const point_type& point);
>
> accessor function I need to go through a lot of work to rewrite it as
>
> template <int axis>
> typename coordinate_type<axis>::type get(const point_type& point);
>
> and the user needs to go through more work to provide both
>
> template<int axis>
> struct coordinate_type<axis> { typedef int type; }
>
> and
>
> struct general_coordinate_type { typedef int type; }
>
> and will generally be puzzled about why the geometry library is so
(Continue reading)

Permalink | Reply |
headers
Bruno Lalande | 8 Oct 23:55

Re: Geometry and spatial indexes, my opinion

Hello,

>> Ok, I take your point. I wasn't suggesting that a library not be able to
>> handle more than 3 dimensions. Rather I would suggest that the population of
>> developers who have such requirements must be very small. Considering that
>> generalization on dimension is not trivial for many algorithms, this leads
>> me to the conclusion that the specific algorithms will decide the
>> requirements on their inputs. This is why I chose a traits based interface
>> for the geometry library I've been implementing. There's nothing to stop one
>> from creating a multi-dimensional Cartesian/polar/parametric access traits
>> interface for any algorithm which requires it. So I suppose I agree, the
>> geometry library should not constrain on the number of dimensions. But I
>> don't agree with full agnosticism (to mean agnosticism of coordinate frame
>> as well.) There should be a way to differentiate points further to align
>> with the concrete traits of the dimension they describe.
>
>
> This sounds reasonable. Certainly there are many 2D/3D algorithms for which
> there is little point in generalizing to higher dimensions.

But it's not a reason to limit the point concept to 2D/3D. Once you
have your points defined dimension-agnosticly (which was really not a
big deal compared to some other problems we had when defining our
points...), nothing prevents you from writing an algorithm that will
only work with a precise dimension because it doesn't make sense for
the other ones. Let's take the cross product. Every 3D programmer use
it, and it has a sense only in 3D even if it can be generalized with
wedge product. Well your cross_product() function will just have to do
a BOOST_STATIC_ASSERT to ensure your passing it a 3D point, and will
let the rest of the algorithms be dimension agnostic.
(Continue reading)

Permalink | Reply |
headers
Phil Endecott | 8 Oct 23:58

Re: Geometry and spatial indexes, my opinion

Patrick Mihelich wrote:
> I can't offhand think of a use case where the dimensions
> are of heterogeneous type

In GPS data, I store altitude to the nearest metre in an int16_t, and 
altitude and longitude in degrees in 32-bit fixed-point types.  
Although longitude needs one more bit than latitude I tend to use the 
same type for both, so my 2d algorithms are homogeneous.  But anything 
that also involves altitude needs to be heterogeneous.

Phil.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Jonathan Franklin | 8 Oct 17:17

Re: Geometry and spatial indexes, my opinion

On Wed, Oct 8, 2008 at 2:37 AM, Patrick Mihelich <patrick.mihelich <at> gmail.com
> wrote:

> In my opinion, a Boost geometry library must have at least basic support
> for
> n-dimensional computational geometry. Let's start with able to handle
> points
> of arbitrary dimension and calculate distances between them (given some
> metric). This is easy to do and already sufficient to implement many useful
> spatial indices. I have not looked at Barend's geometry library in detail,
> but on the surface it looks generic enough to support this.

I very much need this for the generic DM/KDD algorithms that I am working
on.  We started work on a clustering algorithms library at boostcon this
year, and support for n-dimensional spatial indexes/queries is still needed
to improve the performance of some of the algorithms.

WRT the clustering library, I dropped the ball over the summer when things
heated up at work and school, but will be picking it up again Real Soon
Now.  If you have any interest in clustering or classification algorithms,
then please contact me! </shameless_plug>.

Jon
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Patrick Mihelich | 9 Oct 00:17

Re: Geometry and spatial indexes, my opinion

On Wed, Oct 8, 2008 at 8:17 AM, Jonathan Franklin <
franklin.jonathan <at> gmail.com> wrote:

> I very much need this for the generic DM/KDD algorithms that I am working
> on.  We started work on a clustering algorithms library at boostcon this
> year, and support for n-dimensional spatial indexes/queries is still needed
> to improve the performance of some of the algorithms.
>
> WRT the clustering library, I dropped the ball over the summer when things
> heated up at work and school, but will be picking it up again Real Soon
> Now.  If you have any interest in clustering or classification algorithms,
> then please contact me! </shameless_plug>.

This is very interesting, and relevant to my current work. I would love to
see a nice generic clustering library in Boost. I can't promise much help at
this point (I also have a project I've been meaning to pick up again Real
Soon Now :-) but let me know when you start working on it again.

Clustering and spatial indexes have some close connections - as you say,
spatial indexes can be used to improve the performance of some clustering
algorithms. Likewise, clustering is sometimes used to construct spatial
indexes (agglomerative clustering, hierarchical k-means). So, it would be
nice for the libraries to play nicely with each other... but more important
to get the core functionality in place first, of course.

Cheers,
Patrick
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
(Continue reading)

Permalink | Reply |
headers
Jonathan Franklin | 9 Oct 01:36

Re: Geometry and spatial indexes, my opinion

On Wed, Oct 8, 2008 at 4:17 PM, Patrick Mihelich <patrick.mihelich <at> gmail.com
> wrote:

> I would love to
> see a nice generic clustering library in Boost. I can't promise much help
> at
> this point (I also have a project I've been meaning to pick up again Real
> Soon Now :-) but let me know when you start working on it again.

I will.

> Clustering and spatial indexes have some close connections - as you say,
> spatial indexes can be used to improve the performance of some clustering
> algorithms. Likewise, clustering is sometimes used to construct spatial
> indexes (agglomerative clustering, hierarchical k-means). So, it would be
> nice for the libraries to play nicely with each other... but more important
> to get the core functionality in place first, of course.

I agree, on all counts.  I'm also looking at it as a starting point for
other DM/KDD algorithms.  I'd love to build a generic SVM implementation,
and there are plenty of others.

Jon
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Stjepan Rajko | 9 Oct 03:57
Favicon

Re: Geometry and spatial indexes, my opinion

On Wed, Oct 8, 2008 at 4:36 PM, Jonathan Franklin
<franklin.jonathan <at> gmail.com> wrote:
> other DM/KDD algorithms.  I'd love to build a generic SVM implementation,
> and there are plenty of others.
>

The kernel-machine library has some genericity, uses boost and implements SVM:
http://www.terborg.net/research/kml/

I've only used it briefly and a long time ago, but I remember liking
it (it was actually what introduced me to boost).  Might be worth
looking at if you're thinking of implementing your own.

Kind regards,

Stjepan
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Permalink | Reply |
headers
Brandon Kohn | 8 Oct 01:36
Favicon

Re: Geometry and spatial indexes, my opinion

--------------------------------------------------
From: "Mathias Gaunard" <mathias.gaunard <at> ens-lyon.org>
Sent: Tuesday, October 07, 2008 5:52 PM
To: <boost <at> lists.boost.org>
Subject: [boost] Geometry and spatial indexes, my opinion

> Hi,
>
> Wanting to code a simple 3D virtual world, I looked into the recent 
> spatial indexes SOC work, which depends on the proposed geometry library.
>
> I have to admit I was fairly disappointed.
> So I'm going to put some critics, some quite harsh maybe, along with some 
> ramblings about what I would have liked to have.
> Note that I am no geometry or space indexing expert, so what I say may be 
> perfectly silly.
>
> For starters, I think those libraries should be dimension agnostic and 
> generic. Geometry not only has a strong 2D bias, but the documentation 
> also says geometry::box only works with point_xy (and point_ll).
> Since it is used everywhere in spatial index, that means it's unusable on 
> 3D.
>

Hi Mathias,

I just wanted to say something here about dimensional agnosticism. I don't 
think this is necessarily the way to go. There are a couple of reasons that 
I say this. The more trivial point is that higher than 3D geometry isn't 
likely to be supported and isn't of much practical use anyway. The second
(Continue reading)

Permalink | Reply |
headers
Barend Gehrels | 8 Oct 10:13
Favicon

Re: Geometry and spatial indexes, my opinion

Hi Mathias,

Thanks for your interest in the geometry / spatial index library.

There were also some other postings about this library last week, but to 
be clear. The preview (on which the spatial index was built) was posted 
in March this year. There were many discussions about this preview, 
among others about dimension agnosticity and concepts. Bruno Lalande 
joined me. We agree with those critics and have reworked the library, 
which indeed took a while, but which will now appear very soon on this 
list. It is dimension agnostic and uses concepts.

> For starters, I think those libraries should be dimension agnostic and 
> generic. Geometry not only has a strong 2D bias, but the documentation 
> also says geometry::box only works with point_xy (and point_ll). Since 
> it is used everywhere in spatial index, that means it's unusable on 3D.

The box in the library was just a small helper class. It is indeed more 
important in the spatial index library and should be generic, indeed. 
However, the restriction for just xy / ll points is gone, it can take 3d 
points now, for example. Points (point concepts) are now dimension 
agnostic and generic in our library.

I will not go into the details of your comments on the spatial index 
library, but keep in mind that it was a GSoC exercise and that the 
author, who did a great job, noted with his final report:
(paste of his email):
> The code is still beta (or maybe alpha) and not recommended for
> production use because it is still not tested enough, but if you want
> to check the actual status you can find it in the following location...
(Continue reading)

Permalink | Reply |
headers
"Federico J. =?iso-8859-1?q?Fern=E1ndez=22?= | 8 Oct 19:54

Re: Geometry and spatial indexes, my opinion

>
> Wanting to code a simple 3D virtual world, I looked into the recent spatial
> indexes SOC work, which depends on the proposed geometry library.
>
> I have to admit I was fairly disappointed.
> So I'm going to put some critics, some quite harsh maybe, along with some
> ramblings about what I would have liked to have.
> Note that I am no geometry or space indexing expert, so what I say may be
> perfectly silly.
>

[...]

Mathias,

Thanks for your interest in the SpatialIndex GSoC project.

I agree about that the indexes lack a lot of features and they're very
limited (for example, they are only for 2D now).

But remember that this is the work that we have done in a bit more than two
months from the ground up (this time include reading the papers about the
indexes, writing little documentation, writing unit tests, finding data to
test, integrate with the geometry proposal, etc), so it's still has a long
road to be usable (as I say in my email).

Some remarks:

- You are able to find all elements within a certain range, if you mean by
range a box. Or you can use a box and then refine the result filtering out
(Continue reading)

Permalink | Reply |
headers
Mathias Gaunard | 9 Oct 03:53

Re: Geometry and spatial indexes, my opinion

Federico J. Fernández wrote:

> - You are able to find all elements within a certain range, if you mean by
> range a box. Or you can use a box and then refine the result filtering out
> the elements that are not in your area.

I meant it in a more abstract way. Usually a range is defined by a 
circle (rather than a box), but it could also be an area defined 
arbitrarily, so why not make it work with any geometrical object, using 
geometry::intersect and geometry::within in place of your overlap function?
Maybe it would be more practical if geometry provided an overlap 
(not-completely-within) test function. Maybe having a search where you 
search for elements that are completely within an area is interesting 
too? In that case you might as well parameterize the criteria.

> - About "Being able to index arbitrary objects and not just points". You can
> insert the envelopes of arbitrary geometries and a pointer to the real
> object as the data. Maybe it's not the best interface to do this, but a lot
> of libraries (i.e. GEOS) use this approach.

Which I can only do with R-trees and not Quadtrees, if I understand 
correctly.
It will still lead to approximations when computing distances and the 
like though, the actual object may be more far away than its minimal 
axis-aligned bounding box and thus the nearest neighbor search might 
return wrong results.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
(Continue reading)

Permalink | Reply |
headers
"Federico J. =?iso-8859-1?q?Fern=E1ndez=22?= | 9 Oct 14:07

Re: Geometry and spatial indexes, my opinion

>
> - You are able to find all elements within a certain range, if you mean by
>> range a box. Or you can use a box and then refine the result filtering out
>> the elements that are not in your area.
>>
>
> I meant it in a more abstract way. Usually a range is defined by a circle
> (rather than a box), but it could also be an area defined arbitrarily, so
> why not make it work with any geometrical object, using geometry::intersect
> and geometry::within in place of your overlap function?
> Maybe it would be more practical if geometry provided an overlap
> (not-completely-within) test function. Maybe having a search where you
> search for elements that are completely within an area is interesting too?
> In that case you might as well parameterize the criteria.

I understand. That's the plan, but it's not yet ready, I just wanted to
point out that there is some basic functionality about this.

insert the envelopes of arbitrary geometries and a pointer to the real
>> object as the data. Maybe it's not the best interface to do this, but a
>> lot
>> of libraries (i.e. GEOS) use this approach.
>>
> - About "Being able to index arbitrary objects and not just points". You
> can
>
> Which I can only do with R-trees and not Quadtrees, if I understand
> correctly.

Yes.
(Continue reading)

Permalink | Reply |
headers
Phil Endecott | 10 Oct 01:30

Re: Geometry and spatial indexes, my opinion

Mathias Gaunard wrote:
> Wanting to code a simple 3D virtual world, I looked into the recent 
> spatial indexes SOC work, which depends on the proposed geometry library.

Your message has prompted me to finally have a look at Federico's 
spatial index work.

> I don't really get what boost::spatial_index::spatial_index is for. It 
> does nothing but forward everything to the last template parameter.
>
> Instead of writing
> boost::spatial_index::spatial_index<
>      point_type, value_type,
>      boost::spatial_index::rtree<point_type, value_type>
>  > index(args...);
>
> I might as well write
> boost::spatial_index::rtree<point_type, value_type> index(args...);
>
> Also, I think the spatial indexes do not provide enough operations. The 
> only things they allow is putting point => value pairs, retrieving the 
> value associated to a point in O(log n) time (I assume, complexity is 
> not documented), and finding all values within a certain box (in O(log 
> n) too?).
> Many things one typically wants to do with spatial indexes are not possible:
> - Iterate all (points, value) pairs in the index
> - Find the element closest (or k-closest) to some point in space or 
> other element.
> - Find all elements within a certain range of some point in space or 
> other element
(Continue reading)

Permalink | Reply |

Gmane