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