<< NL_V_FitEllipsePlot NL_V: Vision NL_V_ImageShow >>

NARVAL >> NL_V: Vision > NL_V_GrahamScan

NL_V_GrahamScan

Compute the Graham scan on a cloud of points.

Calling Sequence

[G] = NL_V_GrahamScan(P)

Arguments

P :

List of points (coordinates).

G :

Convex hull.

Description

NL_V_GrahamScan compute the Graham scan (WIKIPEDIA) on the cloud of points P (matrix of coordinates [P1x P1y;P2x P2y;...]). The convex hull is stored in (matrix of coordinates [G1x G1y;G2x G2y;...]).

Pseudo-Code (Wikipedia)

# Three points are a counter-clockwise turn if ccw > 0, clockwise if
# ccw inferior to 0, and collinear if ccw = 0 because ccw is a determinant that
# gives twice the signed  area of the triangle formed by p1, p2 and p3.
function ccw(p1, p2, p3):
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)

let N = number of points
let points[N+1] = the array of points
swap points[1] with the point with the lowest y-coordinate
sort points by polar angle with points[1]

# We want points[0] to be a sentinel point that will stop the loop.
let points[0] = points[N]

# M will denote the number of points on the convex hull.
let M = 1
for i = 2 to N:
    # Find next valid point on convex hull.
    while ccw(points[M-1], points[M], points[i]) inferior or equal to 0:
        if M superior to 1:
            M -= 1
        # All points are collinear
        else if i == N:
            break
        else
            i += 1

    # Update M and swap points[i] to the correct place.
    M += 1
    swap points[M] with points[i]

Examples

[path]=NL_F_NLPath();//path to NARVAL module
path=path+'/demos/';//folder path
[x,y]=NL_V_LoadBody2D(path);
scf();
plot2d(x,y,style=0);
[G]=NL_V_GrahamScan([x y]);//application of NL_V_GrahamScan
xpoly(G(:,1),G(:,2));

Dependency

NL_V_AngleP1P2P0, NL_F_SortRows, NL_V_DotP1P2P0

Report an issue
<< NL_V_FitEllipsePlot NL_V: Vision NL_V_ImageShow >>