I believe this to be an ACM question from either 96' or 97'
bool nonzerodigit(constunsigned int& n, unsigned int& result)
if (n > 100000) returnfalse;
unsignedint result = 1;
for (unsignedint i = 1; i <= n; ++i)
unsignedint f = i;
while (0 == (f % 5))
f /= 5;
result /= 2;
result = (result % 100000) * f;
result %= 10;
100000 is an upper sanity bound and also a quantizer for the minimum required 6 "least significant" digits.
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.
I'm putting together a Silverlight 2 demo application. It is going to be a simple 2-D tank game where you can use the arrow keys to rotate and move the tank. The tank can point in any direction (360 possible directions, right?). I've written the code to rotate the tank, but I'm not sure where to begin regarding moving the tank. How can I take the angle of the tank (say, 156 degrees for example) and use that to determine the next x,y position of the tank when it moves forward?
I'm sure there must be a simple equation for this, but I don't know what it would be called or even how to google this problem.
The only things you need to remember are:
> Math.Sin and Math.Cos take the angle argument in radians not degrees.
> Sin and Cos return double precision numbers: which may round to 0 or 1 if you are using integer positions and therefore the tank will not move as you want.
i have set of 2D points and i want to offset with a given distance (like offset command in AutoCAD)
i do not know how to deal with corners. i have searched on Internet, there are advanced methods like straight skeletons etc. but my polyline is not self crossing and no holes in it.
At the end, it is a translation however it must be implemented with respect to the normals, as far as i read through if it is a parametric curve then it is rather complicated. If you like to see how much it can further get complicated, you can have a look at the link below.
There is no simple solution to this problem, the best known general solution, is to create capsules between consecutive point pairs of your polyline where the capsule width is the offset, then union the capsule outlines. The capsule may be centered around the edge or it may be biased towards one side of the edge it is really up to the end requirement. For the union operation use something like Alan Murta's Generic Polygon Clipper library.
If you know your polyline is enclosed and represents a convex polygon, then simply calculate the centroid, then offset each edge by the product of the desired offset amount and the vector composed of the mid-point of the edge at hand minus the centroid.
A simple example can be found here:
im trying to convert Quaternion to Euler but i dont have appropriate code, i searched on lots of sites but their converting code do not match with converting back, mean, if i convert from Quaternion to Euler then i convert back the result value to Quaternion, i got different output, here is my code
Doing a quick scan they look like the common formulas out there.
Be aware, the formulas depend on the order you apply the rotations e.g. XYZ, ZXY, YZX, ...
ToEuler may be derived for one order and ToEulerA another.
The idea that I can be presented with a problem, set out to logically solve it with the tools at hand, and wind up with a program that could not be legally used because someone else followed the same logical steps some years ago and filed for a patent on it is horrifying.
- John Carmack
unfortunately i got code from that site, that site converter have some incorrect conversion, eg. at the end of page you will find a java converter, write real = 1, i = 1, and output will be 116.56505117707799, now put this 116.56505117707799 in Euler to Quaternion converter on another page and now result is completely different, why ?
Care to give us a clue to why so we know better what to suggest?
Fair enough, let me explain it further
I need to draw N rectangles side by side (their centers lying on a line or trajectory).
Works like this, user gives two points (left and right) then i need to draw a series of rectangles from the first point to the second with the rectangles centers lying on the line.
i figured for that i need to calculate the points that will lie on that line, hence the requirement for an algorithm that will give me the points that will lie on a line(x1,y1,x2,y2)
Secondly user will provide the color of the first rectangle and the last and i need to fill the rest of the rects with the gradient color, hence the requirement for a gradient algorithm
Here is a sample image (it uses sine wave i think instead of a line) Sample[^]
And lastly thanks for your valuable time
C++ where friends have access to your private members !
Well, this might be a place to get started. Bresenham's algorithm[^] certainly picks pixels to draw straight lines and some other curves. You might also check some of the 3D drawing class libraries, like VRML or the library that originated at SGI, as they often implement a process they call "extrude" where they sweep a shape through space that follows a curve, a cylinder is an example of extruding a circle along a straight line. I don't think they use pixels generally but you might get some ideas.
If you don't have the data, you're just another a**hole with an opinion.
For example, used for video conference or video capture.
Oh, probably some DCT (discrete cosine transform) derivative like H.261. It's an ITU standard suited for two-way communication over ISDN. It supports fairly high data rates as well (i.e. multiples of 64Kbit/sec).
All of you must have herd of Best fit also, but i would give a brief , just in case.
Say i have slots of 50 KB, and there are some codes of different sizes say [10KB,11KB,23KB,34KB,2KB,28KB,31KB,9KB]
Now i have to fit all the elements in the different 50KB Slots such that i make the optimum use of the space. Like:
31+9+10 = 50KB --- 1st slot.
11+34 = 45KB --- 2nd slot...
The best fit is a rather lengthy algorithm to implement. I would try sorting in descending order before trying to assign bins. Then you'll have to loop through all the bins and assign as appropriate. You also have the possibility of increasing the numbers of bins. Assign elements to the bin that is most full that can accomodate your element. At this point you can increase the number of bins if you like. Continue in this manner....
This is a standard Multiple Knapsack[^] problem, there are lots of references on the web and a variety of solution trchniques with different ranges of applicability. One general code (fortran though, not c#) is TOMS ALgortihm 632[^]
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
Best Fit problem as applies to computer science involves variable size storage blocks as well as variable size data to be put into the storage blocks notably without combining data chunks before storage (see Knuth, Vol. I).
What you have described is the timeworn knapsack problem, aka circus train problem. Simply stated: What is the packaging arrangement of a fixed set of variably sized objects into uniform size containers that fills the fewest containers?
Problem size will be a considerable obstacle here. Consider unfavorable size distributions in your set of variables that yield many size combinations to be generated, tested, and compared with the previous-best combination. And how many possible combinations of these combinations are possible?
Anyway, I think you should postulate some modest inputs and do some pencil scratch before hunting down code or algorithm.
An ounce of Clever is worth a pound of Experience.
I want to implement an algorithm in which I need to put some nodes(points)in an environment and segments which connect theses nodes in some way to each other. The environment is occupied with some obstacles(simple shapes or polygons)! How can I determine when collision exists between nodes or segments and the environment's obstacles! Thanks so much in advance.
The solution requires the use of a spatial container. You place all your environment objects into the container, then as you process your dynamic objects you query them against the spatial container. The result should provide back the intersecting objects. Depending on the dimensionality of the objects you could either use a quad-tree or an oc-tree.
General process is that you perform a "broad phase" sweep to determine potential collision pairs based on something easy - bounding circles or boxes, and then move onto a "narrow phase" to check for exact collisions.
You might want to read up on minkowski sums - using these in an embedded system at the moment for mining machine anti-collision.
Non-Numerics R Us, use bitmaps and the GDI Bitblt() function.
Two congruent bitmaps A and B each contain some 'on' bits and some 'off' bits and we wish to determine if any 'on' bits occupy the same coord location in both maps.
1. A AND B yields a bitmap with 'on' bits only where the 'on' bits of A and B collided.
2. Row-wise OR the first half of C with its second half, then the first one fourth with the second one forth, etc. until all rows are ORed to a single row.
3. Repeat step 2, except column-wise for the first row only until ORed to a single bit.
If the upper-left bit is 'on', then a collision occurred.
This method always answers yes or no, but never how many or where. You might ask what use is that?
I have used blitter and bitmaps in (unsuccessful) attempt to simulate fluid flow through a maze by pumping bits into the entrance and sumping them out the exit. My bits just wouldn't flow and I need a better notion of 'boolean soup'.
I have also used this method to successfully determine if constrained random walks in integer 3-space cross one another.
This method boasts a strictly linear increase in execution time as number of objects to test increases. This feature makes it useful for very large numbers of objects like the hundreds of thousands of bits bouncing around in my mazes, keeping track of which are moving N, E, S, W and colliding with each other or with maze walls.
An ounce of Clever is worth a pound of Experience.