|
123lucy45 wrote: i need an algorithm itself
Aha, that is different now. I used to solve such puzzles with an exhaustive search, breadth first. The only caveat is one must detect positions that have been reached before. Not hard at all.
|
|
|
|
|
Wow. A little Googling for "15 puzzle solve algorithm" reveals a bunch of interesting stuff, and examples.
|
|
|
|
|
I'll give you a starting point. This puzzle can be solved efficiently with three algorithms:
1. The simple case: For numbers not in the rightmost column or the last two rows, move tiles to create a blank space between the next tile to place, and the correct location for this tile. Then move the tile into the blank space, bringing you one step closer to correct placement for this tile. Repeat until the tile is in the correct location.
2. For a position in the rightmost column (but not the last two rows), the problem is getting the wrong tile out and the right tile in. Get the right tile under the correct location (in the rightmost column). Then move another tile in the same row as the correct location down one (temporarily moving it out of its correct location), slide the rest of the row to the left, move the right tile up (to its correct position), get a blank spot under the wrong tile, move the wrong tile down, move the rest of the row right, then move the tile you moved out of its correct position back, thus completing the row.
3. For the last two rows, move them in a circular pattern until you get the opportunity to swap two tiles that are in the wrong order. Repeat until the last two rows are correct.
|
|
|
|
|
Does anyone have an algorithm that avoids a month table which computes the last day in a month?
|
|
|
|
|
convert to date (1- x+1 - year); // where x is the month number - obviously you need to take care of December.
reduce 1 day from it.
Hope it helps
It is Good to be Important but!
it is more Important to be Good
|
|
|
|
|
I'd get the 1st day of the month after the one you're interested in, then subtract 1 day.
CQ de W5ALT
Walt Fair, Jr., P. E.
Comport Computing
Specializing in Technical Engineering Software
|
|
|
|
|
|
Hi, I posted this on the C# section but then I got to think maybe the solution could be mathematical so I should have posted here instead.
I want to create a filled cylinder or a tube that can be slanted.
So what I do is I created a closed curve using 4 points (using FillClosedCurve) with 0.8f tension. Then I translated the same closed curve vertically to create a sense of height. But then how do I fill the sides?
Here is an image to illustrate my explanation: http://img692.imageshack.us/img692/9461/100319codeprojectquesti.png[^]
Thanks for any help.
|
|
|
|
|
You can calculate the semi-major axis length. Have a look at:http://en.wikipedia.org/wiki/Semimajor_axis[^].
If you start from the centre of the ellipse (which in your example is the centre of your rectagle) and add this length, you get the point on the circumference of the ellipse where you can start (and end) drawing your vertical line.
Starting from there, you can adjust the angle to find the perfect spot for your verical lines.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Can you give me the equation to find the semi-major axis length, knowing the four points I got? My head just in the verge of exploding reading the article. I'm really not that good at math, honest.
I also read and tried the code from http://en.wikipedia.org/wiki/Ellipse[^], following the links in wikipedia. This function to generate an ellipse is almost the same as DrawClosedCurve() or DrawEllipse(), using that I still can't get the outer most point to put the line.
|
|
|
|
|
Valeriant wrote: I also read and tried the code from http://en.wikipedia.org/wiki/Ellipse[^], following the links in wikipedia. This function to generate an ellipse is almost the same as DrawClosedCurve() or DrawEllipse(), using that I still can't get the outer most point to put the line.
Yep that's a good starting point too. See where it makes you go through the whole circumference:
for (var i = 0; i < 360; i += 360 / steps)
You can use that to get the coordinates to the interesting points, using the angle.
I'll try to put together some code when I have some spare time, but it won't be soon I'm afraid.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Appreciate the time, will wait your help.
I did try each points generated from the steps, but none are exactly the outer most two. And formulating the angle, I cannot.
|
|
|
|
|
Ok I managed to take a couple of minutes off and write some code. Sorry it took me so long, but I'm busy as a bee these days.
Please consider that the code I'm presenting here is quite raw, and you'll probably want to clean it up and make a few changes.
I decided to give you a start-from-scratch idea, which is easier to implement. Please remember that drawing a good looking circle or ellipse is not necessarily an easy task. Have a look on the web, you'll see there are a bunch of good algorithms to do that.
The simplest way of drawing an ellipse is something like what you found on wikipedia. In my example you'll see a very similar approach. I just added rotation, which you need in order to draw your cylinder, and optimized the code (you don't have to go through the whole 360 degrees, but only half of it, cause the rest is specular).
private class EllipseOuterXPoints
{
internal double left_x = double.MaxValue;
internal double left_y = double.MaxValue;
internal double right_x = double.MinValue;
internal double right_y = double.MinValue;
internal void CheckPoint(double x, double y)
{
if (x < left_x)
{
left_x = x;
left_y = y;
}
if (x > right_x)
{
right_x = x;
right_y = y;
}
}
}
private EllipseOuterXPoints DrawEllipse(Graphics g, double center_x, double center_y, double semi_minor, double semi_major, double angle)
{
EllipseOuterXPoints OuterPoints = new EllipseOuterXPoints();
double beta = -angle * (Math.PI / 180);
double sin_beta = Math.Sin(beta);
double cos_beta = Math.Cos(beta);
double increment = (Math.PI * 2) / (semi_major * 2);
double sin_alpha;
double cos_alpha;
double x1 = 0;
double y1 = 0;
double x2 = 0;
double y2 = 0;
double prev_x1 = 0;
double prev_y1 = 0;
double prev_x2 = 0;
double prev_y2 = 0;
double first_x1 = 0;
double first_y1 = 0;
Pen mypen = new Pen(Color.Black);
for (double alpha = 0; alpha < Math.PI; alpha += increment)
{
sin_alpha = Math.Sin(alpha);
cos_alpha = Math.Cos(alpha);
x1 = center_x + ((semi_major * cos_alpha * cos_beta) - (semi_minor * sin_alpha * sin_beta));
y1 = center_y + ((semi_major * cos_alpha * sin_beta) + (semi_minor * sin_alpha * cos_beta));
sin_alpha = Math.Sin(alpha * 2);
cos_alpha = Math.Cos(alpha * 2);
x2 = center_x + ((semi_major * cos_alpha * cos_beta) - (semi_minor * sin_alpha * sin_beta));
y2 = center_y + ((semi_major * cos_alpha * sin_beta) + (semi_minor * sin_alpha * cos_beta));
if (alpha == 0)
{
first_x1 = x1;
first_y1 = y1;
}
else
{
g.DrawLine(mypen, (float)prev_x1, (float)prev_y1, (float)x1, (float)y1);
g.DrawLine(mypen, (float)prev_x2, (float)prev_y2, (float)x2, (float)y2);
}
OuterPoints.CheckPoint(x1, y1);
OuterPoints.CheckPoint(x2, y2);
prev_x1 = x1;
prev_y1 = y1;
prev_x2 = x2;
prev_y2 = y2;
}
g.DrawLine(mypen, (float)x2, (float)y2, (float)first_x1, (float)first_y1);
return OuterPoints;
}
First point you should note is the "magic" taking place here:
double increment = (Math.PI * 2) / (semi_major * 2);
This is what allows you to draw a decent-looking ellipse. The number of points you calculate on the circumference is derived by a brute empirical calculation based on the major axis length. Not that fine, not that beautiful, but it works.
Secondly, note that while I draw the ellipse I keep a record of the leftmost and rightmost points (this is based only on the X axis, since I didn't manage rotation on the Y axis!). These are the outer points you will connect to create your cylinder.
So, just call this code inside a Paint event with something like:
private void picCanvas_Paint(object sender, PaintEventArgs e)
{
EllipseOuterXPoints OuterPoints1 = DrawEllipse(e.Graphics, picCanvas.Size.Width / 2, picCanvas.Size.Height / 4, picCanvas.Size.Height / 8, picCanvas.Size.Width / 4, 10);
EllipseOuterXPoints OuterPoints2 = DrawEllipse(e.Graphics, picCanvas.Size.Width / 2, (picCanvas.Size.Height / 4) * 3, picCanvas.Size.Height / 8, picCanvas.Size.Width / 4, 10);
Pen mypen = new Pen(Color.Black);
e.Graphics.DrawLine(mypen, (float)OuterPoints1.left_x, (float)OuterPoints1.left_y, (float)OuterPoints2.left_x, (float)OuterPoints2.left_y);
e.Graphics.DrawLine(mypen, (float)OuterPoints1.right_x, (float)OuterPoints1.right_y, (float)OuterPoints2.right_x, (float)OuterPoints2.right_y);
}
And there is your (hopefully) good looking cylinder!
Have a look at the result here[^].
I think this is all you need to get you started. Good luck!
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Thank you for your time! I've try to implement it, and it does get the left and right points! Very cool, and lotsa math there for me.
I wonder if you could help me more, on filling the cylinder. Here is my code: http://rapidshare.com/files/368251744/IsoCylinder.rar[^]. Just as you please and no rush, maybe if you have time again . Thank you.
|
|
|
|
|
Glad it helped you. I'll try and have a look at your code as soon as I can.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Ok I took some time to go through my code and try to give you some idea as how to get a filled cylinder. Sorry I didn't look at your code (guess I'm just too lazy hehe), but I think this one should help you.
I tried to do some cleanup, but be aware that my code is still not that polished.
I did some experiments on the track I first suggested you: using the angle to get the outer points for both ellipses. This simple version works just fine, except for rotation angles not in the range from -10 to +10 degrees you'll need to compensate (i.e. add an offset to the angles 0 and PI I'm using here to get the outer points):
private void FillEllipse(Graphics g, Color line_color, Color fill_color, double center_x, double center_y, double semi_minor, double semi_major, double angle)
{
Pen mypen = new Pen(line_color);
SolidBrush mybrush = new SolidBrush(fill_color);
double PI2 = Math.PI * 2;
double beta = -angle * (Math.PI / 180);
double sin_beta = Math.Sin(beta);
double cos_beta = Math.Cos(beta);
double increment = (Math.PI * 2) / (semi_major * 2);
double sin_alpha;
double cos_alpha;
int x;
int y;
List<Point> points = new List<Point>();
for (double alpha = 0; alpha < PI2; alpha += increment)
{
sin_alpha = Math.Sin(alpha);
cos_alpha = Math.Cos(alpha);
x = (int)(center_x + ((semi_major * cos_alpha * cos_beta) - (semi_minor * sin_alpha * sin_beta)));
y = (int)(center_y + ((semi_major * cos_alpha * sin_beta) + (semi_minor * sin_alpha * cos_beta)));
points.Add(new Point(x, y));
}
Point[] point_array = points.ToArray();
g.FillPolygon(mybrush, point_array);
g.DrawPolygon(mypen, point_array);
}
private void FillCylinder(Graphics g, double center_x, double center_y, double height, double semi_minor, double semi_major, double angle)
{
Pen mypen = new Pen(Color.Black);
SolidBrush mybrush = new SolidBrush(Color.LightGray);
double semi_height = height / 2;
double beta = -angle * (Math.PI / 180);
double sin_beta = Math.Sin(beta);
double cos_beta = Math.Cos(beta);
double sin_alpha = Math.Sin(Math.PI);
double cos_alpha = Math.Cos(Math.PI);
int left_x1 = (int)(center_x + ((semi_major * cos_alpha * cos_beta) - (semi_minor * sin_alpha * sin_beta)));
int left_y1 = (int)(center_y - semi_height + ((semi_major * cos_alpha * sin_beta) + (semi_minor * sin_alpha * cos_beta)));
int left_x2 = (int)(center_x + ((semi_major * cos_alpha * cos_beta) - (semi_minor * sin_alpha * sin_beta)));
int left_y2 = (int)(center_y + semi_height + ((semi_major * cos_alpha * sin_beta) + (semi_minor * sin_alpha * cos_beta)));
sin_alpha = Math.Sin(0);
cos_alpha = Math.Cos(0);
int right_x1 = (int)(center_x + ((semi_major * cos_alpha * cos_beta) - (semi_minor * sin_alpha * sin_beta)));
int right_y1 = (int)(center_y - semi_height + ((semi_major * cos_alpha * sin_beta) + (semi_minor * sin_alpha * cos_beta)));
int right_x2 = (int)(center_x + ((semi_major * cos_alpha * cos_beta) - (semi_minor * sin_alpha * sin_beta)));
int right_y2 = (int)(center_y + semi_height + ((semi_major * cos_alpha * sin_beta) + (semi_minor * sin_alpha * cos_beta)));
FillEllipse(g, Color.Black, Color.LightGray, center_x, center_y + semi_height, semi_minor, semi_major, angle);
Point p_left_1 = new Point(left_x1, left_y1);
Point p_right_1 = new Point(right_x1, right_y1);
Point p_left_2 = new Point(left_x2, left_y2);
Point p_right_2 = new Point(right_x2, right_y2);
Point[] mypoints = new Point[] { p_left_1, p_right_1, p_right_2, p_left_2 };
g.FillPolygon(mybrush, mypoints);
FillEllipse(g, Color.Black, Color.LightGray, center_x, center_y - semi_height, semi_minor, semi_major, angle);
g.DrawLine(mypen, left_x1, left_y1, left_x2, left_y2);
g.DrawLine(mypen, right_x1, right_y1, right_x2, right_y2);
}
private void picCanvas_Paint(object sender, PaintEventArgs e)
{
FillCylinder(e.Graphics, picCanvas.Size.Width / 2, picCanvas.Size.Height / 2, picCanvas.Size.Height / 2, picCanvas.Size.Height / 8, picCanvas.Size.Width / 4, 10);
}
See the result here[^].
Of course you can also choose to continute with the "brute force" approach I showed earlier for getting the outer points, which is ok for any rotation angle. In that case I suggest you calculate the points for both ellipses and store them in point arrays, so that you can also get the outer points. Then, you can proceed to drawing:
private class EllipseOuterXPoints
{
internal int left_x = int.MaxValue;
internal int left_y = int.MaxValue;
internal int right_x = int.MinValue;
internal int right_y = int.MinValue;
internal void CheckPoint(int x, int y)
{
if (x < left_x)
{
left_x = x;
left_y = y;
}
if (x > right_x)
{
right_x = x;
right_y = y;
}
}
}
private Point[] GetEllipsePoints(double center_x, double center_y, double semi_minor, double semi_major, double angle, EllipseOuterXPoints OuterPoints)
{
double PI2 = Math.PI * 2;
double major = semi_major * 2;
double increment = (Math.PI * 2) / major;
Point[] points = new Point[(int)major];
double beta = -angle * (Math.PI / 180);
double sin_beta = Math.Sin(beta);
double cos_beta = Math.Cos(beta);
double sin_alpha;
double cos_alpha;
int x;
int y;
int i = 0;
for (double alpha = 0; alpha < PI2; alpha += increment)
{
sin_alpha = Math.Sin(alpha);
cos_alpha = Math.Cos(alpha);
x = (int)(center_x + ((semi_major * cos_alpha * cos_beta) - (semi_minor * sin_alpha * sin_beta)));
y = (int)(center_y + ((semi_major * cos_alpha * sin_beta) + (semi_minor * sin_alpha * cos_beta)));
points[i++] = new Point(x, y);
OuterPoints.CheckPoint(x, y);
}
return points;
}
private void FillCylinder_BruteForce(Graphics g, double center_x, double center_y, double height, double semi_minor, double semi_major, double angle)
{
Pen mypen = new Pen(Color.Black);
SolidBrush mybrush = new SolidBrush(Color.LightGray);
double semi_height = height / 2;
EllipseOuterXPoints OuterPoints1 = new EllipseOuterXPoints();
EllipseOuterXPoints OuterPoints2 = new EllipseOuterXPoints();
Point[] points1 = GetEllipsePoints(center_x, center_y - semi_height, semi_minor, semi_major, angle, OuterPoints1);
Point[] points2 = GetEllipsePoints(center_x, center_y + semi_height, semi_minor, semi_major, angle, OuterPoints2);
g.FillPolygon(mybrush, points2);
g.DrawPolygon(mypen, points2);
Point p_left_1 = new Point(OuterPoints1.left_x, OuterPoints1.left_y);
Point p_right_1 = new Point(OuterPoints1.right_x, OuterPoints1.right_y);
Point p_left_2 = new Point(OuterPoints2.left_x, OuterPoints2.left_y);
Point p_right_2 = new Point(OuterPoints2.right_x, OuterPoints2.right_y);
Point[] mypoints = new Point[] { p_left_1, p_right_1, p_right_2, p_left_2 };
g.FillPolygon(mybrush, mypoints);
g.FillPolygon(mybrush, points1);
g.DrawPolygon(mypen, points1);
g.DrawLine(mypen, OuterPoints1.left_x, OuterPoints1.left_y, OuterPoints2.left_x, OuterPoints2.left_y);
g.DrawLine(mypen, OuterPoints1.right_x, OuterPoints1.right_y, OuterPoints2.right_x, OuterPoints2.right_y);
}
private void picCanvas_Paint(object sender, PaintEventArgs e)
{
FillCylinder_BruteForce(e.Graphics, picCanvas.Size.Width / 2, picCanvas.Size.Height / 2, picCanvas.Size.Height / 2, picCanvas.Size.Height / 8, picCanvas.Size.Width / 4, 45);
}
See the result here[^].
Well, this should give you enough meat to chew I hope. Enjoy!
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Thanks! I'm gonna try your code, tell you the truth though, I have no idea of the math whatsoever.
But I might be able to chew the meat slowly, maybe add some salt or recook it.
Thanks again for taking the time to help. Appreciate it.
|
|
|
|
|
My pleasure. Good luck!
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
IMHO you should consider this for an article - A1 stuff
I don't speak Idiot - please talk slowly and clearly
'This space for rent'
Driven to the arms of Heineken by the wife
|
|
|
|
|
Thanks Andy, really appreciated.
I will consider writing an article on this. Maybe when I'm on my holidays next month, then hopefully I'll get enough free time. If I don't overplay my PS3, that is hehe.
Now I "only" need to get good at writing articles... ARGH!
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Hi all,
Is there anyone could point out any way in bypassing a firewall via compression techniques? would appreciate if any available algorithm (java) is provided as well.
What i want is for the software to basically compress the files or sites in order to bypass the firewall instead of hiding the IP address. Is it possible?
Tried google but couldnt get the answer i m looking for.
Thanks
|
|
|
|
|
|
What is a good algorithm to calculate if a square is intersecting a rectangle?
I noticed in Windows forms the picture box Rectangle had an "intersect" function but I would like to program something on those lines with an algorithm instead.modified on Monday, March 8, 2010 7:52 PM
|
|
|
|
|
There is no PictureBox.Intersect; maybe you are confusing with Rectangle.Intersect?
are the rectangles always orthogonal (parallel to the axes)? (if so, use Rectangle.Interset)
or under an arbitrary but fixed angle? or a variable angle?
|
|
|
|
|
Luc Pattyn wrote: There is no PictureBox.Intersect; maybe you are confusing with Rectangle.Intersect?
Ah yes I confused my self that is what I meant, a rectangle intersection
|
|
|
|
|