8 using namespace numeric;
16 n(P.length()), m(Q.length()),
23 : P(that.P), Q(that.Q),
24 n(that.P.length()), m(that.Q.length()),
26 _components(that._components)
38 tbb::static_partitioner sp;
39 tbb::parallel_for(0,
n-1, [&] (
int i)
44 for(
int j=0; j < (
m-1); ++j)
51 calculateFreeSpaceSegment<accurate_float>(
56 calculateFreeSpaceSegment<accurate_float>(
68 for(
int j=0; j < (
m-1); ++j)
72 calculateFreeSpaceSegment<accurate_float>(
84 for(
int i=0; i < (
n-1); ++i)
88 calculateFreeSpaceSegment<accurate_float>(
99 tbb::parallel_for (0,
n - 1, [&] (
int i)
101 for (
int j = 0; j <= (
m - 1); ++j) {
104 (j < (
m-1)) ? &cl.
L :
nullptr,
105 (i < (
n-1)) ? &cl.
B :
nullptr,
106 (j>0) ? &
cell(i, j - 1).L :
nullptr,
107 (i>0) ? &
cell(i - 1, j).B :
nullptr);
115 for(i=0; i < (
n-1); ++i)
117 for(j=0; j < (
m-1); ++j)
152 calculateEllipseBoundaries<accurate_float>(
153 P[i],
P[i+1],
Q[j],
Q[j+1],
163 calculateEllipseBoundaries<accurate_float>(
164 Q[j],
Q[j+1],
P[i],
P[i+1],
207 return (s1.x()-s2.x())*(t1.y()-t2.y()) - (s1.y()-s2.y())*(t1.x()-t2.x());
219 std::list<Interval> result;
221 bool inside = (L.
lower()==0.0);
222 if (inside) result.push_back(L);
224 for(
int j=0; j <
m-1; ++j)
232 else if (L.
lower() > 0.0) {
233 result.push_back(L + (
double)j);
234 inside = (L.
upper() >= 1.0) && (L2.
lower()==0.0);
237 Q_ASSERT(L.
lower()==0.0);
238 result.back().upper() = L.
upper() + j;
239 inside = (L.
upper() >= 1.0) && (L2.
lower()==0.0);
255 bool fix = (N && (N->
lower()==0.0))
256 || (E && (E->
lower()==0.0))
257 || (S && (S->
upper()==1.0))
258 || (W && (W->
upper()==1.0));
273 if (W && (std::isnan(W->
upper()) || (W->
upper()!=1.0))) {
280 template<
typename Float>
298 lambda[0]=lambda[1] = NAN;
300 A = q2x*(p1y-q1y) + q1x*(q2y-p1y) + p1x*(q1y-q2y);
301 B = euclidean_distance_sq<Float>(q1,q2);
302 D = (q2y-q1y)*(p2x-p1x) - (p2y-p1y)*(q2x-q1x);
307 Float lambda0 = (A - epsilon*
sqrt(B)) / D;
308 Float lambda1 = (A + epsilon*
sqrt(B)) / D;
310 if (lambda0 > lambda1)
314 if ((lambda0<0.0) || (lambda0>1.0))
316 if ((lambda1<0.0) || (lambda1>1.0))
319 if (std::isnan(lambda0) && std::isnan(lambda1))
return;
322 Float E8 = (p2x-p1x)*(q2x-q1x) + (p2y-p1y)*(q2y-q1y);
323 Float E9 = (q2x-q1x)*(p1x-q1x) + (q2y-q1y)*(p1y-q1y);
325 Float mu0 = (lambda0*E8+E9)/B;
326 Float mu1 = (lambda1*E8+E9)/B;
329 if ((mu0>=0.0) && (mu0<=1.0))
330 lambda[0] = (
double)lambda0;
332 if ((mu1>=0.0) && (mu1<=1.0))
333 lambda[1] = (
double)lambda1;
void swap(gpuword **A, gpuword **B)
static const QRectF UNIT_RECT
the unit rectangle [0,1]x[0,1]
bool cellFull(int i, int j) const
test if a cell is completely covered by the free-space area
static void fixBorderCase(data::Interval *N, data::Interval *E, data::Interval *S, data::Interval *W)
fix border case at the joint of four intervals
QRectF segmentBounds(int i, int j)
Interval & setLower(double value)
update lower bound
Interval H
horizontal interval
global definitions for all algorithms.
double determinant(int i, int j) const
void calculateFreeSpace(double epsilon)
calculate all free space intervals
static const double DET_MINIMUM
minimum determinant to avoid roundoff errors
Float sqrt(const Float &x)
square-root function template for floating point types
data::IntervalPair bounds
bool cellEmptyIntervals(int i, int j) const
test if a cell is empty
Interval V
vertical interval
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
std::list< data::Interval > collectFreeVerticalIntervals(int i) const
traverse one column of the free-space and find all connected intervals. This method is needed by the ...
double min(double a, double b)
minimum function with checks for NAN
Interval & setUpper(double value)
update upper bound
const int m
number of vertexes in Q
bool cellEmptyBounds(int i, int j) const
test if the bounding box of a cell is empty
static const Interval UNIT
the unit interval [0,1]
void calculateBounds(double epsilon)
calculate the bounding boxes of the free-space areas (k-Frechet only)
The FreeSpace class models the Free-Space Diagram calculated from two curves.
holds data for one cell of the free-space diagram
bool contains(double x) const
containment test (assumes closed interval, bounds inclusive)
const int n
number of vertexes in P
an interval of two double values.
FreeSpace(const Curve &ap, const Curve &aq)
default constructor with two input curves
bool valid() const
validity test
const Curve & Q
second input curve
void calculateEllipseBoundaries(const Point &p1, const Point &p2, const Point &q1, const Point &q2, double epsilon, double lambda[2])
compute the bounding box of one cell in the free-space are. As parameters we expect two segments of P...
Cell & cell(int x, int y)
const Curve & P
first input curve
double max(double a, double b)
maximum function with checks for NAN
QRectF boundingRect() const
calculate the bounding rectangle, i.e. a rectangle that is defined by the horizontal and vertical int...