1 /*========================================================================= 2 3 Program: Visualization Toolkit 4 Module: vtkPointsProjectedHull.h 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 Copyright (c) Sandia Corporation 17 See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details. 18 ----------------------------------------------------------------------------*/ 19 20 /** 21 * @class vtkPointsProjectedHull 22 * @brief the convex hull of the orthogonal 23 * projection of the vtkPoints in the 3 coordinate directions 24 * 25 * a subclass of vtkPoints, it maintains the counter clockwise 26 * convex hull of the points (projected orthogonally in the 27 * three coordinate directions) and has a method to 28 * test for intersection of that hull with an axis aligned 29 * rectangle. This is used for intersection tests of 3D volumes. 30 */ 31 32 #ifndef vtkPointsProjectedHull_h 33 #define vtkPointsProjectedHull_h 34 35 #include "vtkCommonDataModelModule.h" // For export macro 36 #include "vtkPoints.h" 37 38 class VTKCOMMONDATAMODEL_EXPORT vtkPointsProjectedHull : public vtkPoints 39 { 40 vtkTypeMacro(vtkPointsProjectedHull, vtkPoints); 41 42 public: 43 void PrintSelf(ostream& os, vtkIndent indent) override; 44 45 static vtkPointsProjectedHull* New(); 46 47 /** 48 * determine whether the resulting rectangle intersects the 49 * convex hull of the projection of the points along that axis. 50 */ 51 52 int RectangleIntersectionX(vtkPoints* R); 53 54 /** 55 * the convex hull of the projection of the points along the 56 * positive X-axis. 57 */ 58 59 int RectangleIntersectionX(float ymin, float ymax, float zmin, float zmax); 60 int RectangleIntersectionX(double ymin, double ymax, double zmin, double zmax); 61 62 /** 63 * of the parallel projection along the Y axis of the points 64 */ 65 66 int RectangleIntersectionY(vtkPoints* R); 67 68 /** 69 * the convex hull of the projection of the points along the 70 * positive Y-axis. 71 */ 72 73 int RectangleIntersectionY(float zmin, float zmax, float xmin, float xmax); 74 int RectangleIntersectionY(double zmin, double zmax, double xmin, double xmax); 75 76 /** 77 * of the parallel projection along the Z axis of the points 78 */ 79 80 int RectangleIntersectionZ(vtkPoints* R); 81 82 /** 83 * the convex hull of the projection of the points along the 84 * positive Z-axis. 85 */ 86 87 int RectangleIntersectionZ(float xmin, float xmax, float ymin, float ymax); 88 int RectangleIntersectionZ(double xmin, double xmax, double ymin, double ymax); 89 90 /** 91 * Returns the coordinates (y,z) of the points in the convex hull 92 * of the projection of the points down the positive x-axis. pts has 93 * storage for len*2 values. 94 */ 95 96 int GetCCWHullX(float* pts, int len); 97 int GetCCWHullX(double* pts, int len); 98 99 /** 100 * Returns the coordinates (z, x) of the points in the convex hull 101 * of the projection of the points down the positive y-axis. pts has 102 * storage for len*2 values. 103 */ 104 105 int GetCCWHullY(float* pts, int len); 106 int GetCCWHullY(double* pts, int len); 107 108 /** 109 * Returns the coordinates (x, y) of the points in the convex hull 110 * of the projection of the points down the positive z-axis. pts has 111 * storage for len*2 values. 112 */ 113 114 int GetCCWHullZ(float* pts, int len); 115 int GetCCWHullZ(double* pts, int len); 116 117 /** 118 * Returns the number of points in the convex hull of the projection 119 * of the points down the positive x-axis 120 */ 121 122 int GetSizeCCWHullX(); 123 124 /** 125 * Returns the number of points in the convex hull of the projection 126 * of the points down the positive y-axis 127 */ 128 129 int GetSizeCCWHullY(); 130 131 /** 132 * Returns the number of points in the convex hull of the projection 133 * of the points down the positive z-axis 134 */ 135 136 int GetSizeCCWHullZ(); 137 138 void Initialize() override; Reset()139 void Reset() override { this->Initialize(); } 140 141 /** 142 * Forces recalculation of convex hulls, use this if 143 * you delete/add points 144 */ 145 146 void Update(); 147 148 protected: 149 vtkPointsProjectedHull(); 150 ~vtkPointsProjectedHull() override; 151 152 private: 153 int RectangleIntersection(double hmin, double hmax, double vmin, double vmax, int direction); 154 int GrahamScanAlgorithm(int direction); 155 void GetPoints(); 156 int RectangleBoundingBoxIntersection( 157 double hmin, double hmax, double vmin, double vmax, int direction); 158 int RectangleOutside(double hmin, double hmax, double vmin, double vmax, int direction); 159 160 int RectangleOutside1DPolygon(double hmin, double hmax, double vmin, double vmax, int dir); 161 162 void InitFlags(); 163 void ClearAllocations(); 164 165 static int RemoveExtras(double* pts, int n); 166 static double Distance(double* p1, double* p2); 167 static vtkIdType PositionInHull(double* base, double* top, double* pt); 168 static int OutsideLine( 169 double hmin, double hmax, double vmin, double vmax, double* p0, double* p1, double* insidePt); 170 static int OutsideHorizontalLine( 171 double vmin, double vmax, double* p0, double* p1, double* insidePt); 172 static int OutsideVerticalLine( 173 double hmin, double hmax, double* p0, double* p1, double* insidePt); 174 175 double* Pts; 176 vtkIdType Npts; 177 vtkTimeStamp PtsTime; 178 179 double* CCWHull[3]; 180 float HullBBox[3][4]; 181 int HullSize[3]; 182 vtkTimeStamp HullTime[3]; 183 184 vtkPointsProjectedHull(const vtkPointsProjectedHull&) = delete; 185 void operator=(const vtkPointsProjectedHull&) = delete; 186 }; 187 #endif 188