| 197 | } |
| 198 | |
| 199 | VTK_ABI_NAMESPACE_BEGIN |
| 200 | int vtkPointsProjectedHull::GrahamScanAlgorithm(int dir) |
| 201 | { |
| 202 | int horizAxis = 0, vertAxis = 0; |
| 203 | |
| 204 | if ((this->Npts == 0) || (this->GetMTime() > this->PtsTime)) |
| 205 | { |
| 206 | GetPoints(); |
| 207 | } |
| 208 | |
| 209 | // I'm not sure what I'm doing here but the current code is clearly screwed |
| 210 | // up and doesn't handle some degenerate cases |
| 211 | if (this->Npts == 0) |
| 212 | { |
| 213 | return 0; |
| 214 | } |
| 215 | |
| 216 | switch (dir) |
| 217 | { |
| 218 | case xdim: |
| 219 | horizAxis = ydim; |
| 220 | vertAxis = zdim; |
| 221 | break; |
| 222 | |
| 223 | case ydim: |
| 224 | horizAxis = zdim; |
| 225 | vertAxis = xdim; |
| 226 | break; |
| 227 | |
| 228 | case zdim: |
| 229 | horizAxis = xdim; |
| 230 | vertAxis = ydim; |
| 231 | break; |
| 232 | } |
| 233 | |
| 234 | // Find the lowest, rightmost point in the set |
| 235 | |
| 236 | double* hullPts = new double[this->Npts * 2]; |
| 237 | |
| 238 | for (vtkIdType i = 0; i < this->Npts; ++i) |
| 239 | { |
| 240 | hullPts[i * 2] = this->Pts[i * 3 + horizAxis]; |
| 241 | hullPts[i * 2 + 1] = this->Pts[i * 3 + vertAxis]; |
| 242 | } |
| 243 | |
| 244 | qsort(hullPts, this->Npts, sizeof(double) * 2, vtkPointsProjectedHullIncrVertAxis); |
| 245 | |
| 246 | int firstId = 0; |
| 247 | |
| 248 | for (vtkIdType i = 1; i < this->Npts; ++i) |
| 249 | { |
| 250 | if (hullPts[i * 2 + 1] != hullPts[1]) |
| 251 | break; |
| 252 | |
| 253 | if (hullPts[i * 2] > hullPts[firstId * 2]) |
| 254 | { |
| 255 | firstId = i; |
| 256 | } |