Re: [AD] Remove the P3D code please!

[Jason Wilkins <fenix@xxxxxxxxxx>]

On Tue, 20 Feb 2001, Bertrand Coconnier wrote:

> Jason Wilkins wrote :
> > It does not sort (at least, I don't
> > think it does), it puts the segments in the correct position.  This is a
> > searching problem, not a sorting problem.
> 
> Yep ! You are right.

After thinking about it, I realized that its actually difficult sometimes
to determine whenter you are searching or sorting because they are two
sides of the same coin.  It is indeed searching for the right spot to put
something, but the result is a sorted list of line segments.  This is the
definition of an insertion sort.  (pick an item, search for the spot to
put it, _insert_ it there, repeat until no more items).  So, I'm both
right and wrong at the same time.  Thats the best way to be wrong ^_^

I still have not looked at the code, but the trick to speeding up an
insertion sort would seem to be to speed up the speed of your
search.  I would imagine that since P3D is building a line segment list,
that this list is always sorted.  So, the first thing to check is to make
sure it is using a binary search, or a fast hash, and not a linear search.

If memory could be spared, it might even be possible to create a huge 2D
grid of small line segment structures the size of the screen, or some
fraction of screen size (say, 1/8th) and do a weird 2 dimensional radix
sort.  To give an example, you would divide the x coord by 8 (shift it 3 
to the left if you prefer), and that tells you which bucket line
segments near it are.  Be kind to that idea, its kinda off the
cuff.  There are probably millions of problems, I can already think of
them...