Graphviz 14.0.0~dev.20250918.0130
Loading...
Searching...
No Matches
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: