GOFIGURE2  0.9.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
vtkPolylineDecimation.cxx
Go to the documentation of this file.
1 /*=========================================================================
2  Authors: The GoFigure Dev. Team.
3  at Megason Lab, Systems biology, Harvard Medical school, 2009-11
4 
5  Copyright (c) 2009-11, President and Fellows of Harvard College.
6  All rights reserved.
7 
8  Redistribution and use in source and binary forms, with or without
9  modification, are permitted provided that the following conditions are met:
10 
11  Redistributions of source code must retain the above copyright notice,
12  this list of conditions and the following disclaimer.
13  Redistributions in binary form must reproduce the above copyright notice,
14  this list of conditions and the following disclaimer in the documentation
15  and/or other materials provided with the distribution.
16  Neither the name of the President and Fellows of Harvard College
17  nor the names of its contributors may be used to endorse or promote
18  products derived from this software without specific prior written
19  permission.
20 
21  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
23  THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
25  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
26  OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
27  OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
28  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
30  OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 
33 =========================================================================*/
34 
35 #include "vtkPolylineDecimation.h"
36 
37 #include "vtkDoubleArray.h"
38 #include "vtkLine.h"
39 #include "vtkMath.h"
40 #include "vtkInformation.h"
41 #include "vtkInformationVector.h"
42 #include "vtkObjectFactory.h"
43 #include "vtkLine.h"
44 #include "vtkPolyData.h"
45 #include "vtkPoints.h"
46 #include "vtkCellArray.h"
47 #include "vtkPointData.h"
48 #include "vtkCellData.h"
49 #include <vtkstd/list>
50 #include <vtkstd/vector>
51 #include <vtkstd/queue>
52 
53 vtkCxxRevisionMacro(vtkPolylineDecimation, "$Revision: 1.1 $");
55 
56 //---------------------------------------------------------------------
57 // Create object with specified reduction of 90%.
59 {
60  this->TargetReduction = 0.90;
61  this->Closed = true;
62  this->PriorityQueue = vtkPriorityQueue::New();
63 }
64 
65 //---------------------------------------------------------------------
67 {
68  this->PriorityQueue->Delete();
69 }
70 
71 double vtkPolylineDecimation::ComputeError(vtkPolyData *input,
72  int prev, int id, int next)
73 {
74  vtkPoints *inputPoints = input->GetPoints();
75 
76  double x1[3], x[3], x2[3];
77 
78  inputPoints->GetPoint(prev, x1);
79  inputPoints->GetPoint(id, x);
80  inputPoints->GetPoint(next, x2);
81 
82  if ( vtkMath::Distance2BetweenPoints(x1, x2) == 0.0 )
83  {
84  return 0.0;
85  }
86  else
87  {
88  return vtkLine::DistanceToLine(x, x1, x2);
89  }
90 }
91 
92 //---------------------------------------------------------------------
93 // Reduce the number of points in a set of polylines
94 //
96  vtkInformation *vtkNotUsed(request),
97  vtkInformationVector **inputVector,
98  vtkInformationVector *outputVector)
99 {
100  // get the info objects
101  vtkInformation *inInfo = inputVector[0]->GetInformationObject(0);
102  vtkInformation *outInfo = outputVector->GetInformationObject(0);
103 
104  // get the input and ouptut
105  vtkPolyData *input = vtkPolyData::SafeDownCast(
106  inInfo->Get( vtkDataObject::DATA_OBJECT() ) );
107  vtkPolyData *output = vtkPolyData::SafeDownCast(
108  outInfo->Get( vtkDataObject::DATA_OBJECT() ) );
109 
110  vtkCellArray *inputLines = input->GetLines();
111  vtkPoints * inputPoints = input->GetPoints();
112 
113  if ( !inputLines || !inputPoints )
114  {
115  return 1;
116  }
117  vtkIdType numLines = inputLines->GetNumberOfCells();
118  vtkIdType numPts = inputPoints->GetNumberOfPoints();
119  if ( numLines < 1 || numPts < 1 )
120  {
121  return 1;
122  }
123 
124  // Allocate memory and prepare for data processing
125  vtkPoints * newPts = vtkPoints::New();
126  vtkCellArray *newLines = vtkCellArray::New();
127  newLines->Allocate(numLines, 2);
128  vtkPointData *inPD = input->GetPointData();
129  vtkPointData *outPD = output->GetPointData();
130  vtkCellData * inCD = input->GetCellData();
131  vtkCellData * outCD = output->GetCellData();
132  outPD->CopyAllocate(inPD);
133  outCD->CopyAllocate(inCD);
134 
135  // Loop over all polylines, decimating each independently
136  vtkIdType i, cellId = 0, newId;
137  double error;
138 
139  for ( i = 0; i < numPts; i++ )
140  {
141  this->VertexErrorMap[i] = 0.;
142  }
143 
144  for ( i = 0; i < numPts; i++ )
145  {
146  error = ComputeError( input, GetPrev(i), i, GetNext(i) );
147  this->VertexErrorMap[i] = error;
148  this->PriorityQueue->Insert(error, i);
149  } //for all points in polyline
150 
151  // Now process structures,
152  // deleting points until the decimation target is met.
153  vtkIdType currentNumPts = this->PriorityQueue->GetNumberOfItems();
154  while ( 1.0 - ( static_cast< double >( currentNumPts ) / static_cast< double >(
155  numPts ) )
156  < this->TargetReduction
157  && currentNumPts > 2 )
158  {
159  i = this->PriorityQueue->Pop();
160  currentNumPts--;
161  UpdateError(input, i);
162  this->VertexErrorMap.erase(i);
163  }
164 
165  // What's left over is now spit out as a new polyline
166  newId = newLines->InsertNextCell(currentNumPts + 1);
167  outCD->CopyData(inCD, cellId, newId);
168 
169  for ( std::map< int, double >::iterator it = this->VertexErrorMap.begin();
170  it != this->VertexErrorMap.end();
171  ++it )
172  {
173  newId = newPts->InsertNextPoint( inputPoints->GetPoint(it->first) );
174  newLines->InsertCellPoint(newId);
175  outPD->CopyData(inPD, it->first, newId);
176  }
177  if ( this->Closed )
178  {
179  newId = newPts->InsertNextPoint( newPts->GetPoint(0) );
180  newLines->InsertCellPoint(0);
181  outPD->CopyData(inPD, this->VertexErrorMap.begin()->first, newId);
182  }
183 
184  // Clean up in preparation for the next line
185  this->PriorityQueue->Reset();
186 
187 // Create output and clean up
188  output->SetPoints(newPts);
189  output->SetLines(newLines);
190 
191  newLines->Delete();
192  newPts->Delete();
193 
194  return 1;
195 }
196 
197 //---------------------------------------------------------------------
198 int vtkPolylineDecimation::GetPrev(const int & iId)
199 {
200  std::map< int, double >::iterator it = this->VertexErrorMap.find(iId);
201 
202  if ( it == this->VertexErrorMap.begin() )
203  {
204  if ( this->Closed )
205  {
206  it = this->VertexErrorMap.end();
207  --it;
208  return it->first;
209  }
210  else
211  {
212  return iId;
213  }
214  }
215  else
216  {
217  --it;
218  return it->first;
219  }
220 }
221 
222 //---------------------------------------------------------------------
223 int vtkPolylineDecimation::GetNext(const int & iId)
224 {
225  std::map< int, double >::iterator it = this->VertexErrorMap.find(iId);
226  std::map< int, double >::iterator end_it = this->VertexErrorMap.end();
227  --end_it;
228  if ( it == end_it )
229  {
230  if ( this->Closed ) { return this->VertexErrorMap.begin()->first; }
231  else
232  {
233  return iId;
234  }
235  }
236  else
237  {
238  ++it;
239  return it->first;
240  }
241 }
242 
243 //---------------------------------------------------------------------
244 void vtkPolylineDecimation::UpdateError(vtkPolyData *input, const int & iId)
245 {
246  int prev = GetPrev(iId);
247  int prev_prev = GetPrev(prev);
248  int next = GetNext(iId);
249  int next_next = GetNext(next);
250 
251  double prev_error = ComputeError(input, prev_prev, prev, next);
252 
253  this->VertexErrorMap[prev] = prev_error;
254  this->PriorityQueue->DeleteId(prev);
255  this->PriorityQueue->Insert(prev_error, prev);
256 
257  double next_error = ComputeError(input, prev, next, next_next);
258  this->VertexErrorMap[next] = next_error;
259  this->PriorityQueue->DeleteId(next);
260  this->PriorityQueue->Insert(next_error, next);
261 }
262 
263 //---------------------------------------------------------------------
264 void vtkPolylineDecimation::PrintSelf(ostream & os, vtkIndent indent)
265 {
266  this->Superclass::PrintSelf(os, indent);
267 
268  os << indent << "Target Reduction: " << this->TargetReduction << "\n";
269 }
vtkCxxRevisionMacro(vtkFillImageWithPolyData,"$Revision: 490 $")
vtkPriorityQueue * PriorityQueue
int RequestData(vtkInformation *vtkNotUsed(request), vtkInformationVector **inputVector, vtkInformationVector *outputVector)
double ComputeError(vtkPolyData *input, int prev, int id, int next)
Decimate a polyline.
void PrintSelf(ostream &os, vtkIndent indent)
vtkStandardNewMacro(vtkFillImageWithPolyData)
std::map< int, double > VertexErrorMap
void UpdateError(vtkPolyData *input, const int &iId)