SUMO - Simulation of Urban MObility
Helper_ConvexHull.cpp
Go to the documentation of this file.
00001 /****************************************************************************/
00009 // Copyright 2002, softSurfer (www.softsurfer.com)
00010 // This code may be freely used and modified for any purpose
00011 // providing that this copyright notice is included with it.
00012 // SoftSurfer makes no warranty for this code, and cannot be held
00013 // liable for any real or imagined damage resulting from its use.
00014 // Users of this code must verify correctness for their application.
00015 /****************************************************************************/
00016 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
00017 // Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors
00018 /****************************************************************************/
00019 //
00020 //   This file is part of SUMO.
00021 //   SUMO is free software: you can redistribute it and/or modify
00022 //   it under the terms of the GNU General Public License as published by
00023 //   the Free Software Foundation, either version 3 of the License, or
00024 //   (at your option) any later version.
00025 //
00026 /****************************************************************************/
00027 
00028 
00029 // ===========================================================================
00030 // included modules
00031 // ===========================================================================
00032 #ifdef _MSC_VER
00033 #include <windows_config.h>
00034 #else
00035 #include <config.h>
00036 #endif
00037 
00038 #include "Helper_ConvexHull.h"
00039 
00040 
00041 #include <utils/common/UtilExceptions.h>
00042 #include <iostream>
00043 
00044 #ifdef CHECK_MEMORY_LEAKS
00045 #include <foreign/nvwa/debug_new.h>
00046 #endif // CHECK_MEMORY_LEAKS
00047 
00048 
00049 // Assume that a class is already given for the object:
00050 //    Position with coordinates {SUMOReal x, y;}
00051 PositionVector
00052 simpleHull_2D(const PositionVector& V) {
00053     if (V.size() < 3) {
00054         throw ProcessError();
00055     }
00056     // initialize a deque D[] from bottom to top so that the
00057     // 1st three vertices of V[] are a counterclockwise triangle
00058     int n = (int) V.size();
00059     std::vector<Position> D(2 * n + 1);
00060     int bot = n - 2, top = bot + 3; // initial bottom and top deque indices
00061     D[bot] = D[top] = V[2];       // 3rd vertex is at both bot and top
00062     if (isLeft(V[0], V[1], V[2]) > 0) {
00063         D[bot + 1] = V[0];
00064         D[bot + 2] = V[1];        // ccw vertices are: 2,0,1,2
00065     } else {
00066         D[bot + 1] = V[1];
00067         D[bot + 2] = V[0];        // ccw vertices are: 2,1,0,2
00068     }
00069 
00070     // compute the hull on the deque D[]
00071     for (int i = 3; i < n; i++) { // process the rest of vertices
00072         // test if next vertex is inside the deque hull
00073         if (bot >= (int) D.size() || top - 1 >= (int) D.size() || i >= (int) V.size()) {
00074             throw ProcessError();
00075         }
00076         if ((isLeft(D[bot], D[bot + 1], V[i]) > 0) &&
00077                 (isLeft(D[top - 1], D[top], V[i]) > 0)) {
00078             continue;    // skip an interior vertex
00079         }
00080 
00081         // incrementally add an exterior vertex to the deque hull
00082         // get the rightmost tangent at the deque bot
00083         while (isLeft(D[bot], D[bot + 1], V[i]) <= 0) {
00084             ++bot;                // remove bot of deque
00085             if (bot >= (int) D.size()) {
00086                 throw ProcessError();
00087             }
00088         }
00089         if (bot == 0) {
00090             throw ProcessError();
00091         }
00092         D[--bot] = V[i];          // insert V[i] at bot of deque
00093 
00094         if (top == 0 || top >= (int) D.size()) {
00095             throw ProcessError();
00096         }
00097         // get the leftmost tangent at the deque top
00098         while (isLeft(D[top - 1], D[top], V[i]) <= 0) {
00099             --top;                // pop top of deque
00100             if (top == 0 || top >= (int) D.size()) {
00101                 throw ProcessError();
00102             }
00103         }
00104 
00105         if (top + 1 >= (int) D.size()) {
00106             throw ProcessError();
00107         }
00108         D[++top] = V[i];          // push V[i] onto top of deque
00109     }
00110 
00111     // transcribe deque D[] to the output hull array H[]
00112     int h;        // hull vertex counter
00113     PositionVector H;
00114     for (h = 0; h <= (top - bot); h++) {
00115         if (bot + h >= (int) D.size()) {
00116             throw ProcessError();
00117         }
00118         H.push_back_noDoublePos(D[bot + h]);
00119     }
00120     return H;
00121 }
00122 
00123 
00124 
00125 /****************************************************************************/
00126 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Defines