shortest.c File Reference

#include <assert.h>
#include <cgraph/list.h>
#include <cgraph/prisize_t.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <pathplan/pathutil.h>
#include <pathplan/tri.h>

Include dependency graph for shortest.c:

Go to the source code of this file.

Data Structures
struct	pointnlink_t
struct	tedge_t
struct	triangle_t
struct	deque_t

Macros
#define	DQ_FRONT   1
#define	DQ_BACK   2
#define	prerror(msg)    fprintf (stderr, "lib/pathplan/%s:%d: %s\n", __FILE__, __LINE__, (msg))
#define	POINTSIZE   sizeof (Ppoint_t)
#define	POINTNLINKSIZE   sizeof (pointnlink_t)
#define	POINTNLINKPSIZE   sizeof (pointnlink_t *)

Typedefs
typedef struct pointnlink_t	pointnlink_t
typedef struct triangle_t	triangle_t
typedef struct deque_t	deque_t

Functions
static int	triangulate (pointnlink_t **, int)
static int	loadtriangle (pointnlink_t *, pointnlink_t *, pointnlink_t *)
static void	connecttris (size_t, size_t)
static bool	marktripath (size_t, size_t)
static void	add2dq (deque_t *dq, int, pointnlink_t *)
static void	splitdq (deque_t *dq, int, size_t)
static size_t	finddqsplit (const deque_t *dq, pointnlink_t *)
static int	pointintri (size_t, Ppoint_t *)
static int	growops (size_t)
static Ppoint_t	point_indexer (void *base, int index)
int	Pshortestpath (Ppoly_t *polyp, Ppoint_t eps[2], Ppolyline_t *output)

Variables
static triangles_t	tris
static Ppoint_t *	ops
static size_t	opn

Macro Definition Documentation

DQ_BACK

#define DQ_BACK   2

Definition at line 24 of file shortest.c.

DQ_FRONT

#define DQ_FRONT   1

Definition at line 23 of file shortest.c.

POINTNLINKPSIZE

#define POINTNLINKPSIZE   sizeof (pointnlink_t *)

Definition at line 37 of file shortest.c.

POINTNLINKSIZE

#define POINTNLINKSIZE   sizeof (pointnlink_t)

Definition at line 36 of file shortest.c.

POINTSIZE

#define POINTSIZE   sizeof (Ppoint_t)

Definition at line 29 of file shortest.c.

prerror

#define prerror

(

msg

)

fprintf (stderr, "lib/pathplan/%s:%d: %s\n", __FILE__, __LINE__, (msg))

Definition at line 26 of file shortest.c.

Typedef Documentation

deque_t

typedef struct deque_t deque_t

pointnlink_t

typedef struct pointnlink_t pointnlink_t

triangle_t

typedef struct triangle_t triangle_t

Function Documentation

add2dq()

static void add2dq ( deque_t *  dq, int  side, pointnlink_t *  pnlp  )

static

Definition at line 401 of file shortest.c.

References DQ_FRONT, deque_t::fpnlpi, pointnlink_t::link, deque_t::lpnlpi, and deque_t::pnlps.

Referenced by Pshortestpath().

Here is the caller graph for this function:

connecttris()

static void connecttris ( size_t  tri1, size_t  tri2  )

static

Definition at line 366 of file shortest.c.

References triangle_t::e, tedge_t::pnl0p, tedge_t::pnl1p, pointnlink_t::pp, tedge_t::right_index, and tris.

Referenced by Pshortestpath().

Here is the caller graph for this function:

finddqsplit()

static size_t finddqsplit ( const deque_t *  dq, pointnlink_t *  pnlp  )

static

Definition at line 422 of file shortest.c.

References deque_t::apex, ccw(), deque_t::fpnlpi, ISCCW, ISCW, deque_t::lpnlpi, deque_t::pnlps, and pointnlink_t::pp.

Referenced by Pshortestpath().

Here is the call graph for this function:

Here is the caller graph for this function:

growops()

static int growops ( size_t  newopn )

static

Definition at line 442 of file shortest.c.

References NULL, opn, ops, POINTSIZE, and prerror.

Referenced by Pshortestpath().

Here is the caller graph for this function:

loadtriangle()

static int loadtriangle ( pointnlink_t *  pnlap, pointnlink_t *  pnlbp, pointnlink_t *  pnlcp  )

static

Definition at line 349 of file shortest.c.

References triangle_t::e, tedge_t::pnl0p, tedge_t::pnl1p, prerror, tedge_t::right_index, SIZE_MAX, and tris.

Referenced by triangulate().

Here is the caller graph for this function:

marktripath()

static bool marktripath ( size_t  trii, size_t  trij  )

static

Definition at line 384 of file shortest.c.

References mark(), marktripath(), SIZE_MAX, and tris.

Referenced by marktripath(), and Pshortestpath().

Here is the call graph for this function:

Here is the caller graph for this function:

point_indexer()

static Ppoint_t point_indexer ( void *  base, int  index  )

static

Definition at line 75 of file shortest.c.

References pointnlink_t::pp.

Referenced by triangulate().

Here is the caller graph for this function:

pointintri()

static int pointintri ( size_t  trii, Ppoint_t *  pp  )

static

Definition at line 432 of file shortest.c.

References ccw(), ISCW, and tris.

Referenced by Pshortestpath().

Here is the call graph for this function:

Here is the caller graph for this function:

Pshortestpath()

int Pshortestpath	(	Ppoly_t *	polyp,
		Ppoint_t	eps[2],
		Ppolyline_t *	output
	)

Definition at line 85 of file shortest.c.

References add2dq(), deque_t::apex, ccw(), connecttris(), DQ_BACK, DQ_FRONT, triangle_t::e, finddqsplit(), deque_t::fpnlpi, free(), growops(), ISCCW, pointnlink_t::link, deque_t::lpnlpi, triangle_t::mark, marktripath(), NULL, ops, Ppoly_t::pn, tedge_t::pnl0p, tedge_t::pnl1p, deque_t::pnlpn, deque_t::pnlps, pointintri(), POINTNLINKPSIZE, pointnlink_t::pp, prerror, PRISIZE_T, Ppoly_t::ps, tedge_t::right_index, SIZE_MAX, splitdq(), triangulate(), tris, Pxy_t::x, and Pxy_t::y.

Referenced by genroute(), routesplines_(), and simpleSplineRoute().

Here is the call graph for this function:

Here is the caller graph for this function:

splitdq()

static void splitdq ( deque_t *  dq, int  side, size_t  index  )

static

Definition at line 415 of file shortest.c.

References DQ_FRONT, deque_t::fpnlpi, and deque_t::lpnlpi.

Referenced by Pshortestpath().

Here is the caller graph for this function:

triangulate()

static int triangulate ( pointnlink_t **  points, int  point_count  )

static

Definition at line 321 of file shortest.c.

References isdiagonal(), loadtriangle(), point_indexer(), points, prerror, and triangulate().

Referenced by Pshortestpath(), and triangulate().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

opn

size_t opn

static

Definition at line 60 of file shortest.c.

Referenced by growops().

ops

Ppoint_t* ops

static

Definition at line 59 of file shortest.c.

Referenced by growops(), and Pshortestpath().

tris

triangles_t tris

static

Definition at line 57 of file shortest.c.

Referenced by connecttris(), loadtriangle(), marktripath(), mkTriIndices(), pointintri(), and Pshortestpath().