CODEWITHSUNDEEP
c++algorithmhashhashmaphashtable
devsda
devsda

Reputation: 4222

what is the good hash function for given situation?

There is a points given in two dimensional plane and I want to count maximum collinear points for that I calculated all possible lines slopes and their intercepts. To solve this problem, I tried to build a hash table but i am unable to find a hash function by which I can easily point all collinear points in one hash key. So help me to find out hash function that fits for this scenario?

Upvotes: 2

Views: 418

Answers (2)

PermanentGuest
PermanentGuest

Reputation: 5331

Also you could consider an algorithm based on the Hough Transform. Hough transform allows you to detect lines in an image by counting the number of points falling in a line with a given slope and intercept (or angle and distance of the line from the origin). So, in your specific case, you could store the votes for each distance/angle pairs in a two-dimensional matrix and later take the maximum value from this matrix. This would give you the maximum number of co-linear points. If you allow for approximations then, instead of looking for a single value, you could find a small rectangular grid providing maximum sum of value.

Upvotes: 1

gexicide
gexicide

Reputation: 40058

This is not possible, because colinearity is not transitive. I.e., lets say A B and C lie on a line (i.e. are colinear). Therefore, A B and C should get the same hash key. Next, C D and E also lie on another line. Therefore, C D and E should also get the same hash key. Consequently, A B receive the same hash key as D and E, which is wrong because these points are not colinear.

In addition, colinearity is defined on sets of points, so my above definition is rather vague. I.e. you cannot say A and B are colinear (well, you can, but if you only regard two points, each pair of points is colinear).

What you can do is save the sets of colinear points in a hash map. Then, a good hash function would simply consist of the slope s and ordinate intercept i. For example, you could use s * 31i. This hash map can be used to add new points to the sets and finally count the size of the sets to retrieve your answer.

Upvotes: 7

Related Questions