1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkConvexHull2D.cxx
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14 =========================================================================*/
15
16 #include "vtkConvexHull2D.h"
17
18 #include "vtkCellArray.h"
19 #include "vtkCellData.h"
20 #include "vtkCoordinate.h"
21 #include "vtkInformation.h"
22 #include "vtkInformationVector.h"
23 #include "vtkObjectFactory.h"
24 #include "vtkPointsProjectedHull.h"
25 #include "vtkPolygon.h"
26 #include "vtkPolyLine.h"
27 #include "vtkRenderer.h"
28 #include "vtkSmartPointer.h"
29 #include "vtkTransform.h"
30 #include "vtkTransformPolyDataFilter.h"
31
32 #include <algorithm>
33
34 vtkStandardNewMacro(vtkConvexHull2D);
35
36 //-----------------------------------------------------------------------------
vtkConvexHull2D()37 vtkConvexHull2D::vtkConvexHull2D()
38 {
39 this->SetNumberOfOutputPorts(2);
40 this->ScaleFactor = 1.0;
41 this->Outline = false;
42 this->MinHullSizeInWorld = 1.0;
43 this->MinHullSizeInDisplay = 10;
44 this->HullShape = vtkConvexHull2D::ConvexHull;
45 this->Renderer = nullptr;
46
47 this->Coordinate = vtkSmartPointer<vtkCoordinate>::New();
48 this->Transform = vtkSmartPointer<vtkTransform>::New();
49 this->OutputTransform = vtkSmartPointer<vtkTransform>::New();
50 this->OutputTransformFilter = vtkSmartPointer<vtkTransformPolyDataFilter>::New();
51 this->OutputTransformFilter->SetTransform(this->OutputTransform);
52 this->OutlineSource = vtkSmartPointer<vtkPolyLine>::New();
53 this->HullSource = vtkSmartPointer<vtkPolygon>::New();
54 }
55
56 //-----------------------------------------------------------------------------
~vtkConvexHull2D()57 vtkConvexHull2D::~vtkConvexHull2D()
58 {
59 this->SetRenderer(nullptr);
60 }
61
62 //-----------------------------------------------------------------------------
CalculateBoundingRectangle(vtkPoints * inPoints,vtkPoints * outPoints,double minimumHullSize)63 void vtkConvexHull2D::CalculateBoundingRectangle(vtkPoints* inPoints,
64 vtkPoints* outPoints, double minimumHullSize)
65 {
66 minimumHullSize /= 2.0;
67 inPoints->ComputeBounds();
68 double bounds[6];
69 inPoints->GetBounds(bounds);
70
71 double xDeficit = minimumHullSize - (bounds[1] - bounds[0]);
72 if (xDeficit > 0.0)
73 {
74 bounds[0] -= xDeficit;
75 bounds[1] += xDeficit;
76 }
77
78 double yDeficit = minimumHullSize - (bounds[3] - bounds[2]);
79 if (yDeficit > 0.0)
80 {
81 bounds[2] -= yDeficit;
82 bounds[3] += yDeficit;
83 }
84
85 outPoints->SetNumberOfPoints(4);
86 outPoints->SetPoint(0, bounds[0], bounds[2], 0.0);
87 outPoints->SetPoint(1, bounds[1], bounds[2], 0.0);
88 outPoints->SetPoint(2, bounds[1], bounds[3], 0.0);
89 outPoints->SetPoint(3, bounds[0], bounds[3], 0.0);
90 }
91
92 //-----------------------------------------------------------------------------
CalculateConvexHull(vtkPoints * inPoints,vtkPoints * outPoints,double minimumHullSize)93 void vtkConvexHull2D::CalculateConvexHull(vtkPoints* inPoints,
94 vtkPoints* outPoints, double minimumHullSize)
95 {
96 if (inPoints->GetNumberOfPoints() == 1 ||
97 inPoints->GetNumberOfPoints() == 2)
98 {
99 vtkConvexHull2D::CalculateBoundingRectangle(inPoints, outPoints,
100 minimumHullSize);
101 }
102 else if (inPoints->GetNumberOfPoints() >= 3)
103 {
104 vtkPointsProjectedHull* ppHull = vtkPointsProjectedHull::New();
105 ppHull->ShallowCopy(inPoints);
106 int numHullPoints = ppHull->GetSizeCCWHullZ();
107 double* pts = new double[2 * numHullPoints];
108 ppHull->GetCCWHullZ(pts, numHullPoints);
109
110 vtkPoints* hullPoints = vtkPoints::New();
111 hullPoints->SetNumberOfPoints(numHullPoints);
112 for (vtkIdType i = 0; i < numHullPoints; ++i)
113 {
114 hullPoints->SetPoint(i, pts[2 * i], pts[2 * i + 1], 0.0);
115 }
116 ppHull->Delete();
117 delete[] pts;
118
119 if (numHullPoints < 3)
120 {
121 vtkConvexHull2D::CalculateBoundingRectangle(hullPoints, outPoints,
122 minimumHullSize);
123 return;
124 }
125
126 double bounds[6];
127 hullPoints->GetBounds(bounds);
128 double xScale = std::max(1.0, minimumHullSize / (bounds[1] - bounds[0]));
129 double yScale = std::max(1.0, minimumHullSize / (bounds[3] - bounds[2]));
130 if (xScale > 1.0 || yScale > 1.0)
131 {
132 double scale[3] = {xScale, yScale, 1.0};
133 double translate[3] = {
134 (bounds[0] + (bounds[1] - bounds[0]) / 2.0),
135 (bounds[2] + (bounds[3] - bounds[2]) / 2.0), 0.0};
136
137 vtkTransform* transform = vtkTransform::New();
138 transform->Translate(translate);
139 transform->Scale(scale);
140 transform->Translate(-translate[0], -translate[1], -translate[2]);
141 transform->TransformPoints(hullPoints, outPoints);
142 transform->Delete();
143 }
144 else
145 {
146 outPoints->ShallowCopy(hullPoints);
147 }
148 hullPoints->Delete();
149 }
150 }
151
152 //-----------------------------------------------------------------------------
ResizeHullToMinimumInDisplay(vtkPolyData * hullPolyData)153 void vtkConvexHull2D::ResizeHullToMinimumInDisplay(vtkPolyData* hullPolyData)
154 {
155 if (this->Renderer && this->Renderer->IsActiveCameraCreated())
156 {
157 double bounds[6];
158 hullPolyData->ComputeBounds();
159 hullPolyData->GetBounds(bounds);
160
161 double leftBottom[2];
162 double rightTop[2];
163 double* coord;
164 this->Coordinate->SetCoordinateSystemToWorld();
165 this->Coordinate->SetValue(bounds[0], bounds[2], 0.0);
166 coord = this->Coordinate->GetComputedDoubleDisplayValue(this->Renderer);
167 leftBottom[0] = coord[0];
168 leftBottom[1] = coord[1];
169 this->Coordinate->SetValue(bounds[1], bounds[3], 0.0);
170 coord = this->Coordinate->GetComputedDoubleDisplayValue(this->Renderer);
171 rightTop[0] = coord[0];
172 rightTop[1] = coord[1];
173 double currentDisplaySize[2] = {rightTop[0] - leftBottom[0],
174 rightTop[1] - leftBottom[1]};
175
176 if (currentDisplaySize[0] == 0.0 || currentDisplaySize[1] == 0.0)
177 {
178 vtkWarningMacro(<< "Can not scale a hull with zero display area.")
179 return;
180 }
181
182 if (currentDisplaySize[0] < this->MinHullSizeInDisplay ||
183 currentDisplaySize[1] < this->MinHullSizeInDisplay)
184 {
185 double scaleFx = std::max(1.0, this->MinHullSizeInDisplay
186 / currentDisplaySize[0]);
187 double scaleFy = std::max(1.0, this->MinHullSizeInDisplay
188 / currentDisplaySize[1]);
189 double scale[3] = {scaleFx, scaleFy, 1.0};
190 double translate[3] = {
191 (bounds[0] + (bounds[1] - bounds[0]) / 2.0),
192 (bounds[2] + (bounds[3] - bounds[2]) / 2.0), 0.0};
193
194 this->Transform->Identity();
195 this->Transform->Translate(translate);
196 this->Transform->Scale(scale);
197 this->Transform->Translate(-translate[0], -translate[1], -translate[2]);
198
199 vtkPoints* outPoints = vtkPoints::New();
200 this->Transform->TransformPoints(hullPolyData->GetPoints(), outPoints);
201 hullPolyData->SetPoints(outPoints);
202 outPoints->Delete();
203 }
204 }
205 }
206
207 //-----------------------------------------------------------------------------
SetRenderer(vtkRenderer * renderer)208 void vtkConvexHull2D::SetRenderer(vtkRenderer* renderer)
209 {
210 this->Renderer = renderer;
211 this->Modified();
212 }
213
214 //-----------------------------------------------------------------------------
GetRenderer()215 vtkRenderer* vtkConvexHull2D::GetRenderer()
216 {
217 return this->Renderer;
218 }
219
220 //-----------------------------------------------------------------------------
GetMTime()221 vtkMTimeType vtkConvexHull2D::GetMTime()
222 {
223 if (this->Renderer)
224 {
225 return this->Renderer->GetMTime();
226 }
227 else
228 {
229 return this->MTime;
230 }
231 }
232
233 //-----------------------------------------------------------------------------
RequestData(vtkInformation * vtkNotUsed (request),vtkInformationVector ** inputVector,vtkInformationVector * outputVector)234 int vtkConvexHull2D::RequestData(vtkInformation *vtkNotUsed(request),
235 vtkInformationVector **inputVector, vtkInformationVector *outputVector)
236 {
237 // Get the input and output.
238 vtkInformation *inInfo = inputVector[0]->GetInformationObject(0);
239
240 vtkPolyData* input = vtkPolyData::SafeDownCast(
241 inInfo->Get(vtkDataObject::DATA_OBJECT()));
242 vtkPoints* inputPoints = input->GetPoints();
243 if (!inputPoints)
244 {
245 vtkErrorMacro("Input points needed");
246 return 0;
247 }
248
249 vtkInformation *outInfo0 = outputVector->GetInformationObject(0);
250 vtkInformation *outInfo1 = outputVector->GetInformationObject(1);
251
252 vtkPolyData *outputHull = vtkPolyData::SafeDownCast(outInfo0->Get(
253 vtkDataObject::DATA_OBJECT()));
254 vtkPolyData *outputOutline = vtkPolyData::SafeDownCast(outInfo1->Get(
255 vtkDataObject::DATA_OBJECT()));
256
257 // Create filled polygon
258 vtkPoints* hullPoints = vtkPoints::New();
259 switch (this->HullShape)
260 {
261 case vtkConvexHull2D::BoundingRectangle:
262 this->CalculateBoundingRectangle(inputPoints, hullPoints,
263 this->MinHullSizeInWorld);
264 break;
265 default: // vtkConvexHull2D::ConvexHull
266 this->CalculateConvexHull(inputPoints, hullPoints,
267 this->MinHullSizeInWorld);
268 break;
269 }
270
271 vtkIdType numHullPoints = hullPoints->GetNumberOfPoints();
272 vtkIdType* hullPts = new vtkIdType[numHullPoints];
273 for (int i = 0; i < numHullPoints; ++i)
274 {
275 hullPts[i] = i;
276 }
277 this->HullSource->Initialize(numHullPoints, hullPts, hullPoints);
278 delete [] hullPts;
279
280 vtkCellArray* hullCells = vtkCellArray::New();
281 hullCells->InsertNextCell(this->HullSource);
282 vtkSmartPointer<vtkPolyData> hullPolyData = vtkSmartPointer<vtkPolyData>::New();
283 hullPolyData->SetPoints(hullPoints);
284 hullPolyData->SetPolys(hullCells);
285 hullPoints->Delete();
286 hullCells->Delete();
287
288 // Adjust for the scale-factor
289 double* centre = hullPolyData->GetCenter();
290 this->OutputTransform->Identity();
291 this->OutputTransform->Translate(centre);
292 this->OutputTransform->Scale(this->ScaleFactor, this->ScaleFactor, this->ScaleFactor);
293 this->OutputTransform->Translate(-centre[0], -centre[1], -centre[2]);
294 this->OutputTransformFilter->SetInputData(hullPolyData);
295 this->OutputTransformFilter->Update();
296 hullPolyData = this->OutputTransformFilter->GetOutput();
297
298 // Account for current camera zoom level
299 this->ResizeHullToMinimumInDisplay(hullPolyData);
300
301 // Copy hull to output
302 outputHull->ShallowCopy(hullPolyData);
303
304 if (this->Outline)
305 {
306 vtkIdType numOutlinePoints = outputHull->GetNumberOfPoints();
307 vtkIdType* outlinePts = new vtkIdType[numOutlinePoints + 1];
308 for (int i = 0; i < numOutlinePoints; ++i)
309 {
310 outlinePts[i] = i;
311 }
312 outlinePts[numOutlinePoints] = outlinePts[0];
313
314 this->OutlineSource->Initialize(numOutlinePoints + 1, outlinePts, outputHull->GetPoints());
315
316 vtkSmartPointer<vtkPolyData> outlinePolyData =
317 vtkSmartPointer<vtkPolyData>::New();
318 vtkCellArray* outlineCells = vtkCellArray::New();
319 outlineCells->InsertNextCell(this->OutlineSource);
320 outlinePolyData->SetPoints(outputHull->GetPoints());
321 outlinePolyData->SetLines(outlineCells);
322 outlineCells->Delete();
323 delete[] outlinePts;
324
325 // Copy outline to output
326 outputOutline->ShallowCopy(outlinePolyData);
327 }
328 return 1;
329 }
330
331 //-----------------------------------------------------------------------------
PrintSelf(ostream & os,vtkIndent indent)332 void vtkConvexHull2D::PrintSelf(ostream& os, vtkIndent indent)
333 {
334 this->Superclass::PrintSelf(os, indent);
335 os << indent << "ScaleFactor: " << this->ScaleFactor << "\n";
336 os << indent << "Outline: " << (this->Outline ? "On" : "Off") << "\n";
337 os << indent << "HullShape: ";
338 switch (this->HullShape)
339 {
340 case ConvexHull:
341 os << "ConvexHull\n";
342 break;
343 case BoundingRectangle:
344 os << "BoundingRectangle\n";
345 break;
346 default:
347 os << "Unknown\n";
348 break;
349 }
350 os << indent << "MinHullSizeInDisplay: " << this->MinHullSizeInDisplay << "\n";
351 os << indent << "MinHullSizeInWorld: " << this->MinHullSizeInWorld << "\n";
352 os << indent << "Renderer: ";
353 if (this->Renderer)
354 {
355 os << endl;
356 this->Renderer->PrintSelf(os, indent.GetNextIndent());
357 }
358 else
359 {
360 os << "(none)" << endl;
361 }
362 }
363