Hashing / mapping Point locations to material ID

[Corbin Foucart]

Hello all,

I'm attempting to set material ID based on x-location. I'd like to create  std::unordered_map between x-locations of cell centers and material id, and then refer to that map to quickly set material_id later.

The compiler is rightly complaining that there isn't a hash method for the Point object, and it seems like this could indeed be dangerous, because of floating point comparison later between Point objects during lookup.

However, this must be a commonly done sort of thing... what's the best way to map a known set of Point objects to other data?

Best,

Corbin

[Wolfgang Bangerth]

On 2/6/21 1:55 PM, Corbin Foucart wrote:
>
> The compiler is rightly complaining that there isn't a hash method for the
> Point object, and it seems like this could indeed be dangerous, because of
> floating point comparison later between Point objects during lookup.

Just add such a hash function for Point. It's true that two nearby points will
have different hash values, but that shouldn't stop you from using hashes if
you query the same points over and over.

That said, I would suggest to do the indexing not on geometric locations but
the logic position of a cell. You can either do that with a cell iterator
itself, or if you want to make it work in a parallel context, the CellId of a
cell.

Best
W.


--
------------------------------------------------------------------------
Wolfgang Bangerth email: bang...@colostate.edu
www: http://www.math.colostate.edu/~bangerth/

[Corbin Foucart]

Thank you for the fast and clear answer, Wolfgang.

Just add such a hash function for Point. It's true that two nearby points will
have different hash values, but that shouldn't stop you from using hashes if
you query the same points over and over.

This is definitely doable. 

 

That said, I would suggest to do the indexing not on geometric locations but
the logic position of a cell. You can either do that with a cell iterator
itself, or if you want to make it work in a parallel context, the CellId of a
cell.

I'm curious about this; if the material ID physically represents a location-based quantity (e.g., which vertical column of fluid as specified by a surface mesh), how come you recommend using the iteration order to specify it? Unless I'm misunderstanding what you mean by logic position of the cell w/r/t a cell iterator...

Best,

Corbin 

[Jean-Paul Pelteret]

Hi Corbin,

Just add such a hash function for Point.

In case you haven't yet done this, I've dug out an old snippet of code that implements a reliable hash function for the point class. I used this approach successfully when implementing some exotic constraints manager, so hopefully it would suit your purposes too.

template<int spacedim>

struct PointHashFunc

{

std::size_t

operator()(const dealii::Point<spacedim>&p) const

{

std::size_t h;

h = std::hash<double>()(p[0]);

if (spacedim > 1)

{

std::size_t h2 = std::hash<double>()(p[1]);

h = h ^ (h2 << 1);

}

if (spacedim > 2)

{

size_t h3 = std::hash<double>()(p[2]);

h = h ^ h3;

}

if (spacedim > 3)

{

AssertThrow(false, ExcNotImplemented());

}

return h;

}

}; // struct PointHashFunc

template<int spacedim, typename T>

using PointMap =

std::unordered_map<dealii::Point<spacedim>, T, PointHashFunc<spacedim> >;

Best,
Jean-Paul

[Wolfgang Bangerth]

On 2/6/21 2:30 PM, Corbin Foucart wrote:
> Thank you for the fast and clear answer, Wolfgang.
>
> Just add such a hash function for Point. It's true that two nearby points
> will
> have different hash values, but that shouldn't stop you from using hashes if
> you query the same points over and over.
>
> This is definitely doable.

We would love to see the corresponding patch to deal.II then :-)

The C++ standard is (maybe oddly) written in a way that suggests that one
should specialize std::hash. Take a look at
https://en.cppreference.com/w/cpp/utility/hash

> I'm curious about this; if the material ID physically represents a
> location-based quantity (e.g., which vertical column of fluid as specified by
> a surface mesh), how come you recommend using the iteration order to specify
> it? Unless I'm misunderstanding what you mean by logic position of the cell
> w/r/t a cell iterator...

What I meant to say is this: because floating point numbers can not be
computed in a stable way, it is often tricky to use them as indices or as the
basis of a hash lookup. If I understand you correctly, what you wanted to do
is something like

std::map<Point<dim>, MyProperty> property_map;
for (auto cell : ...)
{
MyProperty prop;
prop = some_function(depends on the location of 'cell');
property_map[cell->center()] = prop;
}

This is tricky because of the lookup based on a floating point number (the
'center' location of the cell). A better design might be

std::map<cell_iterator, MyProperty> property_map;
for (auto cell : ...)
{
MyProperty prop;
prop = some_function(depends on the location of 'cell');
property_map[cell] = prop;
}

You're still computing the property based on the location of the cell, but
you're storing it based on something that's conceptually an integer.