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 150 vtkPointsProjectedHull(); 151 ~vtkPointsProjectedHull() override; 152 153 private: 154 155 int RectangleIntersection(double hmin, double hmax, 156 double vmin, double vmax, int direction); 157 int GrahamScanAlgorithm(int direction); 158 void GetPoints(); 159 int RectangleBoundingBoxIntersection(double hmin, double hmax, 160 double vmin, double vmax, int direction); 161 int RectangleOutside(double hmin, double hmax, 162 double vmin, double vmax, int direction); 163 164 int RectangleOutside1DPolygon(double hmin, double hmax, 165 double vmin, double vmax, int dir); 166 167 void InitFlags(); 168 void ClearAllocations(); 169 170 171 static int RemoveExtras(double *pts, int n); 172 static double Distance(double *p1, double *p2); 173 static vtkIdType PositionInHull(double *base, double *top, double *pt); 174 static int OutsideLine(double hmin, double hmax, 175 double vmin, double vmax, double *p0, double *p1, double *insidePt); 176 static int OutsideHorizontalLine(double vmin, double vmax, 177 double *p0, double *p1, double *insidePt); 178 static int OutsideVerticalLine(double hmin, double hmax, double *p0, 179 double *p1, double *insidePt); 180 181 double *Pts; 182 vtkIdType Npts; 183 vtkTimeStamp PtsTime; 184 185 double *CCWHull[3]; 186 float HullBBox[3][4]; 187 int HullSize[3]; 188 vtkTimeStamp HullTime[3]; 189 190 vtkPointsProjectedHull(const vtkPointsProjectedHull&) = delete; 191 void operator=(const vtkPointsProjectedHull&) = delete; 192 }; 193 #endif 194 195 196