← Back to branch summary

~ubuntu-branches/ubuntu/trusty/qgis/trusty

« back to all changes in this revision

Viewing changes to src/core/spatialindex/geometry/LineSegment.cc

  • Committer: Bazaar Package Importer
  • Author(s): Johan Van de Wauw
  • Date: 2010-07-11 20:23:24 UTC
  • mfrom: (3.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100711202324-5ktghxa7hracohmr
Tags: 1.4.0+12730-3ubuntu1
https://launchpad.net/bugs/540941
* Merge from Debian unstable (LP: #540941).
* Fix compilation issues with QT 4.7
* Add build-depends on libqt4-webkit-dev 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/spatialindex/geometry/LineSegment.cc
 
1
// Tools Library
 
2
//
 
3
// Copyright (C) 2004  Navel Ltd.
 
4
//
 
5
// This library is free software; you can redistribute it and/or
 
6
// modify it under the terms of the GNU Lesser General Public
 
7
// License as published by the Free Software Foundation; either
 
8
// version 2.1 of the License, or (at your option) any later version.
 
9
//
 
10
// This library is distributed in the hope that it will be useful,
 
11
// but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
13
// Lesser General Public License for more details.
 
14
//
 
15
// You should have received a copy of the GNU Lesser General Public
 
16
// License along with this library; if not, write to the Free Software
 
17
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
18
//
 
19
//  Email:
 
20
//    mhadji@gmail.com
 
21
 
 
22
#include <cstring>
 
23
#include <limits>
 
24
#include <Tools.h>
 
25
 
 
26
Tools::Geometry::LineSegment::LineSegment()
 
27
    : m_dimension( 0 ), m_pStartPoint( 0 ), m_pEndPoint( 0 )
 
28
{
 
29
}
 
30
 
 
31
Tools::Geometry::LineSegment::LineSegment( const double* pStartPoint, const double* pEndPoint, unsigned long dimension )
 
32
    : m_dimension( dimension )
 
33
{
 
34
  // no need to initialize arrays to 0 since if a bad_alloc is raised the destructor will not be called.
 
35
 
 
36
  m_pStartPoint = new double[m_dimension];
 
37
  m_pEndPoint = new double[m_dimension];
 
38
  memcpy( m_pStartPoint, pStartPoint, m_dimension * sizeof( double ) );
 
39
  memcpy( m_pEndPoint, pEndPoint, m_dimension * sizeof( double ) );
 
40
}
 
41
 
 
42
Tools::Geometry::LineSegment::LineSegment( const Point& startPoint, const Point& endPoint )
 
43
    : m_dimension( startPoint.m_dimension )
 
44
{
 
45
  if ( startPoint.m_dimension != endPoint.m_dimension )
 
46
    throw Tools::IllegalArgumentException(
 
47
      "Tools::Geometry::LineSegment::LineSegment: Points have different dimensionalities."
 
48
    );
 
49
 
 
50
  // no need to initialize arrays to 0 since if a bad_alloc is raised the destructor will not be called.
 
51
 
 
52
  m_pStartPoint = new double[m_dimension];
 
53
  m_pEndPoint = new double[m_dimension];
 
54
  memcpy( m_pStartPoint, startPoint.m_pCoords, m_dimension * sizeof( double ) );
 
55
  memcpy( m_pEndPoint, endPoint.m_pCoords, m_dimension * sizeof( double ) );
 
56
}
 
57
 
 
58
Tools::Geometry::LineSegment::LineSegment( const LineSegment& l )
 
59
    : m_dimension( l.m_dimension )
 
60
{
 
61
  // no need to initialize arrays to 0 since if a bad_alloc is raised the destructor will not be called.
 
62
 
 
63
  m_pStartPoint = new double[m_dimension];
 
64
  m_pEndPoint = new double[m_dimension];
 
65
  memcpy( m_pStartPoint, l.m_pStartPoint, m_dimension * sizeof( double ) );
 
66
  memcpy( m_pEndPoint, l.m_pEndPoint, m_dimension * sizeof( double ) );
 
67
}
 
68
 
 
69
Tools::Geometry::LineSegment::~LineSegment()
 
70
{
 
71
  delete[] m_pStartPoint;
 
72
  delete[] m_pEndPoint;
 
73
}
 
74
 
 
75
Tools::Geometry::LineSegment& Tools::Geometry::LineSegment::operator=( const LineSegment & l )
 
76
{
 
77
  if ( this != &l )
 
78
  {
 
79
    makeDimension( l.m_dimension );
 
80
    memcpy( m_pStartPoint, l.m_pStartPoint, m_dimension * sizeof( double ) );
 
81
    memcpy( m_pEndPoint, l.m_pEndPoint, m_dimension * sizeof( double ) );
 
82
  }
 
83
 
 
84
  return *this;
 
85
}
 
86
 
 
87
bool Tools::Geometry::LineSegment::operator==( const LineSegment& l ) const
 
88
{
 
89
  if ( m_dimension != l.m_dimension )
 
90
    throw IllegalArgumentException(
 
91
      "Tools::Geometry::LineSegment::operator==: LineSegments have different number of dimensions."
 
92
    );
 
93
 
 
94
  for ( unsigned long i = 0; i < m_dimension; i++ )
 
95
  {
 
96
    if (
 
97
      m_pStartPoint[i] < l.m_pStartPoint[i] - std::numeric_limits<double>::epsilon() ||
 
98
      m_pStartPoint[i] > l.m_pStartPoint[i] + std::numeric_limits<double>::epsilon() )  return false;
 
99
 
 
100
    if (
 
101
      m_pEndPoint[i] < l.m_pEndPoint[i] - std::numeric_limits<double>::epsilon() ||
 
102
      m_pEndPoint[i] > l.m_pEndPoint[i] + std::numeric_limits<double>::epsilon() )  return false;
 
103
  }
 
104
 
 
105
  return true;
 
106
}
 
107
 
 
108
//
 
109
// IObject interface
 
110
//
 
111
Tools::Geometry::LineSegment* Tools::Geometry::LineSegment::clone()
 
112
{
 
113
  return new LineSegment( *this );
 
114
}
 
115
 
 
116
//
 
117
// ISerializable interface
 
118
//
 
119
unsigned long Tools::Geometry::LineSegment::getByteArraySize()
 
120
{
 
121
  return ( sizeof( unsigned long ) + m_dimension * sizeof( double ) * 2 );
 
122
}
 
123
 
 
124
void Tools::Geometry::LineSegment::loadFromByteArray( const byte* ptr )
 
125
{
 
126
  unsigned long dimension;
 
127
  memcpy( &dimension, ptr, sizeof( unsigned long ) );
 
128
  ptr += sizeof( unsigned long );
 
129
 
 
130
  makeDimension( dimension );
 
131
  memcpy( m_pStartPoint, ptr, m_dimension * sizeof( double ) );
 
132
  ptr += m_dimension * sizeof( double );
 
133
  memcpy( m_pEndPoint, ptr, m_dimension * sizeof( double ) );
 
134
  //ptr += m_dimension * sizeof(double);
 
135
}
 
136
 
 
137
void Tools::Geometry::LineSegment::storeToByteArray( byte** data, unsigned long& len )
 
138
{
 
139
  len = getByteArraySize();
 
140
  *data = new byte[len];
 
141
  byte* ptr = *data;
 
142
 
 
143
  memcpy( ptr, &m_dimension, sizeof( unsigned long ) );
 
144
  ptr += sizeof( unsigned long );
 
145
  memcpy( ptr, m_pStartPoint, m_dimension * sizeof( double ) );
 
146
  ptr += m_dimension * sizeof( double );
 
147
  memcpy( ptr, m_pEndPoint, m_dimension * sizeof( double ) );
 
148
  //ptr += m_dimension * sizeof(double);
 
149
}
 
150
 
 
151
//
 
152
// IShape interface
 
153
//
 
154
bool Tools::Geometry::LineSegment::intersectsShape( const IShape& s ) const
 
155
{
 
156
  throw IllegalStateException(
 
157
    "Tools::Geometry::LineSegment::intersectsShape: Not implemented yet!"
 
158
  );
 
159
}
 
160
 
 
161
bool Tools::Geometry::LineSegment::containsShape( const IShape& s ) const
 
162
{
 
163
  return false;
 
164
}
 
165
 
 
166
bool Tools::Geometry::LineSegment::touchesShape( const IShape& s ) const
 
167
{
 
168
  throw IllegalStateException(
 
169
    "Tools::Geometry::LineSegment::touchesShape: Not implemented yet!"
 
170
  );
 
171
}
 
172
 
 
173
void Tools::Geometry::LineSegment::getCenter( Point& out ) const
 
174
{
 
175
  double* coords = new double[m_dimension];
 
176
 
 
177
  for ( unsigned long cDim = 0; cDim < m_dimension; cDim++ )
 
178
  {
 
179
    coords[cDim] =
 
180
      ( std::abs( m_pStartPoint[cDim] - m_pEndPoint[cDim] ) / 2.0 ) +
 
181
      std::min( m_pStartPoint[cDim], m_pEndPoint[cDim] );
 
182
  }
 
183
 
 
184
  out = Point( coords, m_dimension );
 
185
 
 
186
  delete[] coords;
 
187
}
 
188
 
 
189
unsigned long Tools::Geometry::LineSegment::getDimension() const
 
190
{
 
191
  return m_dimension;
 
192
}
 
193
 
 
194
void Tools::Geometry::LineSegment::getMBR( Region& out ) const
 
195
{
 
196
  double* low = new double[m_dimension];
 
197
  double* high = new double[m_dimension];
 
198
 
 
199
  for ( unsigned long cDim = 0; cDim < m_dimension; cDim++ )
 
200
  {
 
201
    low[cDim] = std::min( m_pStartPoint[cDim], m_pEndPoint[cDim] );
 
202
    high[cDim] = std::max( m_pStartPoint[cDim], m_pEndPoint[cDim] );
 
203
  }
 
204
 
 
205
  out = Region( low, high, m_dimension );
 
206
 
 
207
  delete[] low;
 
208
  delete[] high;
 
209
}
 
210
 
 
211
double Tools::Geometry::LineSegment::getArea() const
 
212
{
 
213
  return 0.0;
 
214
}
 
215
 
 
216
double Tools::Geometry::LineSegment::getMinimumDistance( const IShape& s ) const
 
217
{
 
218
  const Point* ppt = dynamic_cast<const Point*>( &s );
 
219
  if ( ppt != 0 )
 
220
  {
 
221
    return getMinimumDistance( *ppt );
 
222
  }
 
223
 
 
224
  /*
 
225
   const Region* pr = dynamic_cast<const Region*>(&s);
 
226
   if (pr != 0)
 
227
   {
 
228
    return pr->getMinimumDistance(*this);
 
229
   }
 
230
  */
 
231
 
 
232
  throw IllegalStateException(
 
233
    "Tools::Geometry::LineSegment::getMinimumDistance: Not implemented yet!"
 
234
  );
 
235
}
 
236
 
 
237
double Tools::Geometry::LineSegment::getMinimumDistance( const Point& p ) const
 
238
{
 
239
  if ( m_dimension == 1 )
 
240
    throw Tools::NotSupportedException(
 
241
      "Tools::Geometry::LineSegment::getMinimumDistance: Use an Interval instead."
 
242
    );
 
243
 
 
244
  if ( m_dimension != 2 )
 
245
    throw Tools::NotSupportedException(
 
246
      "Tools::Geometry::LineSegment::getMinimumDistance: Distance for high dimensional spaces not supported!"
 
247
    );
 
248
 
 
249
  if ( m_pEndPoint[0] >= m_pStartPoint[0] - std::numeric_limits<double>::epsilon() &&
 
250
       m_pEndPoint[0] <= m_pStartPoint[0] + std::numeric_limits<double>::epsilon() ) return std::abs( p.m_pCoords[0] - m_pStartPoint[0] );
 
251
 
 
252
  if ( m_pEndPoint[1] >= m_pStartPoint[1] - std::numeric_limits<double>::epsilon() &&
 
253
       m_pEndPoint[1] <= m_pStartPoint[1] + std::numeric_limits<double>::epsilon() ) return std::abs( p.m_pCoords[1] - m_pStartPoint[1] );
 
254
 
 
255
  double x1 = m_pStartPoint[0];
 
256
  double x2 = m_pEndPoint[0];
 
257
  double x0 = p.m_pCoords[0];
 
258
  double y1 = m_pStartPoint[1];
 
259
  double y2 = m_pEndPoint[1];
 
260
  double y0 = p.m_pCoords[1];
 
261
 
 
262
  return std::abs(( x2 - x1 ) *( y1 - y0 ) - ( x1 - x0 ) *( y2 - y1 ) ) / ( std::sqrt(( x2 - x1 ) *( x2 - x1 ) + ( y2 - y1 ) *( y2 - y1 ) ) );
 
263
}
 
264
 
 
265
// assuming moving from start to end, positive distance is from right hand side.
 
266
double Tools::Geometry::LineSegment::getRelativeMinimumDistance( const Point& p ) const
 
267
{
 
268
  if ( m_dimension == 1 )
 
269
    throw Tools::NotSupportedException(
 
270
      "Tools::Geometry::LineSegment::getRelativeMinimumDistance: Use an Interval instead."
 
271
    );
 
272
 
 
273
  if ( m_dimension != 2 )
 
274
    throw Tools::NotSupportedException(
 
275
      "Tools::Geometry::LineSegment::getRelativeMinimumDistance: Distance for high dimensional spaces not supported!"
 
276
    );
 
277
 
 
278
  if ( m_pEndPoint[0] >= m_pStartPoint[0] - std::numeric_limits<double>::epsilon() &&
 
279
       m_pEndPoint[0] <= m_pStartPoint[0] + std::numeric_limits<double>::epsilon() )
 
280
  {
 
281
    if ( m_pStartPoint[1] < m_pEndPoint[1] ) return m_pStartPoint[0] - p.m_pCoords[0];
 
282
    if ( m_pStartPoint[1] >= m_pEndPoint[1] ) return p.m_pCoords[0] - m_pStartPoint[0];
 
283
  }
 
284
 
 
285
  if ( m_pEndPoint[1] >= m_pStartPoint[1] - std::numeric_limits<double>::epsilon() &&
 
286
       m_pEndPoint[1] <= m_pStartPoint[1] + std::numeric_limits<double>::epsilon() )
 
287
  {
 
288
    if ( m_pStartPoint[0] < m_pEndPoint[0] ) return p.m_pCoords[1] - m_pStartPoint[1];
 
289
    if ( m_pStartPoint[0] >= m_pEndPoint[0] ) return m_pStartPoint[1] - p.m_pCoords[1];
 
290
  }
 
291
 
 
292
  double x1 = m_pStartPoint[0];
 
293
  double x2 = m_pEndPoint[0];
 
294
  double x0 = p.m_pCoords[0];
 
295
  double y1 = m_pStartPoint[1];
 
296
  double y2 = m_pEndPoint[1];
 
297
  double y0 = p.m_pCoords[1];
 
298
 
 
299
  return (( x1 - x0 ) *( y2 - y1 ) - ( x2 - x1 ) *( y1 - y0 ) ) / ( std::sqrt(( x2 - x1 ) *( x2 - x1 ) + ( y2 - y1 ) *( y2 - y1 ) ) );
 
300
}
 
301
 
 
302
double Tools::Geometry::LineSegment::getRelativeMaximumDistance( const Tools::Geometry::Region& r ) const
 
303
{
 
304
  if ( m_dimension == 1 )
 
305
    throw Tools::NotSupportedException(
 
306
      "Tools::Geometry::LineSegment::getRelativeMaximumDistance: Use an Interval instead."
 
307
    );
 
308
 
 
309
  if ( m_dimension != 2 )
 
310
    throw Tools::NotSupportedException(
 
311
      "Tools::Geometry::LineSegment::getRelativeMaximumDistance: Distance for high dimensional spaces not supported!"
 
312
    );
 
313
 
 
314
  // clockwise.
 
315
  double d1 = getRelativeMinimumDistance( Point( r.m_pLow, 2 ) );
 
316
 
 
317
  double coords[2];
 
318
  coords[0] = r.m_pLow[0];
 
319
  coords[1] = r.m_pHigh[1];
 
320
  double d2 = getRelativeMinimumDistance( Point( coords, 2 ) );
 
321
 
 
322
  double d3 = getRelativeMinimumDistance( Point( r.m_pHigh, 2 ) );
 
323
 
 
324
  coords[0] = r.m_pHigh[0];
 
325
  coords[1] = r.m_pLow[1];
 
326
  double d4 = getRelativeMinimumDistance( Point( coords, 2 ) );
 
327
 
 
328
  return std::max( d1, std::max( d2, std::max( d3, d4 ) ) );
 
329
}
 
330
 
 
331
double Tools::Geometry::LineSegment::getAngleOfPerpendicularRay()
 
332
{
 
333
  if ( m_dimension == 1 )
 
334
    throw Tools::NotSupportedException(
 
335
      "Tools::Geometry::LineSegment::getAngleOfPerpendicularRay: Use an Interval instead."
 
336
    );
 
337
 
 
338
  if ( m_dimension != 2 )
 
339
    throw Tools::NotSupportedException(
 
340
      "Tools::Geometry::LineSegment::getAngleOfPerpendicularRay: Distance for high dimensional spaces not supported!"
 
341
    );
 
342
 
 
343
  if ( m_pStartPoint[0] >= m_pEndPoint[0] - std::numeric_limits<double>::epsilon() &&
 
344
       m_pStartPoint[0] <= m_pEndPoint[0] + std::numeric_limits<double>::epsilon() ) return 0.0;
 
345
 
 
346
  if ( m_pStartPoint[1] >= m_pEndPoint[1] - std::numeric_limits<double>::epsilon() &&
 
347
       m_pStartPoint[1] <= m_pEndPoint[1] + std::numeric_limits<double>::epsilon() ) return M_PI_2;
 
348
 
 
349
  return std::atan( -( m_pStartPoint[0] - m_pEndPoint[0] ) / ( m_pStartPoint[1] - m_pEndPoint[1] ) );
 
350
}
 
351
 
 
352
void Tools::Geometry::LineSegment::makeInfinite( unsigned long dimension )
 
353
{
 
354
  makeDimension( dimension );
 
355
  for ( unsigned long cIndex = 0; cIndex < m_dimension; cIndex++ )
 
356
  {
 
357
    m_pStartPoint[cIndex] = std::numeric_limits<double>::max();
 
358
    m_pEndPoint[cIndex] = std::numeric_limits<double>::max();
 
359
  }
 
360
}
 
361
 
 
362
void Tools::Geometry::LineSegment::makeDimension( unsigned long dimension )
 
363
{
 
364
  if ( m_dimension != dimension )
 
365
  {
 
366
    delete[] m_pStartPoint;
 
367
    delete[] m_pEndPoint;
 
368
 
 
369
    // remember that this is not a constructor. The object will be destructed normally if
 
370
    // something goes wrong (bad_alloc), so we must take care not to leave the object at an intermediate state.
 
371
    m_pStartPoint = 0;
 
372
    m_pEndPoint = 0;
 
373
 
 
374
    m_dimension = dimension;
 
375
    m_pStartPoint = new double[m_dimension];
 
376
    m_pEndPoint = new double[m_dimension];
 
377
  }
 
378
}
 
379
 
 
380
std::ostream& Tools::Geometry::operator<<( std::ostream& os, const LineSegment& l )
 
381
{
 
382
  for ( unsigned long cDim = 0; cDim < l.m_dimension; cDim++ )
 
383
  {
 
384
    os << l.m_pStartPoint[cDim] << ", " << l.m_pEndPoint[cDim] << " ";
 
385
  }
 
386
 
 
387
  return os;
 
388
}