geometric hashing algorithmus

[mit]

Hallo,
hat jemand schon eine Python Implementation von "Geometric Hashing" Algorithmus gesehen?

Viele Grüsse.

[sma]

"Geometric Hashing" ist doch eine Bezeichnung für eine Klasse von Algorithmen. Welchen konkreten Algorithmus meinst du? Warum kannst du ihn nicht selbst implementieren? Befürchtest du, das wird zu langsam?

Würdest du nach "geometric hashing python" bei Google suchen, sähest du, dass der erste Link eine Sammlung von Algorithmen bereit hält, die in verschiedensten Sprachen, auch Python, implementiert sind. Ist dein Wunschalgorithmus dabei?

Stefan

[name]

Meinst du das?

[mit]

@sma: Ich glaube du beziehst dich auf diese Seite http://www.partow.net/programming/hashf ... ricHashing . Dort ist dieser nur kurz beschrieben, aber leider gibt es dort keine Implementierung.

@ name: Eigentlich meine ich dieses http://en.wikipedia.org/wiki/Hash_funct ... ic_hashing und http://july.fixedreference.org/en/20040 ... ic_hashing

Ich habe hier ( http://www.cs.rpi.edu/academics/courses ... mework/09/ )eine C++ Implementierung gefunden, aber leider nur für 2D und nicht für 3D:

Code: Alles auswählen

//geo_hash.h
#ifndef geo_hash_h_
#define geo_hash_h_

#include <list>
#include <vector>

//  A point location in 2d
class point {
public:
  point( float in_x, float in_y ) : m_x(in_x), m_y(in_y) {}
  point() : m_x(0), m_y(0) {}
  float x() const { return m_x; }
  float y() const { return m_y; }
private:
  float m_x, m_y;
};


//  The index for a bin in a 2d grid
class bin_index {
public:
  bin_index( int in_i, int in_j ) : m_i(in_i), m_j(in_j) {}
  bin_index() : m_i(0), m_j(0) {}
  int i() const { return m_i; }
  int j() const { return m_j; }
private:
  int m_i, m_j;
};

class geo_hash {
public:
  //  Construct a geometric hash with square bins having the specified
  //  bin width.
  geo_hash( float bin_width=10.0 );

  //  Add a point to the geometric hash
  void add_point( point loc );

  //  Add a vector of points to the geometric hash
  void add_points( std::vector<point> const& locs );

  //  Find all points in the geometric hash that fall within the given
  //  circle.  Order them by increasing x and for ties, by increasing
  //  y
  std::vector<point> points_in_circle( point center, float radius ) const;

  //  Find all points in the geometric hash that fall within the given
  //  rectangle defined by the min_point (smallest x and y) and the
  //  max_point (greatest x and y).  Order the points found by
  //  increasing x and for ties, by increasing y
  std::vector<point> points_in_rectangle( point min_point, point max_point ) const;

  //  Erase the points that fall within the given circle
  int erase_points( point center, float radius=1e-6 );

  //  Find the bin index associated with a given point location
  bin_index point_to_bin( point loc ) const;

  //  Find the hash value of the given point location
  unsigned int hash_value( point loc ) const;

  //  What points are in the bin associated with the given point
  //  location.
  std::vector<point> points_in_bin( point loc ) const;

  //  How many non-empty bins are there?
  int num_non_empty() const;

  //  How many points are in the geometric hash?
  int num_points() const;

  //  What is the size of the hash table?
  int table_size() const;  

private:
  //  This is an internal record for an entry in the table.
  struct table_entry {
  public:
    bin_index bin;
    std::list<point> points;
  };

private:
  //  Iterator and cons iterator typedefs for the hash table
  typedef std::list<table_entry>::iterator table_entry_iterator;
  typedef std::list<table_entry>::const_iterator const_table_entry_iterator;

  //  Compute the hash value for the given bin index
  unsigned int hash_value( bin_index bin ) const;

  //  Find the table location and list iterator within the table for
  //  the given point.  Used when changes to the table are possible.
  bool find_entry_iterator( point                  loc, 
                            int                  & table_index,
                            table_entry_iterator & itr);

  //  Find the table location and list iterator within the table for
  //  the given point.  Used when changes to the table are not
  //  possible.
  bool find_entry_iterator( point                        loc, 
                            int                        & table_index,
                            const_table_entry_iterator & itr) const;

  //  Find the table location and list iterator within the table for
  //  the given bin.  Used when changes to the table are possible.
  bool find_entry_iterator( bin_index              bin, 
                            int                  & table_index,
                            table_entry_iterator & itr);

  //  Find the table location and list iterator within the table for
  //  the given bin.  Used when changes to the table are not
  //  possible.
  bool find_entry_iterator( bin_index                    bin,
                            int                        & table_index,
                            const_table_entry_iterator & itr) const;


private:
  //  The table itself
  std::vector< std::list<table_entry> > m_table;

  //  Size of the square bins
  float m_width;

  //  Counters
  int   m_num_bin_entries, m_num_points;
};


#endif

Code: Alles auswählen

//geo_hash.cpp
#include "geo_hash.h"

#include <algorithm>
#include <cmath>

bool operator< ( point const& left, point const& right )
{
  return left.x() < right.x() ||
    ( left.x() == right.x() && left.y() < right.y() );
}

bool operator== ( bin_index const& left, bin_index const& right )
{
  return left.i() == right.i() && left.j() == right.j();
}


geo_hash::geo_hash( float bin_width )
  : m_table(4), m_width(bin_width), m_num_bin_entries(0), m_num_points(0)
{}


void
geo_hash::add_point( point loc )
{
  int            index;
  table_entry_iterator itr;

  //  Find the bin.
  if ( this->find_entry_iterator( loc, index, itr ) )
    {
      // If it is already there, just add the point
      itr->points.push_back(loc);
    }
  else
    {
      // Need to create a new entry in the table
      table_entry entry;
      entry.bin = this->point_to_bin( loc );
      entry.points.push_back( loc );
      m_table[index].push_back( entry );
      m_num_bin_entries ++ ;

      //  Resize the table right here if needed
      const float resize_multiplier = 1.5;
      if ( m_num_bin_entries > resize_multiplier * m_table.size() )
        {
          std::vector< std::list<table_entry> > new_table( 2*m_table.size() + 1 );
          for ( unsigned int i = 0; i<m_table.size(); ++i )
            for ( table_entry_iterator p = m_table[i].begin(); 
                  p != m_table[i].end(); ++p )
              {
                unsigned k = hash_value( p->bin ) % new_table.size();
                new_table[k].push_back( *p );
              }
          m_table = new_table;
        }
    }
  m_num_points ++ ;
}


void 
geo_hash::add_points( std::vector<point> const& locs )
{
  //  Just repeated apply add_point for an individual point.
  for ( unsigned int i=0; i<locs.size(); ++i )
    this->add_point( locs[i] );
}

//  
inline float square( float a ) { return a*a; }


std::vector<point>
geo_hash::points_in_circle( point center, float radius ) const
{
  // Establish bounds on the bins that could intersect the circle.
  bin_index lower = point_to_bin( point( center.x()-radius, center.y()-radius) );
  bin_index upper = point_to_bin( point( center.x()+radius, center.y()+radius) );

  int   index;
  const_table_entry_iterator itr;
  std::vector<point> points_found;  // record the points found

  //  Check each bin falling within the bounds.
  for ( int i = lower.i(); i<=upper.i(); ++i )
    for ( int j = lower.j(); j<=upper.j(); ++j )
      //  Is the bin occupied?
      if ( find_entry_iterator( bin_index(i,j), index, itr ) )
        {
          //  Check each point
          for ( std::list<point>::const_iterator p = itr->points.begin();
                p != itr->points.end(); ++p )
             { 
               //  If inside the circle, save the point
               if ( square(p->x() - center.x()) + square(p->y() - center.y())
                    <= square(radius) )
                 points_found.push_back( *p );
             }
        }

  std::sort( points_found.begin(), points_found.end() );
  return points_found;
}


std::vector<point>
geo_hash::points_in_rectangle( point min_point, point max_point ) const
{
  //  Establish bounds on the bins
  bin_index lower = point_to_bin( min_point );
  bin_index upper = point_to_bin( max_point );

  int   index;
  const_table_entry_iterator itr;
  std::vector<point> points_found;

  //  Check each bin
  for ( int i = lower.i(); i<=upper.i(); ++i )
    for ( int j = lower.j(); j<=upper.j(); ++j )
      //  Is the bin occupied?
      if ( find_entry_iterator( bin_index(i,j), index, itr ) )
        {
          // Check each point
          for ( std::list<point>::const_iterator p = itr->points.begin();
                p != itr->points.end(); ++p )
             {
               //  If it is actually inside the rectangle then save it
               if ( min_point.x() <= p->x() && p->x() <= max_point.x() &&
                    min_point.y() <= p->y() && p->y() <= max_point.y() )
                 points_found.push_back( *p );
             }
        }
    
  std::sort( points_found.begin(), points_found.end() );
  return points_found;
}


int
geo_hash::erase_points( point center, float radius )
{
  // Find the search range of bins 
  bin_index lower = point_to_bin( point( center.x()-radius, center.y()-radius) );
  bin_index upper = point_to_bin( point( center.x()+radius, center.y()+radius) );

  int   index;
  table_entry_iterator itr;
  
  int num_erased = 0;    // keep track of the number of points erased

  //  For each bin
  for ( int i = lower.i(); i<=upper.i(); ++i )
    for ( int j = lower.j(); j<=upper.j(); ++j )
      //  If the bin is non-empty
      if ( find_entry_iterator( bin_index(i,j), index, itr ) )
        {
          // For  each point in the bin
          for ( std::list<point>::iterator p = itr->points.begin();
                p != itr->points.end(); )
            {
              //  If the point is withn the radius
              if ( square(p->x() - center.x()) + square(p->y() - center.y())
                   <= square(radius) )
                {
                  //  Erase it
                  p = itr->points.erase(p);
                  m_num_points -- ;
                  num_erased ++ ;
                }
              else
                ++p;
            }
          //  Remove the bin if it is empty
          if ( itr->points.empty() )
            {
              m_table[index].erase( itr );
              m_num_bin_entries -- ;
            }
        }

  return num_erased;
}


//  Point location to bin index
bin_index
geo_hash::point_to_bin( point loc ) const
{
  int i = int( floor(loc.x() / m_width) );
  int j = int( floor(loc.y() / m_width) );
  return bin_index(i,j);
}


unsigned int 
geo_hash::hash_value( bin_index bin ) const
{
  return std::abs( bin.i() * 378551 + bin.j() * 63689 );
}


unsigned int 
geo_hash::hash_value( point loc ) const
{
  return hash_value( point_to_bin(loc) );
}


//  Find all points in the bin associated 
std::vector<point>
geo_hash::points_in_bin( point loc ) const
{
  std::vector<point> points_found;
  int   index;
  const_table_entry_iterator itr;

  if ( find_entry_iterator( loc, index, itr ) )  
    {
      points_found.resize( itr->points.size() );
      std::copy( itr->points.begin(), itr->points.end(), points_found.begin() );
      std::sort( points_found.begin(), points_found.end() );
    }
  return points_found;
}


int
geo_hash::num_non_empty() const
{
  return m_num_bin_entries;
}

int
geo_hash::num_points() const
{
  return m_num_points;
}

int
geo_hash::table_size() const
{
  return int( m_table.size() );
}


bool
geo_hash::find_entry_iterator( point                    loc, 
                               int                    & table_index,
                               table_entry_iterator   & itr)
{
  bin_index bin = this->point_to_bin( loc );
  return find_entry_iterator( bin, table_index, itr );
}

bool
geo_hash::find_entry_iterator( point                        loc, 
                               int                        & table_index,
                               const_table_entry_iterator & itr) const
{
  bin_index bin = this->point_to_bin( loc );
  return find_entry_iterator( bin, table_index, itr );
}


bool
geo_hash::find_entry_iterator( bin_index              bin, 
                               int                  & table_index,
                               table_entry_iterator & itr)
{
  table_index = this->hash_value( bin ) % this->table_size();
  for ( itr = m_table[table_index].begin();  
        itr != m_table[table_index].end() && ! (itr->bin == bin); ++itr )
    ;
  return ( itr != m_table[table_index].end() );
}


bool
geo_hash::find_entry_iterator( bin_index                    bin, 
                               int                        & table_index,
                               const_table_entry_iterator & itr) const
{
  table_index = this->hash_value( bin ) % this->table_size();
  for ( itr = m_table[table_index].begin();  
        itr != m_table[table_index].end() && ! (itr->bin == bin); ++itr )
    ;
  return ( itr != m_table[table_index].end() );
}

Ich habe dateien die beinhalten 3D-Koordinten:

Code: Alles auswählen

39      18.378  59.466  13.185
40      14.270  54.556  18.227
41      30.119  51.333  33.732
43      26.326  51.100  21.154
44      23.764  55.050  18.338
45      17.697  75.884  26.178
48      22.351  66.269  28.727
49      19.980  63.046  33.535

Leider weiss ich nicht wie man diesen Algorithmus für 3D implementiert?