

Seriously, it wasn't clear what your problem was. Do you just want to draw the tree upside down on the screen? If so, for a display of height H, substitute (H  y) for every y coordinate to flip the tree.





Sorry. I want to know if is something like treeview but where the root is on the bottom and everything goes up.





Oh, I thought you might be interested in an algorithm, since this is the Algorithms forum and your title was "Tree algo". Since you're looking for a suggestion on a graphics package, you might want to post your question in the Lounge.





Sorry. I'll try there. Thanks for your help.





Hello,
I have some 3d points (not self intersecting). the shape of the points is looking like / (forward slash) from profile, It is actually a slice of a 3d object, cut with a rotated plane.
I want to calculate the area of 3d points and its centre. For 2d case, i use the following
http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/[^]
but, how can i extend the 2d case to 3d for area and its centre?
Thanks in advance.
Bekir.





If you could rotate the points so they all have the same Z coordinate, you could then ignore the Z coordinate and apply the 2D formulas for the area and centroid.
Rotation will not change the area. Apply the reverse rotation to the calculated centroid to get the centroid of the original 3D points.





Thank you,
i will try that and i think it will solve the problem but it will create a bit of overhead.
Bekir.





What you want is a 2D coordinate system in the plane of intersection, then you can use your equation for area.
Assume that your original points are represented as vectors {Vk} from some origin O (this is your original 3D coordinate system).
As you have the equation of the plane, choose one point on it as the new origin Op, and choose two orthogonal unit vectors (U1, U2) that lie in the plane as the new axes. (i.e. choose two orthogonal vectors orthogonal to the normal of the plane)
Then in your new coordinate system, the 2D coordinates of the point Vk are: ( (VkOp).U1, (VkOp).U2 )
i.e. you simply project the 3D vector from your new origin onto your new axes.
Note  this includes Alan's solution, the vectors U1 and U2 would be rows of his rotation matrix. It's just a different way of looking at things.
Peter "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."





Does anyone have a stable Quicksort? I have looked at many, and they all seem to have a problem in that they swap elements that are not equal to the pivot element before knowing whether the swapped elements match any other element. see the following example:
014447222563 where '3' is the pivot You will swap the '4's and '2's leaving:
012227444563 and the final swap:
012223444567 however, the swaps of the '2's and '4's (done one at a time from the outside) put them out of order before you even get to see that they are duplicates.
The only way I know of is to supply an additional key element in the record (sorted along with the key) which contains the input record number of the key. This is time expensive, rebuilding the records just to sort them, only to unbuild them when the sort completes. It is easily done, however, with indirect sorting, where the indirect array is an array of structures containing both the pointer to the actual record and also the input record number. Swapping the indirect pointers as records keeps the original record number with its record definition where it can be checked when an equal comparison is encountered. Of course, indirect sorting is inefficient when huge arrays (> 2GB)are involved because the underlying data remains scattered in memory, and paging in huge blocks of memory to compare a small record is a terrible waste.
Dave Augustine





If you are sorting numbers then consider using a bucket sort which is stable. It's also faster than QuickSort in some circumstances.
Greetings  Gajatko Portable.NET is part of DotGNU, a project to build a complete Free Software replacement for .NET  a system that truly belongs to the developers.





gajatko,
Thank you for the reply, but I was specifically interested in a Stable Quicksort.
Off topic, I see that you answered this over 3 hours ago. I checked the forums no more than 5 minutes ago and this message was not there, I got your reply on my Email and answered it from there. Guess I'll have to tell Chris.
Dave.





Have a look at STL's stable_sort[^]. Perhaps this is what you're after.
Steve





