# Aryabhatta

Member

60

186 Neutral

• Rank
Member
1. ## Polygon Triangulation

Quote:Original post by JeffLander Google Delaunay Triangulation. That is what you want. That is incorrect. Delaunay triangulation is not related to what the poster is asking. Look at the following site: http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html The references mentioned on that page might be useful.
2. ## Need help with physics equation

Quote:Original post by ordered_disorder This isn't homework, this is just a questiont that I came up with in the spare time, I will take your word for it. So, you have worked on the gravitation pull problem and want us to solve a probably equivalent but simpler problem.. Let V(t) be the velocity of B as a function of time (you have given the initial values) If x(t) is the distance between A and B, we have that dx/dt = V_B(t) + V_A (where V_A is the velocity of A, taking the proper sign into account) We have been given that dV_B/dt = -x/5 Thus d^2x/dt^2 = -x/5 = -xw^2 (say) (w^2 = 1/5 so w is 1/sqrt(5)) This is a second order differential equation whose solution is given by a linear combination of sin(wt) and cos(wt) of the form Acos(wt) + Bsin(wt). Fill in the initial values and get the result.
3. ## Need help with physics equation

This looks like homework. Please read the FAQ. The FAQ lists sites where you might get help with homework... I don't know why the FAQ lists such homework sites!
4. ## Odd Discrete Math Problem

Quote:Original post by Steve132 I have a COMPLETE digraph of N nodes, with N^2 weights W. I want to calculate the minimum path required to visit all nodes exactly once with the minimum cost. You have a COMPLETE digraph, which means there is a directed edge from any node i to any other node j. Also, you say all the weights are W, I don't see what your problem is! Just pick any permutation of the nodes and you have a minimum cost path hitting all nodes exactly once. If the weights could be different for different edges, you are probably looking at the "Asymmetric Travelling Salesman Problem". The Minimum Spanning Tree won't work.
5. ## Optimization help?

