File Poly.cu

#include "Poly.h"

Public Functions

Type	Name
Polygon	CounterCWPoly (Polygon Poly) check polygon handedness and reverse if necessary.
bool	PolygonIntersect (Polygon P, Polygon Q) Intersection between two polygons.
bool	SegmentIntersect (Polygon P, Polygon Q) Intersection between segments.
Vertex	VertAdd (Vertex A, Vertex B) Add two vertices.
Vertex	VertSub (Vertex A, Vertex B) Subtract two vertices.
bool	blockinpoly (T xo, T yo, T dx, int blkwidth, Polygon Poly) Check whether a block is inside or intersects a polygon.
template bool	blockinpoly< double > (double xo, double yo, double dx, int blkwidth, Polygon Poly)
template bool	blockinpoly< float > (float xo, float yo, float dx, int blkwidth, Polygon Poly)
int	cn_PnPoly (T Px, T Py, F * Vx, F * Vy, int n) Crossing number test for a point in a polygon.
double	dotprod (Vertex A, Vertex B) Compute dot product of two vertices.
T	isLeft (T P0x, T P0y, T P1x, T P1y, T P2x, T P2y) Tests if a point is Left\|On\|Right of an infinite line.
bool	test_SegmentIntersect () Test segment intersection function.
bool	test_intersectpoly () Test polygon intersection function.
bool	test_wninpoly () Test winding number inpoly function.
int	wn_PnPoly (T Px, T Py, T * Vx, T * Vy, unsigned int n) winding number test for a point in a polygon
int	wn_PnPoly (T Px, T Py, Polygon Poly) winding number test for a point in a polygon
template int	wn_PnPoly< double > (double Px, double Py, Polygon Poly)
template int	wn_PnPoly< float > (float Px, float Py, Polygon Poly)
double	xprod (Vertex A, Vertex B) Compute cross product of two vertices.

Public Functions Documentation

function CounterCWPoly

check polygon handedness and reverse if necessary.

Polygon CounterCWPoly (
    Polygon Poly
)

Description

check polygon handedness and enforce left-handesness (Counter-clockwise). This function is used to ensure the right polygon handedness for the winding number inpoly (using the isleft())

function PolygonIntersect

Intersection between two polygons.

bool PolygonIntersect (
    Polygon P,
    Polygon Q
)

Checks whether two polygons intersect by testing all segment pairs. The function checks whether each segment of Polygon P intersect any segment of Poly Q. If an intersection is detected, returns true immediately.

Parameters:

P First polygon
Q Second polygon

Returns:

True if polygons intersect, false otherwise

function SegmentIntersect

Intersection between segments.

bool SegmentIntersect (
    Polygon P,
    Polygon Q
)

Checks whether two polygon segments intersect. Polygon P and Q are only 2 vertex long each. i.e. they represent a segment each.

Where does this come from:

https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect Best answer from Gareth Rees

Parameters:

P First segment as Polygon
Q Second segment as Polygon

Returns:

True if segments intersect, false otherwise

function VertAdd

Add two vertices.

Vertex VertAdd (
    Vertex A,
    Vertex B
)

Returns the sum of two Vertex objects.

Parameters:

A First vertex
B Second vertex

Returns:

Sum vertex

function VertSub

Subtract two vertices.

Vertex VertSub (
    Vertex A,
    Vertex B
)

Returns the difference of two Vertex objects.

Parameters:

A First vertex
B Second vertex

Returns:

Difference vertex

function blockinpoly

Check whether a block is inside or intersects a polygon.

template<class T>
bool blockinpoly (
    T xo,
    T yo,
    T dx,
    int blkwidth,
    Polygon Poly
)

Determines if any corner of the block is inside the polygon or if the block intersects the polygon.

Template parameters:

T Coordinate type

Parameters:

xo Block origin x
yo Block origin y
dx Block cell size
blkwidth Block width
Poly Polygon to test

Returns:

True if block is inside or intersects polygon, false otherwise

function blockinpoly< double >

template bool blockinpoly< double > (
    double xo,
    double yo,
    double dx,
    int blkwidth,
    Polygon Poly
)

function blockinpoly< float >

template bool blockinpoly< float > (
    float xo,
    float yo,
    float dx,
    int blkwidth,
    Polygon Poly
)

function cn_PnPoly

Crossing number test for a point in a polygon.

template<class T, class F>
int cn_PnPoly (
    T Px,
    T Py,
    F * Vx,
    F * Vy,
    int n
)

Determines if a point is inside a polygon using the crossing number algorithm. cn_PnPoly(): crossing number test for a point in a polygon Input: P = a point, V[] = vertex points of a polygon V[n+1] with V[n]=V[0] Return: 0 = outside, 1 = inside

Where does this come from:

Original Licence

This code may be freely used and modified for any purpose providing that this copyright notice is included with it. SoftSurfer makes no warranty for this code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code must verify correctness for their application. Code modified to fit the use in DisperGPU

This code is patterned after [Franklin, 2000]

Template parameters:

T Point coordinate type
F Vertex coordinate type

Parameters:

Px X coordinate of point
Py Y coordinate of point
Vx Array of polygon vertex X coordinates
Vy Array of polygon vertex Y coordinates
n Number of vertices

Returns:

1 if inside, 0 if outside

function dotprod

Compute dot product of two vertices.

double dotprod (
    Vertex A,
    Vertex B
)

Calculates the dot product of two Vertex objects.

Parameters:

A First vertex
B Second vertex

Returns:

Dot product value

function isLeft

Tests if a point is Left|On|Right of an infinite line.

template<class T>
T isLeft (
    T P0x,
    T P0y,
    T P1x,
    T P1y,
    T P2x,
    T P2y
)

Returns >0 for P2 left of the line through P0 and P1, =0 for P2 on the line, <0 for P2 right of the line. See: Algorithm 1 "Area of Triangles and Polygons"

Where does this come from:

Original Licence

This code may be freely used and modified for any purpose providing that this copyright notice is included with it. SoftSurfer makes no warranty for this code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code must verify correctness for their application. Code modified to fit the use in DisperGPU

Template parameters:

T Coordinate type

Parameters:

P0x X of first point
P0y Y of first point
P1x X of second point
P1y Y of second point
P2x X of test point
P2y Y of test point

Returns:

Relative position value

function test_SegmentIntersect

Test segment intersection function.

bool test_SegmentIntersect ()

Tests the segment intersection function for known cases.

Returns:

True if test passes, false otherwise

function test_intersectpoly

Test polygon intersection function.

bool test_intersectpoly ()

Tests the polygon intersection function for known cases.

Returns:

True if test passes, false otherwise

function test_wninpoly

Test winding number inpoly function.

bool test_wninpoly ()

Tests the winding number function for a block polygon.

Returns:

True if test passes, false otherwise

function wn_PnPoly

winding number test for a point in a polygon

template<class T>
int wn_PnPoly (
    T Px,
    T Py,
    T * Vx,
    T * Vy,
    unsigned int n
)

Description

wn_PnPoly(): winding number test for a point in a polygon Input: P = a point, V[] = vertex points of a polygon V[n+1] with V[n]=V[0] Return: wn = the winding number (=0 only when P is outside)

Where does this come from:

Original Licence

This code may be freely used and modified for any purpose providing that this copyright notice is included with it. SoftSurfer makes no warranty for this code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code must verify correctness for their application. Code modified to fit the use in DisperGPU

function wn_PnPoly

winding number test for a point in a polygon

template<class T>
int wn_PnPoly (
    T Px,
    T Py,
    Polygon Poly
)

Description

wn_PnPoly(): winding number test for a point in a polygon Input: P = a point, V[] = vertex points of a polygon V[n+1] with V[n]=V[0] Return: wn = the winding number (=0 only when P is outside)

Where does this come from:

Original Licence

This code may be freely used and modified for any purpose providing that this copyright notice is included with it. SoftSurfer makes no warranty for this code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code must verify correctness for their application. Code modified to fit the use in DisperGPU

function wn_PnPoly< double >

template int wn_PnPoly< double > (
    double Px,
    double Py,
    Polygon Poly
)

function wn_PnPoly< float >

template int wn_PnPoly< float > (
    float Px,
    float Py,
    Polygon Poly
)

function xprod

Compute cross product of two vertices.

double xprod (
    Vertex A,
    Vertex B
)

Calculates the cross product of two Vertex objects.

Parameters:

A First vertex
B Second vertex

Returns:

Cross product value

The documentation for this class was generated from the following file src/Poly.cu