|
This is a very interesting question. I don't know if there is a known algorithm for that (but I guess there must be).
Just a thought: maybe you can start working on a basic idea like drawing a line from each vertex to the middle point of each side (excluding the two sides on which the vertex stands). Then examine the intersection points of these lines (excluding those that lie outside the polygon) and find the one which is farthest on average from all vertexes.
Not sure if this is the right way to go, but I hope I gave you some idea to work on.
Let me know if you find the solution, I'll be very interested.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
To calculate the centroid of a polygon:
Source: http://en.wikipedia.org/wiki/Centroid[^] and http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/[^]
PointF centroid(PointF[] p) {
float cx = 0;
float cy = 0;
float a = 0;
float ca;
for (int i = 0; i < p.Length; i++) {
ca = x[i] * y[(i + 1) % p.Length] - x[(i + 1) % p.Length] * y[i];
cx = cx + (x[i] + x[(i + 1) % p.Length]) * ca;
cy = cy + (y[i] + y[(i + 1) % p.Length]) * ca;
a = a + ca / 2;
}
cx = cx / (6 * a);
cy = cy / (6 * a);
return new PointF(cx , cy);
}
By the way, I am not sure if what you need is a centroid. Hope this helps, anyway.
|
|
|
|
|
I have raw metal sheets of various rectangular sizes (x1*y1, x2*y2,
... xn*yn).I want select best fit sheet which fullfill my requirement for getting new sheets of X*Y it also has some tolerence.
e.g
I have metals sheets like 200*100,300*200,250*500,50*100,100*100
and I Require 3 pieces of 100*100 with 3mm tolerence.so how do I find the best fit soluion and how do I implement this logic.
Thanks in advance.
|
|
|
|
|
I am guessing that the effort involved in implementing would be extensive and difficult unless you are a major gemotry geek. After a little searching it seems some of the relevant keywords that lead to academic articles on the topic are "Nesting", and "No Fit Polygon". Since nesting could get you more bird articles you might want to include "sheet metal" or "CAD" in your search. I know it isn't an answer, but it should help your search.
|
|
|
|
|
thx for your suggestion. if any one has done same kind logic for cutting it will be more helpful for me.
|
|
|
|
|
I know it can be done for example with Dynamic Programming[^], but it requires expertise in that particular technique.
My suggestion if you're not specifically into optimization is to go for a stochastic algoritm like Simulated Annealing[^] or a greedy algorithm derived from the classical Kanpsack Problem[^], since they are very easy to implement, not time intensive, and give good results. In both cases, the trick to make it work for your case is to find the right Heuristic[^] function, that is the function to decide wich placing of each rectangular shape is better at a certain iteration.
Another very good approach is using Rectangle Packing algorithms. Google that and you should find info.
Just as a reference, there are many generic optimization techniques, which can apply to specific cases depending on requirements and problem modeling, you can have a look Here[^] for an overview.
Good luck.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
thx for suggestion. but any one has done same kind of sheet cutting logic it will more helpful for me.
|
|
|
|
|
Hi all,
I am creating a little program for scoring RadioControl contests.
First, I distribute the pilots (say they are 30) in 3 groups of 10, and repeat it (in different combinations) several rounds (say 6 rounds)
In each round, each pilot flies one time, only in one group, against other 9 pilots.
I create the groups randomly. Then I count scores and present it.
BUT, the big BUT is some pilots complaint: "I have only flied 1 time against pilot nameJoe , and 4 times against pilot namePeter"
So I need some direction for creating R rounds of N pilots in G groups, trying that all the pilots have flied against each of the other pilots a similar number of times (ideally the same number of times, but if not, with a little difference).
I.e.: this is a contest of 6 pilots (A,B,C,D,E,F), 4 rounds, 2 groups:
ABC DEF
AFC BED
EBD ACF
FCE ADB
A has flied 2 times against B and 3 against C, but none against E
Thank you for any sugestion.
Alex
modified on Thursday, May 27, 2010 6:33 PM
|
|
|
|
|
|
I know there's a few tournament organization algorithms, but I'm not much into that, so I can't suggest you any.
You are using a stochastic algorithm, which can surely be ok. You just need to add some logic to de-randomize matchings in order to get the result you need.
A simple approach can be holding the number of times each pilot flies against each other in a list (array).
Select a random pairing, then randomly select one of the two paired pilots (or just iterate through pilots and choose the second pilot randomly, this depends on how you currently do pairing ofc).
Look into the selected pilot's list, starting at the index corresponding to the second pilot, then proceed in one direction until you get to the same position, holding the index of the cell with the least value you find.
When you're done, change the second pilot to the one whose corresponding cell held the least value.
This is the basic rough idea, it must of course be adapted to your current algorithm and data structures.
It should ensure a certain degree of randomness and come close to the result you need.
Good luck.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
In fact, I was doing a similar aproach, using an array for counting the matches between each pair of pilots. But I got problems when swapping the pair of pilots for correcting the anomalies.
Actually, this is an old problem. Just yesterday, googleing, I found
http://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem[^]
There are some solutions. The best I have found use you suggested approach, but adding a "taboo" value, counting the iterations a pair is not swapped:
http://delphiforfun.org/programs/kirkman.htm[^]
Thank you for you help, anyway
Alex
|
|
|
|
|
My pleasure.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
WolframAlpha[^] returns a different joke for a "Tell me a joke" query.
|
|
|
|
|
Q: Why did the mathematician name his dog "Cauchy?"
A: Because he left a residue at every pole.
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.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
|
Hello,
I need to analyze a document and compile a statistics of the sentences that are used more than once. As sentences I actually mean any sequence of words. I read that compression algorithms do something similar to what I want creating dictionaries of blocks of text with a piece of information telling the frequency of it.
Thanks a lot for any help.
|
|
|
|
|
|
Just keep dividing by 10 and saving the remainder. That will give you the digits in reverse order. Alternatively you can compare the number to successive powers of 10 until you find the smallest value greater than your number. Then just divide by the next lower power and save the quotient, repeat until you are back to zero.
It's time for a new signature.
|
|
|
|
|
"Best" in what way?
Since I have no specifications, I'd probably use something quick and dirty like
int n = 1024;
int d = 2;
int ds = int.Parse(n.ToString().Substring(d,1));
etc.
CQ de W5ALT
Walt Fair, Jr., P. E.
Comport Computing
Specializing in Technical Engineering Software
|
|
|
|
|
I forgot to mention that I was working on arduino
|
|
|
|
|
Ahh, now we have some specifications!
CQ de W5ALT
Walt Fair, Jr., P. E.
Comport Computing
Specializing in Technical Engineering Software
|
|
|
|
|
Convert the number to string
Loop through the characters, store it.
Eg :
<pre>
Dim digits As New ArrayList
For Each digit As Char in CStr(number)
digits.Add(CInt(digit))
End For
</pre>
|
|
|
|
|
like others have said, a loop containing a modulo 10 and a divide by 10, are what is required. Assembly programming may give access to an instruction that does both operations in one, something higher-level languages typically don't exploit.
You probably don't want any leading zeroes, so you should exit the loop as soon as the quotient is zero, but you still need to output the current remainder, i.e. the test belongs at the bottom of the loop as you want at least one digit.
Keep in mind that the number has to be positive for all of this to work correctly; for negative numbers, you need to "negate" first.
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
I only read formatted code with indentation, so please use PRE tags for code snippets.
I'm not participating in frackin' Q&A, so if you want my opinion, ask away in a real forum (or on my profile page).
|
|
|
|
|
After a long trying, I found this snippet:
int number = 1024;
int digit1 = ((number / 1000) % 10);
int digit2 = ((number / 100) % 10);
int digit3 = ((number / 10) % 10);
int digit4 = ((number / 1) % 10);
|
|
|
|
|
ant-damage wrote: After a long trying, I found this snippet:
... which is great until you give it a number like 456789.
Or if you try it with 23, you'll end up with zeroes.
As others have said, a loop will work no matter what number you throw at it.
Days spent at sea are not deducted from one's alloted span - Phoenician proverb
|
|
|
|