SUMO - Simulation of Urban MObility
|
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