shortest.c File Reference

#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>
#include <pathplan/pathutil.h>
#include <pathplan/tri.h>
#include <util/list.h>
#include <util/prisize_t.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	LIST (triangle_t)
int	Pshortestpath (Ppoly_t *polyp, Ppoint_t eps[2], Ppolyline_t *output)
static int	triangulate (pointnlink_t **points, size_t point_count)
static int	loadtriangle (pointnlink_t *pnlap, pointnlink_t *pnlbp, pointnlink_t *pnlcp)
static void	connecttris (size_t tri1, size_t tri2)
static bool	marktripath (size_t trii, size_t trij)
static void	add2dq (deque_t *dq, int side, pointnlink_t *pnlp)
static void	splitdq (deque_t *dq, int side, size_t index)
static size_t	finddqsplit (const deque_t *dq, pointnlink_t *pnlp)
static int	pointintri (size_t trii, Ppoint_t *pp)
static int	growops (size_t newopn)

Macro Definition Documentation

DQ_BACK

#define DQ_BACK   2

Definition at line 22 of file shortest.c.

DQ_FRONT

#define DQ_FRONT   1

Definition at line 21 of file shortest.c.

POINTNLINKPSIZE

#define POINTNLINKPSIZE   sizeof (pointnlink_t *)

Definition at line 35 of file shortest.c.

POINTNLINKSIZE

#define POINTNLINKSIZE   sizeof (pointnlink_t)

Definition at line 34 of file shortest.c.

POINTSIZE

#define POINTSIZE   sizeof (Ppoint_t)

Definition at line 27 of file shortest.c.

prerror

#define prerror

(

msg

)

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

Definition at line 24 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 394 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 359 of file shortest.c.

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

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 415 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 435 of file shortest.c.

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

Referenced by Pshortestpath().

Here is the caller graph for this function:

LIST()

static LIST ( triangle_t  )

static

Definition at line 53 of file shortest.c.

loadtriangle()

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

static

Definition at line 342 of file shortest.c.

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

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 377 of file shortest.c.

References LIST_AT, LIST_GET, mark(), marktripath(), and SIZE_MAX.

Referenced by marktripath(), and Pshortestpath().

Here is the call graph for this function:

Here is the caller graph for this function:

pointintri()

static int pointintri ( size_t  trii, Ppoint_t *  pp  )

static

Definition at line 425 of file shortest.c.

References ccw(), ISCW, and LIST_GET.

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 81 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, LIST_AT, LIST_CLEAR, LIST_GET, LIST_SIZE, 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(), 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 408 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, size_t  point_count  )

static

Definition at line 316 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: