Helper_ConvexHull.h File Reference

---

Detailed Description

Author:

Daniel Krajzewicz

Date:

Fri, 29.04.2005

Version:

Id

Helper_ConvexHull.h 8236 2010-02-10 11:16:41Z behrisch

Definition in file Helper_ConvexHull.h.

#include <config.h>
#include "Position2D.h"
#include "Position2DVector.h"
#include <vector>

Go to the source code of this file.

Functions
SUMOReal	isLeft (const Position2D &P0, const Position2D &P1, const Position2D &P2)
Position2DVector	simpleHull_2D (const Position2DVector &V)

---

Function Documentation

SUMOReal isLeft	(	const Position2D &	P0,
		const Position2D &	P1,
		const Position2D &	P2
	)			[inline]

Definition at line 60 of file Helper_ConvexHull.h.

References Position2D::x(), and Position2D::y().

Referenced by simpleHull_2D().

                             {
    return (P1.x() - P0.x())*(P2.y() - P0.y()) - (P2.x() - P0.x())*(P1.y() - P0.y());
}

Position2DVector simpleHull_2D

(

const Position2DVector &

V

)

Definition at line 49 of file Helper_ConvexHull.cpp.

References isLeft(), Position2DVector::push_back_noDoublePos(), and Position2DVector::size().

Referenced by Position2DVector::convexHull().

                                         {
    if (V.size()<3) {
        throw ProcessError();
    }
    // initialize a deque D[] from bottom to top so that the
    // 1st three vertices of V[] are a counterclockwise triangle
    int n = (int) V.size();
    std::vector<Position2D> D(2*n+1);
    int bot = n-2, top = bot+3;   // initial bottom and top deque indices
    D[bot] = D[top] = V[2];       // 3rd vertex is at both bot and top
    if (isLeft(V[0], V[1], V[2]) > 0) {
        D[bot+1] = V[0];
        D[bot+2] = V[1];          // ccw vertices are: 2,0,1,2
    } else {
        D[bot+1] = V[1];
        D[bot+2] = V[0];          // ccw vertices are: 2,1,0,2
    }

    // compute the hull on the deque D[]
    for (int i=3; i < n; i++) {   // process the rest of vertices
        // test if next vertex is inside the deque hull
        if (bot>=(int) D.size()||top-1>=(int) D.size()||i>=(int) V.size()) {
            throw ProcessError();
        }
        if ((isLeft(D[bot], D[bot+1], V[i]) > 0) &&
                (isLeft(D[top-1], D[top], V[i]) > 0))
            continue;         // skip an interior vertex

        // incrementally add an exterior vertex to the deque hull
        // get the rightmost tangent at the deque bot
        while (isLeft(D[bot], D[bot+1], V[i]) <= 0) {
            ++bot;                // remove bot of deque
            if (bot>=(int) D.size()) {
                throw ProcessError();
            }
        }
        if (bot==0) {
            throw ProcessError();
        }
        D[--bot] = V[i];          // insert V[i] at bot of deque

        if (top==0||top>=(int) D.size()) {
            throw ProcessError();
        }
        // get the leftmost tangent at the deque top
        while (isLeft(D[top-1], D[top], V[i]) <= 0) {
            --top;                // pop top of deque
            if (top==0||top>=(int) D.size()) {
                throw ProcessError();
            }
        }

        if (top+1>=(int) D.size()) {
            throw ProcessError();
        }
        D[++top] = V[i];          // push V[i] onto top of deque
    }

    // transcribe deque D[] to the output hull array H[]
    int h;        // hull vertex counter
    Position2DVector H;
    for (h=0; h <= (top-bot); h++) {
        if (bot + h>=(int) D.size()) {
            throw ProcessError();
        }
        H.push_back_noDoublePos(D[bot + h]);
    }
    return H;
}