Quote:Original post by cypherx I summon you gods of optimizing to help me speed up my code. gprof shows the top 3 CPU drains to be: std::_Rb_tree<template nonsense>::lower_bound(string const&) 18% std::_Rb_tree<template nonsense>::find(string const&) 15% ptr<Expr>::release() 10% <snip> Is there any way I can cut down the CPU usage? <snip> As others have pointed out, we need to know exactly how you are using these structures. Other have answered most of your questions, so I will take the liberty to possibly go Off topic. What I am saying might not be relevant to you, but it is relevant in general to profiling and analysis of profile data for optimization. For instance consider the below sort function: Class X; Sort(X *array, size_t n) { int i; int j; for (i = 0 ; i < n; i++) { for (j = i+1 ; j < n; j ++) { if ( array[j] < array) { Swap(array,i,j); //Swap elements i and j of the array. } } } } When you profile this, it might say that the Swap function is taking 50% CPU time. It might be that Swap is really inefficient, but suppose it is not too bad. Can you think of a better optimization than trying to make Swap more efficient? The point I am trying to make is, even thought the profiling points to a certain function being the bottleneck, the problem could lie else, as in the above Sort function.
6. ## spiral cube edge tracking

It would probably be more efficient if you just looped through, calculating the next XY values from the current XY values. We could maintain how much to increment the X values and the Y values by in order to get to the next cube... For instance look at the following code: (will mostly have mistakes.. dont use verbatim) // MxN rectangle, M width and N height // Traversed in a AntiClockWise spiral fashion, starting from bottom left. AntiClockWiseSpiral(int m, int n) { int X_inc = 1; // The Amount to increment the X value int Y_inc = -1; // The Amount to increment the Y value; int CurX = 0; // Current X value; int CurY = 0; // Current Y value; int X_tot = 0; // Amount of horiz distance covered in current horiz walk. int Y_tot = 0; int X_step = m; //Current max size of horizontal walk int Y_step =n; int i; bool flagIncX = true; // Increment the X value or the value? for (i = 0 ; i < m*n , i++) { RenderVoxel(curX, CurY); if (flagIncX){ X_tot++; }else{ Y_tot++; } if (X_tot >= X_step) // Need to starting going vertically now. { Y_inc = -Y_inc; // Up, Down, Up, Down ... X_tot = 0; flagIncX = false; X_step--; } if (Y_tot >= Y_step) //Need to start moving horizontally now. { X_inc = -X_inc; //Right, Left, Right, Left... Y_tot = 0; flagIncX = true; Y_Step--; } if (flagIncX) { curX += X_inc; }else{ curY += Y_inc; } } }
7. ## Beginner Math and Physics Forum

Quote:Original post by Oluseyi Besides, shouldn't this thread be in Comments, Suggestions and Ideas? You think so? How many of the readers of Math & Physics forums visit that one? I think it makes sense to have this post in this forum. Anyway, apologies if such a thing is mentioned in the FAQ.
8. ## Bad Yellow font in Forum FAQ

This forum faq has some text which is in yellow and is pretty impossible to read over the grey background. Moderators, please do something!
9. ## Beginner Math and Physics Forum

Of the little time I have been here, I see that many posts in this section are usually questions which can be easily answered using basic high school math/physics or a quick web search. Usually these topics get bumped up quite easily, pushing the other topics (which might be more difficult to answer) down, and those might go unanswered for days. Is it time we need a new forum for the beginner version of math and physics? I am ok with the current situation... but what are your thoughts?
10. ## Concave Faces - Detecting and Eliminating

This is a well studied problem. The following assumes that the polygon is simple, i.e two edges dont intesect, except possibly at end points (the region formed by the polygonal does not have holes). If N is not large then there is a simple O(N^2) algorithm which you can use. Step 1) Find a diagonal of the polygon P. Step 2) Split the bigger polygon along the diagonal in two polygons P1 and P2. Step 3) Recursively triangulate P1 and P2. In the end you have a triangulation of P. How do we do Step 1? Find the leftmost vertex a of P. Take the two neighbours b and c of P. If the edge bc is within the polygon P (check intersection with other edges), you have found a diagonal. Otherwise pick a point (among the vertices of P) in the triangle abc which is farthest from bc. Say that point is d. the segment ad is a diagonal. Step 1 takes O(N). So the whole algorithm is O(N^2). There are methods which do this in O(NlogN) and even O(NloglogN). A method which is O(NlogN) is called Monotone Triangulation, which a google search should reveal algorithms for. If the polygon is simple you can find its convex hull in O(N log N) time. If the convex hull has some vertices missing then it is not convex. Otherwise it is convex. (havent tried proving this, but seems that it should be true) The above algorithms supposedly can be extended to polygons with holes. Hope that helps.
11. ## Returning a de-referenced NULL

Quote:Original post by SiCrane There's no reason to do something like that in the first place. If you're going to poison a function like that then why bother to even define it? Just leave out the definition and you can detect at link time that the function is unimplemented and not have to deal with the landmine at runtime. Unless we know the reason why the author put that in, we cannot claim that (s)he is a bad programmer. I don't think it is fair to the author to jump to such a conclusion based on one such snippet.
12. ## Returning a de-referenced NULL

Quote:Original post by Oluseyi Quote:Original post by Aryabhatta Considering that this is still verion 0.1 and is probably still in production... ...one should stay away from versions 0.2 through 2.4? Bad programmers write bad code. That's some bad code. There's bound to be more. LOL :-) I never said that the code was good (how in the world did you deduce that?). Anyway, if the author knows what he is doing and is probably going to change the code soon, you can say that the code is bad, but not that the author is a bad programmer.
13. ## Random Numbers

Quote:Original post by iMalc Quote:Original post by Aryabhatta <snip> Though i admit, your code needs more analysis to claim that this one is not a good one :-)... I think what IMalc wanted to refer to is a Linear Congruential Generator You unfortunately don't know what you're talking about. I didn't just pull this out of thin air. This is a standard implementation of a random number generator, taken from a common runtime library. Search for the above two prime numbers on google and you'll most likely get tons of search results with variants of this prng. The upper 16 bits are far more random than the lower 16. I know that this is a Linear congruential generator. Whoa! Slow down there pal...Sorry If I offended you. I didn't mean to. I did say your code needs more analysis before anyone can claim it is a bad one! What I stated was my opinion.. Hence the words "I think". Upon rereading the chapter in Knuth, in LCG's the higher order bits are more random than the lower order bits if the modulus equals the word size, which is true in this case. So taking the higher order 16 bits is right.. but this RNG is pretty bad nonetheless. [Edited by - Aryabhatta on December 19, 2005 3:52:49 PM]
14. ## Urgent Question

Try reading this link Journey into the third dimension . Might help convince you that 3D is good!
15. ## What am I un-aware of?

using C++ is like driving a stick shift. C#, Java are like automatic. :-) If your main goal is to get to the destination, you would prefer to use the fastest/safest vehicle... Many people who like to ship products (and make money in the process) hate C++. Bad programming/understanding of C++ can lead to hours of time wasted tracking and fixing bugs which could have been saved by using C# or Java or whatever... Some people just drive stick shifts for the fun of it. Some people use C++ for the same reason.