Steve,
Thank you for the reference. Turns out that StableSort is a merge sort. Of course it is stable. You are always comparing elements before you select one or the other to output. My contention, having read many of the Articles on quicksort and seen their algorithms, is that they attempt to be stable once the pivot and an element is compared, but totally ignore whatever has not been seen (between i and j) when swapping i and j elements to satisfy the sort conditions i < pivot, j >= pivot. Note that you have only compared i and pivot and j and pivot, (by the algorithm, i < j), but you know nothing about what lies between i and j. Swapping these two elements may cause an unstable sort as I demonstrated in my initial post.
My attempt is to build a stable quicksort which should be faster, and not require the additional mergesort memory (see The Knuth reference, last paragraph on page 161 (Volume 3, copyright 1973). I would quote it, but cannot due to copyright restriction.
Dave.





My attempt is to build a stable quicksort which should be faster, and not require the additional mergesort memory (see The Knuth reference, last paragraph on page 161 (Volume 3, copyright 1973). I would quote it, but cannot due to copyright restriction.
I'm unaware of any mathematical restriction on the ability to perform a stable sort without requiring either extra time or extra storage (insertion and selection sorts, e.g., require no extra storage, but a lot of extra time) but I am also unaware of any implementations that require neither extra time nor storage. That having been said, in many applications it is better to physically move around pointers than to move around data, and if one is shuffling pointers the extra storage isn't really a problem.
Incidentally, I've invented a sorting algorithm I've never seen elsewhere which performs slightly fewer than n*lg(n) comparisons (as does a good QuickSort implementation, btw) but yields the results in order (the first item will be made available after n1 comparisons; the next item will be available after lg(n) comparisons, etc. The storage and time overhead for bookkeeping (about 16 bytes/element on a 32bit machine, and sublogarithmic time but with a hefty constant) probably make the sort impractical, but having the sort yield the results in order is cute.





supercat9,
Thank you for the reply. I am aware that it will take more time or storage to stablize the sort. The question is how much more. I am already running into conditions that have sometimes forced me to go to an external sort, not enough virtual memory available. Especially under full memory condition, you do not want to swap by exchanging pointers, you will be paged to death the entire time. At least by scanning up or down in memory for adjacent records, you will stay in a small number of pages (3 to 6) the records in their original positions may result in a page fetch for each record.
If you include a tiebreaker element in the keys, it takes that extra room in each record, space that always must be swapped during exchanges, and sometimes must compared when the rest of the key matches. If the original record has another field that can be used as a tiebreaker, then the extra space and the exchange time already exist, and it is only a matter of comparing the tiebreaker if the rest of the key matches, but, this requires having to specify the parameters of the tiebreaker so the compare can be done and the type of element may not be the same as the original key. All of this is doable, just a matter of what is the "best".
Dave.





can someone tell me the O() of this:
struct pivot {
int l,r;
};
function partition( array, left, right ) {
pivot.l = pivot.r = left
for i = left to right
{
if (array[i] >= pivot.l)
pivot.r += 1
else
swap(pivot,i)
}
return pivot.l
}
swap_r (range, index) {
int t=range.r
while(range.l<=t)
swap_i(t,index)
}
swap_i (index1, index2) {
}
function quicksort(array) {
int p = partition(array,0,length1)
quicksort(array,0,p)
quicksort(array,p+1,length1)
}
It is psuedocode, but you get the idea. I think it's O(n^{2}Log(n)) but I'm not sure. If you could figure out how to put 1 element in front of x elements better, it'd be what you want.
modified on Friday, April 3, 2009 8:29 PM





What's up with the copyright mindvirus? from the copy right act of 1976:
In no case does copyright protection for an original work of authorship
extend to any idea, procedure, process, system, method of operation,
concept, principle, or discovery, regardless of the form in which
it is described, explained, illustrated, or embodied in such work.





bulg,
Thank you for the replies. I would respond to your second response (I got an email notification), but it appears that you deleted the post. Do you have an actual algorithm for the "lazy quick sort"? Seems interesting.
For your algorithm in this post, it seems a bit strange and incomplete or inaccurate. How can you swap an integer and a structure of two integers swap(pivot,i) ?
As far as copyrights go , sure it is 25 years old, but has it been renewed? Is it still active? What constitutes "fair use"? This has been argued in the courts many times. I do not have deep pockets so I just refuse to quote an author. I did discuss the point he made about the requirement for the extra space required for the stable quicksort, a size equal to the original size of the piece being partitioned. Similar to a merge sort, but with the terrible disadvantage that merge sort put the elements in the correct sequence, stable quicksort only copies them in an unordered state to two buffers (less than and greater than the pivot) and requires that the two partitions still need to be sorted. What a waste.
Dave.





Hey Dave,
I'm gonna answer the copyright question first: You are protected & free to write or say anything you want *about* Knuth's books, including the contents, as long as you don't do it for profit. If you use it authoritatively, you should also say, "as Knuth wrote in ...", aka, cite it. Otherwise, a million kids across the country turning in book reports with "at least 4 quotes from the book" would be copyright villains.
Here's my lazy quick sort again, this time with better annotation. Still pseudocode, though:struct pivot {
int l,r;
};
function partition( array, left, right ) {
pivot.l = pivot.r = left
for i = left to right
{
if (array[i] >= pivot.l)
pivot.r += 1
else
swap_r(pivot,i)
}
return pivot.l
}
swap_r (range, index) {
int t=range.r
while(range.l<=t)
swap_i(t,index)
}
swap_i (index1, index2) {
}
function quicksort(array) {
int p = partition(array,0,length1)
quicksort(array,0,p)
quicksort(array,p+1,length1)
}
This works on paper. I used the values0 1 4 4 5 4 2 4 2 3 5 3 7 6 7 4 when I did it by hand.
If you wanted to make it like I envisioned lazy quick sort, then you could employ another range for swapping, instead of swapping at the first index that is < pivot.l . I am not convinced this would be faster... but I don't really have time to try it. If you do, please let me know!!
Ryan





Ryan,
Thank you for the reply. swap_r won't work. Here is how to fix it. Move the indexed value out of the way to a temporary location. Now instead of swapping each element in the range with the indexed value (this is what won't work, you overlay all of the prior values on top of each other), just move the range in reverse (as you have done by decrementing t), finally opening space at the front of the range into which you can put the saved original indexed value. Instead of picking up two values and saving two values (a swap), you are just picking up a single value and saving the single value to a new location (a move). Half of the work. Of course, you have to decrement both of the move indexes as you move the data (the fix for the overlay in your original version).
Just about done with my original quicksort. I have found a MASM 8 bug along the way. MASM 8 will not accept:
movd qword ptr [base+index],xmm0 or movd xmm0,qword ptr [base+index] . The AMD manual specifically says movd works for both XMM and MMX as long as you specify a mem64 location. Not really a great problem, I just used a movq instead. I got into this because I just compared two extended floating values via the FPU and needed to swap them and tried to use MMX registers, however, the execution did not work (assembled without error, executed with no exceptions, but the array was not sorted). Seems that MMX and FPU share the same registers and control flags, and I guess you must finit the FPU before trying to use MMX. This is too time expensive, so I was just using XMM which is an independent register set. The only problem is that the code now depends on XMM instead of only MMX (my code was using an alignment specification of 8 to flag MMX OK, and an alignment of 16 to flag XMM OK. I may have to implement one more parameter which will just be used to enable MMX and/or XMM independently of the data alignment.
Dave.





(Let's just hope the description is good enough)
Let's say I have a cylinder, and a series of lines (spokes) that go trou it in circular fashion. lines are pointing from the cylinder surface to the axis of the cylinder.
In my case, the lines "direction" can be either going towards the center of the cylinder or outside.
Is there a way to know if the direction of the vector (IJK) is pointing towards the interior or the exterior ?
I could possibly construct 2 points with the vector and its reverse and see which point is closer to the center and use that direction.
Is there a better "math" solution ?
Thanks
This signature was proudly tested on animals.





I don't see what the problem could be. If you have a cylinder with radius R and a point P, all it takes is to calculate the distance from P to the main axis of your cylinder; if that distance is less than R, then you are inside the cylinder (assuming its height is infinite).
Luc Pattyn [Forum Guidelines] [My Articles]
 before you ask a question here, search CodeProject, then Google  the quality and detail of your question reflects on the effectiveness of the help you are likely to get  use the code block button (PRE tags) to preserve formatting when showing multiline code snippets





The cylinder description was not a good idea to describe the problem. I don't have a radius.
(will edit the original post)
This signature was proudly tested on animals.





OK, if in three dimensional space you have a surface described by f(x,y,z)=0 then all points P(X,Y,Z) that make f(X,Y,Z)>0 will lie on one side, and those making f<0 will lie on the other side. So check one point to see what you choose to call the inside, and you will know for all points.
Luc Pattyn [Forum Guidelines] [My Articles]
 before you ask a question here, search CodeProject, then Google  the quality and detail of your question reflects on the effectiveness of the help you are likely to get  use the code block button (PRE tags) to preserve formatting when showing multiline code snippets





My description is not good enough, it's "too" specific for my particular "problem", With an actual cylinder, and vector, I can resolve it.
I will try to have a better description.
Thanks.
This signature was proudly tested on animals.




