hi,
i have 4 coordinates [(x1,y1),(x2,y2),(x3,y3),x4,y4)] of a rectangle.then i have to generate a unique ID for this recangle using this coordinates.finally by decrypting that ID we shold be able to retreive original coordinates.IF you can pls help me
thanks,
regards,
kelum
1) What are the ranges of values for the coordinates?
2) Are there any constraints on the type of the ID?
3) Is your use of the word "decrypting" meant to imply that the ID is encrypted in the security sense, or simply "encoded" as in "turn these 8 values into a single value?
If the numer of permutations of legal values is larger than Integer.MAX_VALUE - Integer.MIN_VALUE + 1, then you can't use an int as your ID. Likewise the corresponding values for Long/long.
If the number of permutations is small enough for, say, a long, then you can just use the coordinates' values as different bits of groups. Here you have 8 coordinates, and long has 64 bits, so if each coordinate only need 8 bits or less, you can put each one into the byte of a long.
If String is acceptable, you could just build a String from the coordinates' values.
The above both assume you don't actually need "encryption" in the "security" sense.
Hi Kelum,
Generally, if you are trying to compute a unique ID/hash code for a certain object (in this case, a rectangle) based on some of its properties (in this case, the coordinates of its vertices), you are just trying to create a number that will be different for rectangles with different vertices and the same for rectangles with the same vertices. The point of an ID/hash code is usually *not* to be able to retrieve the original coordinates from the ID/hash code.
What exactly are you trying to achieve? If you need to retrieve the coordinates later, why don't you simply pass around the Rectangle object instead of some ID (which will be very hard to define to guarantee that you will be able to get the original values)?
Here's how you would compute the hash code (from which you unfortunately won't be able to retrieve the original values):
public int hashCode() {
return 31 * (31 * (31 * (31 * (31 * (31 * (31 * (31 * x1 + y1)) + x2) + y2) + x3) + y3) + x4) + y4;
}
31 is the hash multiplier used by many hash code functions in the J2SE. All primes are good hash multipliers, for example 29 is a common one. Primes minimize the probability of two different objects yielding the same hash code.
Hi,
If id can be a string they simply u can put all the coordinates values together in a string, each coordinate seperated by some delimiter character.
Like if u have [ (1,2),(3,4),(5,6),(7,8) ], u can put 1:2:3:4:5:6:7:8. Here I have used : as delimiter.
You can also generate seperate strings for X coordinates and Y coordinates. But in that case you have to make sure that the order of X and Y are same. Means if X1 is the first integer in one string, Y1 must be the first integer in second string.
Hope this helps.
hi,
thanks for your suggestions.
actually this is an unique identification system for objects on the land(houses).
in this case we generate the bounded rectangle of that object and generate id for that.
therefore the id must user friendly.
now we are considering about bit stream and store it as hexdecimal value(to genaerate small id--125AC)
pls help me.
thanks,
regards,
kelum
> Isn't that useless because:
>
> 32^8 = 32 * 32 * 32 * 32 * 32 * 32 * 32 * 32
> ...= 2^5 * 2^5 * ... * 2^5
> ...= 2^(5*8)
> ... = 2^40
>
> and the largest int value is 2^32.
This is kind of off-topic, but integer overflow still generates different codes for different coordinates. =)
> > Isn't that useless because:
> >
> > 32^8 = 32 * 32 * 32 * 32 * 32 * 32 * 32 * 32
> > ...= 2^5 * 2^5 * ... * 2^5
> > ...= 2^(5*8)
> > ... = 2^40
> >
> > and the largest int value is 2^32.
> This is kind of off-topic, but integer overflow still
> generates different codes for different coordinates.
> =)
Not necessarily in this case. Assuming all 8 values are ints, then you have 2^256 values mapping to 2^32 slots.
> Assuming all 8 values
> are ints, then you have 2^256 values mapping to 2^32
> slots.
Right. However, even if a more fit multiplier is used, uniqueness of the computed hash code is still not guaranteed -- it is not supposed to be in the case of a hash function. If 100% uniqueness needs to be achieved, traditional hashing techniques are not going to work.
There is, in fact, a way to take a sequence of numbers and turn them into a guaranteed unique number, and then get the original numbers back out of the original number.
However.... you will not want to use int or even long. Go straight to BigInteger, do not pass go, do not collect an open source licence.
The method is called Godel numbering. Either the o or e have funny dots over them (apologies to German readers).
The name Godel is pronounced Girdle (or Gird-ill).
Anyway, here is a description of the method. For numbers a, b, c and d their unique combination is:
2^a * 3^b * 5^c * 7^d. (Two to the power of a, Three to the power of b... etc).
Notice that 2, 3, 5 and 7 are all *prime* numbers. According to the fundamental theorem of arithmetic, the number generated is *guaranteed* to be unique.
To get a, b, c, d back, just compute how many times 2, 3, 5, 7 are factors of the big number.
For your edification, here are the first 25 prime numbers:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
good luck.
Oh, if you want a smaller number (and you probably will) you could figure out the range for each number, and offset it by that much. eg for numbers aaaaa, bbbbbb, cccccc, ddd you would get
0aaaaabbbbbbcccccc000ddd (where a and d had to be padded because they weren't enough digits).
You don't even need to figure out how many digits you are going to use, if you work out all four numbers at the same time then you could just pad the smaller ones out to the size of the largest one.
Then the first quarter of the digits are your first number, the second quarter are the second (etc).
To encrypt that easily against casual glances you could mix up the order of the digits by some scheme, you could append (or prepend) a byte and then choose from any of 255 byte rearranging schemes... etc.
Against professional unencrypter? I cannot help.
> > Assuming all 8 values
> > are ints, then you have 2^256 values mapping to 2^32
> > slots.
> Right. However, even if a more fit multiplier is used,
> uniqueness of the computed hash code is still not
> guaranteed -- it is not supposed to be in the case of
> a hash function. If 100% uniqueness needs to be
> achieved, traditional hashing techniques are not going
> to work.
Yeah, I know. But the OP doesn't seem to be searching for a hash function.
> (x1*10000000)+(y1*1000000)+(x2*100000)+(y2*10000)+(x3*1
> 00)+(y3*100)+(x4*10)+(y4*1)
That won't work because if, for example, x4 has two digits, you won't know that and believe that the first digit is y3.
On another note, there is no way to do this correctly using just a primitive number. You'd have to use something inefficient like BigInteger.
- D.t.O
i think in this case it wouldn't be terribly difficult to store those numbers in an int
i mean, you can just re-think your design storage based on what the numbers are.
i.e. store bottom left(x, y) position. we know its a rectangle and can say that no edge will
be longer than J distance.
so we can then store only the top left position(y) because we know that the "x" value for
the top left position ='s that of the bottom left
and so on.
and by saying that no egde is longer than J distance we can be aware of the amount of
bits we need to assign to each number ... (how many houses are longer than 1024 meters?, for example).
i hope you can understand that :)
of course, its not the most scalable solution ! look-out when you get a large house :)
of course, if its a real rectangle you'd only need to store 3 numbers
x,y of some corner, length and width of box.
and presumably you may have a finite set of Length's and Widths for boxes, that way you could compress it even further into simply x,y and M, m representing the item in the set of lengths and widths :) :)
"a kind of a hash" -- sorry couldn't find another word that would express the idea concisely.
Is compression really that important? How much are you trying to compress? After all, every rectangle, if you use int coordinates, is 8*32 bits = 32 bytes. That's 32 KB for 1000 rectangles.
Just a thought.
- D.t.O
> "a kind of a hash" -- sorry couldn't find
> another word that would express the idea concisely.
>
> Is compression really that important? How much are you
> trying to compress? After all, every rectangle, if you
> use int coordinates, is 8*32 bits = 32 bytes. That's
> 32 KB for 1000 rectangles.
> Just a thought.
maybe he's on a j2me phone, and needs to store it, or something.
> does it have to be a number?
"maybe he's on a j2me phone, and needs to store it, or something."
- silk.m
If he really is not some device with serious space limitations, anything other than a primitive number would be counterintuitive.
But if he's got a different reason, it's a different story. :-)
- D.t.O
hi,
i looked all your comments.
first we have to identify the objects on the land(houses)
then i hava a mecanism to get bounded rectangle for that object.
then we hava to generate id for that rectangle.
because 2 objects can not have same rectangle.so it is unique.
now a days i am thinking about bit stream.
startX .startY.length.width.
pls send your comments.
regards,
kelum
Bit Stream makes sense if you are going to send & receive the numbers on-the-fly, kind of playing by ear until no more numbers come in.
If you want to send everything at once, just create an array. A 2D array with the rows being the rectangles and every column corresponding to one of the four values will accomplish the task. You could even create a serializable class which writes the elements of that array to a file so you can access it later.
I realize that I am not answering your question of how to create a unique ID, but I really do not understand why this is necessary (the 2^x * 3^y * ... method is probably the only one that works, but it creates some really big numbers). Remember, KISS. =)
Regards,
- D.t.O
If you're going to use a bitstream of any sort, be sure that the bit (and therefore byte) ordering you chose is known. Otherwise if you end up re-reading the stream on a machine of different byte-ordering your values will come out wrong.
I don't know if Java takes care of this for you by default though, it may.
You seem to want to create a UNIQUE index for each REACTANGLE. You also seem to want to be able to EXTRACT the coordinates of the rectangle from that index. Looking for numbers may be a lot of work. If you need them for a database, why not let the database create its own unique indeces and refer to the coordinates for that entry in the table?
If you want to be able to compare rectangles (as in extablishing if they are the same) in the java langauge you can overwrite/create the equals method for your (lets call it) Squares class.
If you really have no choice then power is in limiting the info you want to store. Four corners of a rectangle are exclusively determined by 4 indices (minX, minY, maxX, maxY) . You must establish their maximum possible value within you application. If the're small enough you could create a long by multiplying the first coordinate by 1, the second by the maximumExpectedValue of the first, the third by the maximumExpectedValue(of the first)*maximumExpectedValue(of the second) and stepping it up one more time for the fourth. Getting the coordinates back then requires dividing, truncing and dividing the left-overs.
Hope this helps
AP
> i have 4 coordinates [(x1,y1),(x2,y2),(x3,y3),x4,y4)]
> of a rectangle.then i have to generate a unique ID for
> this recangle using this coordinates.finally by
> decrypting that ID we shold be able to retreive
> original coordinates.
Well, if you cannot find any redundancies you'll have to store the 4 coordinates because each bit counts. Maybe you could store the rectangle as one point and three vectors. The vectors would be relative to the point and maybe didn't have to be that "wide", like for example the point could be ints and the vectors bytes or so.
Do you have a solution already?
Silk_m said something important: you only need X1, Y1, Lx and Ly.
You must find out what is the biggest length(Lx) you will have and the biggest width, and also the smallest length and the smallest width if they are not 0. Make Dx the the actual length minus the smallest length you will ever have and MaxDx the maximum value for Dx.
Translate X1 and Y1 so that they are always positive and call them Xt and Yt.
If MaxX1t is bigger than Y1t and MaxDx bigger than MaxDy the smallest possible amount of numbers to store all this you will achieve by the following formula:
Xt + MaxXt*Yt + MaxXt*MaxYt*Dx + MaxXt*MaxYt*MaxDx*Dy
that number being:
MaxXt + MaxXt*MaxYt + MaxXt*MaxYt*MaxDx + MaxXt*MaxYt*MaxDx*MaxDy
If it,s in meters and X sits between -10,000 and + 10,000, Y between -5,000 and 5,000 Lngth between 10 and 19, width between 20 and 24 you get
20,001 + 20,001*10,001 + 20,001*10,001*10 + 20,001*10,001*10 *5 as the largest number to store.
more or less:
20*2^10 + 200*2^10 + 2*2^10*2^10 + 10*2^10*2^10 = 240*2^10 + 12*2^20 < 13*2^20 < 2^24 so you have a factor of 2* space left over for this case is you use an int. If you get just a little over MaxInt or in a more realistic case MaxLong (I mean Long.MAX_VALUE) pick the right point in the calulation to double your max number by translating the end result to cover anything from long.MIN_VALUE to Long.MAX_VALUE and so you score another factor 2.
Please let us all know what you are doing!