Geometric Hashing

Geometric hashing is a method for efficiently finding geometric objects of the same or similar shape, even though they may be rotated and/or translated (scaling is not allowed).

A set of input models (polygons) are given which are defined by their coordinates. For a given query B (which is again a polygon defined by its point coordinates), geometric hashing tries to find the maximum number of points that coincide with the closest input model. Factors like rotation and translation of the model points need to be taken into account.

The points in the query model may be distorted (i.e. the query may not fit exactly
onto one of the input models), so you may require to do some neighborhood search
in case the model is very close to some of input model.

Geometric objects will be restricted to simple polygons.

Input will be a file in which the first line gives the number of models followed by the  model coordinates in each line in a format (x1,y1,x2,y2...) for every model.

It will then be followed by the number of queries and along with each of the queries in the same format at input models.

Output will the closest model number matching to the query model. Output ‘NO’ if the query doesn’t match any input model.

Sample Input

2 // No. of Models
10,10,30,10,30,20,10,20
10,10,20,10,15,20

1 // No. of Queries
10,10,20,10,20,30,10,30

Output
1

test
References

http://www-users.cs.umn.edu/~jieping/geometric_hashing.html

http://www.ii.uib.no/~inge/talks/ismb-tutorial/

For more details, mail to : sunando@cse.iitm.ernet.in