|
I'm trying to figure out how to split a polygon (in the form a C# Point array) into the least number of rectangles. The polygon itself is already limited to only have straight horizontal or vertical lines. So it can always be split into n number of rectangles, I'm just not sure how to go about a) splitting it, and b) figuring out the lowest number of rectangles.
So if someone doesn't mind, could you give me a rough example and the theory behind it?
|
|
|
|
|
Hi,
not a formal algorithm, but something to get you started:
given a polygon with straight angles only, you need four points to describe one rectangle.
if you add two points, you can only get an L-shape for which you basically have two
2-rectangle fills (excluding overlapping rectangles).
for every two points you add, you will need one more rectangle.
So: P = 2*R + 2
with R = number of rectangles and P = number of points.
If you allow for overlapping rectangles though, you may be able to cover the same area
with fewer rectangles. Example: form a cross from two rectangles, you'll get 8 points.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Unless you have a T shape... you could do it with 2 non-overlapping rectangles but it has 8 points.
Jeff
|
|
|
|
|
Can someone please explain to me how assym encryption algs work? It appears that there are two mathmatically related keys, but they are related in some "hard to find" way. My understanding is that you encrypt the data with some public key, then the same data can only be decrypted using both the public and private key. If my understanding is correct, then I am confused as to how the sender encrypts something, but that encryption cannot be undone using only the public key. Can someone please explain this to me? Thanks,
Jeff
|
|
|
|
|
Skippums wrote: Can someone please explain to me how assym encryption algs work?
http://en.wikipedia.org/wiki/Public-key_cryptography[^]
The most common ones [asymmetric key systems] have the property that Alice and Bob each own two keys, one for encryption and one for decryption. In a secure asymmetric key encryption scheme, the decryption key should not be deducible from the encryption key. This is known as public-key encryption, since the encryption key can be published without compromising the security of encrypted messages. In the analogy above, Bob might publish instructions on how to make a lock ("public key"), but the lock is such that it is impossible (so far as is known) to deduce from these instructions how to make a key which will open that lock ("private key"). Those wishing to send messages to Bob use the public key to encrypt the message; Bob uses his private key to decrypt it.<br />
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
Hi Jeff,
imagine two large prime numbers, say 50 digits each.
There are encryption algorithms that use two such numbers, needing them both to decrypt, but
only needing their product to do the encryption. So the product is the public key,
and the prime factors constitute the private key. Splitting a 100-digit nhumber in two
huge primes is a big job, not to be solved in a matter of hours...
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Man, you are everywhere! Are you paid to contribute to this thing? I think that you have single-handedly answered nearly every question that I have ever posted on this forum. Anyway, I understand how the public and private keys can be generated after looking at wikipedia's encryption page. What I am still confused about is how, given only the public key, you can encrypt something but not decrypt it. How is it that I can take some data, apply some known algorithm, and still not be able to undo that algorithm after I am done? It just doesn't seem possible. Any further insight as to how things get irreversibly encrypted would be appreciated. Thanks again,
Jeff
|
|
|
|
|
Well it is not really irreversible, the fact is the cost is several orders of magnitude
larger to decrypt (without the prime factors) than it is to encrypt.
Some operations are just more difficult to undo than they are to do. Example:
what is the value of 1234567 ^ 7 modulo 2^32 is easy
but which number x satisfies x^7 modulo 2^32 = 7654321 is hard.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
ahhhhhh! Thanks again for the help!
Jeff
|
|
|
|
|
Hi Everyone
I want to post an article containing an implementation of an algorithm. Is there any way to display mathematical equations in articles?
Ryan
|
|
|
|
|
Maybe the Equation editor in MS Word, or as a graphics image if you use Latex or Tex...
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
|
|
|
|
|
Paul Conrad wrote: Maybe the Equation editor in MS Word, or as a graphics image if you use Latex or Tex...
The equation editor emits images that would need to be inserted into the article.
Is there any way of embedded Latex into the HTML code and having that automatically generate the images?
|
|
|
|
|
Hi, I guess there are lots of equation editors (MS Word has one) that can emit HTML code;
such code could be pasted into an article.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: Hi, I guess there are lots of equation editors (MS Word has one) that can emit HTML code;
such code could be pasted into an article.
Thanks for the suggestion. Just tried it and it generates images that would need to be inserted into the article.
I was hoping to find a way to embed something like Latex into the article HTML and automatically generate the images.
|
|
|
|
|
|
Check the DoxyGenerator that allows you to document your code with latex Entries.
It Generates Automatically the htmls with the pngs that represents the equations
JO
|
|
|
|
|
One BYTE variable can store 256 distinct values.
One short variable can store 65535 distinct values.
Can one BYTE or short datatype variable store a value between 0 and 999999 ?
Any intermediate variables , arrays can be utilised which will help in packing single BYTE or short variable with values from 0 to 999999.
Thanks & Regards.
|
|
|
|
|
ccpptrain wrote: Can one BYTE or short datatype variable store a value between 0 and 999999 ?
Oh yes (just matter of mapping), but NOT ANY VALUE between 0 and 999999.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
CPallini wrote: but NOT ANY VALUE between 0 and 999999.
I believe the proper term would be ALL values between 0 and 999999. Using a replacement map, I can map byte==0 to any number of bits, but I can store at most 256 values in my map.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
El Corazon wrote: I believe the proper term would be ALL values between 0 and 999999
I believe the proper term is EVERY value between 0 and 999999.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
damn... got me... okay... I stand... err... sit corrected. 
This reminds me of an old joke about mapping my college prof told.... what is the size limit of values you can store in one bit? no limit on size, but you can only store two of them.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
A byte can store 256 of the million values, a short can store 65536 of the million directly, but if you need to be able to store the entire range you're going to need to use a minimum of 20 bits, and unless your storage requirements are very tight relative to your hardware performanace bit packing isn't going to be worth the CPU overhead vs storing in a native 32 bit value.
If you're archiving data or transmitting it in packets instead of streaming it in realtime you can use data compression, and potentially be able to use <16bits per value.
--
If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.
|
|
|
|
|
Thanks all for correcting my question and giving suggestion.
I am having 2D array of size say 1000*1000
In this 2D array each element has any value between 0 to 999999
So decided to take int Aint[1000][1000] as array.
There are only 300 unique elements in this array and all other elements are repeated,
i.e this array has repeated values with only 300 unique values.
Also this array takes 1000*1000*4 = 4000000 bytes.
So I am trying to construct an array
int u[300] which will contain the unique values from Aint[1000][1000].
And instead of making int Aint[1000][1000] I decided to make BYTE Abyte[1000][1000] as my 2D array.
Now this Abyte 2D array's elements should contain any values from 0 to 299.
Previously:
int value = Aint[750][750] = 999999;
Now I will fetch value in this manner:
Abyte[750][750] = 290;<br />
u[290] = 999999; <br />
int value = u[ Abyte[750][750] ] = 999999;
But problem is Abyte's element can have values between 0 and 255.
I need to store 290 in single BYTE.
This approach has reduced memory requirement from 4000000 Bytes ( sizeof(Aint) )
to
1001200 bytes ( sizeof (Abyte) + sizeof(u) )
With this approach page faults can be reduced.
Thanks & Regards.
|
|
|
|
|
You cannot store more than 256 unique values in individual cells of a Byte array. You could reduce your memory footprint in two ways.
The first would be to compress the array in memory. The cost of that would be the loss of easy random access. Instead of O(C) performance to access an arbitrary value you'd have O(N) performance, like a linked list. IIRC with most modern compression algos modifying a value will require recompressing the array from the insert point forward, making an insert even more expensive.
The second would be to use bit packing, to simulate a 9bit int. This would remain O(C) performance, but the constant value would be much higher.
You'd probably need to implement both these approaches and try multiple compression algos for the first (compressed size vs speed to partially decompress to get an arbitrary value) and do performance testing to see if these are actually faster than using an extra 1 meg of memory (using a 16bit int).
Unless you're working on an embedded system with very tight memory constraints however I'm doubtful that either will actually be faster if you're doing any nontrivial examination/processing of the data.
--
If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.
|
|
|
|
|
Thanks for the pointers...
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
