SUMO - Simulation of Urban MObility
Helper_ConvexHull.h
Go to the documentation of this file.
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 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Defines