Re: [Boost-users] [Polygon] Test among 3 libraries

Subject: Re: [Boost-users] [Polygon] Test among 3 libraries
From: Angus Johnson (angus_at_[hidden])
Date: 2010-09-09 20:42:12

> Just a C++ style pointer, we have what we call resource acquisition is initialization (RAII) policy where we initialize all variables at the time they are declared rather than deferring that to later.  The rationale for this is that it avoids bugs introduced later when a variable is attempted to be used between where it was declared and where it is initialized resulting in undefined behavior and different behavior on different platforms/compiler optimization flags.

Thanks. I'll try and remember that. Delphi enforces local variable 
declarations before any logical operations can be performed (IIRC to 
allow a one pass compile), so I'm going to have to break a long standing 
habit.

>   TPolygon result; //it would be better if the TPolygon constructor accepted the size

As you can see I'm still coming to grips with the fundamentals of C++. I 
forgot that the std vector's constructor accepted a size parameter.

>   y = y + (j % 2)*2 -1; //squiggles right twices as fast as it squiggles up

That was so I could see it was really doing what I expected, otherwise 
it just looked like a fat blurry line :).

> This will be the worst case input and have expected runtime complexity of O(n^2) using a linked list as the sweepline data structure while an optimal Vatti using a tree would have O(n log n) complexity and empirical scale factor of about O(n^1.05).

I've given my data structure a little more thought  and believe it isn't 
a simple link-list structure as I stated earlier. The main linked list, 
the  active edge list (AEL) contains a list of active edges which also 
link to their adjacent edges in an edge bound (LML). I imagine that this 
is the tree structure you been mentioning.