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