SUMO - Simulation of Urban MObility
|
00001 /****************************************************************************/ 00008 // 00009 /****************************************************************************/ 00010 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/ 00011 // Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors 00012 /****************************************************************************/ 00013 // 00014 // This file is part of SUMO. 00015 // SUMO is free software: you can redistribute it and/or modify 00016 // it under the terms of the GNU General Public License as published by 00017 // the Free Software Foundation, either version 3 of the License, or 00018 // (at your option) any later version. 00019 // 00020 /****************************************************************************/ 00021 #ifndef Helper_ConvexHull_h 00022 #define Helper_ConvexHull_h 00023 00024 00025 // =========================================================================== 00026 // included modules 00027 // =========================================================================== 00028 00029 00030 #ifdef _MSC_VER 00031 #include <windows_config.h> 00032 #else 00033 #include <config.h> 00034 #endif 00035 00036 #include "Position.h" 00037 #include "PositionVector.h" 00038 #include <vector> 00039 00040 // Copyright 2002, softSurfer (www.softsurfer.com) 00041 // This code may be freely used and modified for any purpose 00042 // providing that this copyright notice is included with it. 00043 // SoftSurfer makes no warranty for this code, and cannot be held 00044 // liable for any real or imagined damage resulting from its use. 00045 // Users of this code must verify correctness for their application. 00046 00047 00048 // Assume that a class is already given for the object: 00049 // Position with coordinates {SUMOReal x, y;} 00050 //=================================================================== 00051 00052 00053 // isLeft(): test if a Position is Left|On|Right of an infinite line. 00054 // Input: three Positions P0, P1, and P2 00055 // Return: >0 for P2 left of the line through P0 and P1 00056 // =0 for P2 on the line 00057 // <0 for P2 right of the line 00058 // See: the January 2001 Algorithm on Area of Triangles 00059 00060 00061 inline SUMOReal 00062 isLeft(const Position& P0, 00063 const Position& P1, 00064 const Position& P2) { 00065 return (P1.x() - P0.x()) * (P2.y() - P0.y()) - (P2.x() - P0.x()) * (P1.y() - P0.y()); 00066 } 00067 00068 00069 PositionVector 00070 simpleHull_2D(const PositionVector& V); 00071 00072 00073 #endif 00074 00075 /****************************************************************************/ 00076