legal.c File Reference

#include <assert.h>
#include <float.h>
#include <math.h>
#include <limits.h>
#include <neatogen/neato.h>
#include <pathplan/pathutil.h>
#include <stddef.h>
#include <util/alloc.h>
#include <util/exit.h>

Include dependency graph for legal.c:

Go to the source code of this file.

Data Structures
struct	vertex
struct	polygon
struct	active_edge
struct	active_edge_list
struct	data

Macros
#define	SLOPE(p, q)   ( ( ( p.y ) - ( q.y ) ) / ( ( p.x ) - ( q.x ) ) )
#define	EQ_PT(v, w)   (((v).x == (w).x) && ((v).y == (w).y))
#define	after(v)   (((v)==((v)->poly->finish))?((v)->poly->start):((v)+1))
#define	prior(v)   (((v)==((v)->poly->start))?((v)->poly->finish):((v)-1))
#define	INBOX(p, bb)   ((p.x <= bb.UR.x) && (p.x >= bb.LL.x) && (p.y <= bb.UR.y) && (p.y >= bb.LL.y))
#define	NESTED(a, b)   (INBOX(a.LL,b) && INBOX(a.UR,b))

Typedefs
typedef struct active_edge	active_edge
typedef struct polygon	polygon
typedef struct active_edge_list	active_edge_list

Functions
static int	sign (double v)
static void	sgnarea (vertex *l, vertex *m, int i[])
static int	between (double f, double g, double h)
static int	online (vertex *l, vertex *m, int i)
static int	intpoint (vertex *l, vertex *m, double *x, double *y, int cond)
static void	putSeg (int i, vertex *v)
static int	realIntersect (vertex *firstv, vertex *secondv, pointf p)
static int	find_intersection (vertex *l, vertex *m)
static int	gt (const void *a, const void *b)
static int	find_ints (vertex vertex_list[], size_t nvertices)
static int	findInside (Ppoly_t **polys, int n_polys, polygon *polygon_list)
int	Plegal_arrangement (Ppoly_t **polys, int n_polys)

Macro Definition Documentation

after

#define after

(

v

)

(((v)==((v)->poly->finish))?((v)->poly->start):((v)+1))

Definition at line 25 of file legal.c.

EQ_PT

#define EQ_PT	(		v,
			w
	)		(((v).x == (w).x) && ((v).y == (w).y))

Definition at line 23 of file legal.c.

INBOX

#define INBOX	(		p,
			bb
	)		((p.x <= bb.UR.x) && (p.x >= bb.LL.x) && (p.y <= bb.UR.y) && (p.y >= bb.LL.y))

Definition at line 377 of file legal.c.

NESTED

#define NESTED	(		a,
			b
	)		(INBOX(a.LL,b) && INBOX(a.UR,b))

Definition at line 378 of file legal.c.

prior

#define prior

(

v

)

(((v)==((v)->poly->start))?((v)->poly->finish):((v)-1))

Definition at line 26 of file legal.c.

SLOPE

#define SLOPE	(		p,
			q
	)		( ( ( p.y ) - ( q.y ) ) / ( ( p.x ) - ( q.x ) ) )

Definition at line 21 of file legal.c.

Typedef Documentation

active_edge

typedef struct active_edge active_edge

Definition at line 28 of file legal.c.

active_edge_list

typedef struct active_edge_list active_edge_list

polygon

typedef struct polygon polygon

Definition at line 29 of file legal.c.

Function Documentation

between()

static int between ( double  f, double  g, double  h  )

static

where is g relative to the interval delimited by f and h?

The order of f and h is not assumed. That is, the interval defined may be (f, h) or (h, f) depending on whether f is less than or greater than h.

Parameters

f	First boundary of the interval
g	Value to test
h	Second boundary of the interval

Returns

-1 if g is not in the interval, 1 if g is in the interval, 0 if g is on the boundary (that is, equal to f or equal to h)

Definition at line 95 of file legal.c.

Referenced by online().

Here is the caller graph for this function:

find_intersection()

static int find_intersection ( vertex *  l, vertex *  m  )

static

Definition at line 233 of file legal.c.

References intpoint(), MAX, online(), realIntersect(), sgnarea(), pointf_s::x, and pointf_s::y.

Referenced by find_ints(), and find_ints().

Here is the call graph for this function:

Here is the caller graph for this function:

find_ints()

static int find_ints ( vertex  vertex_list[], size_t  nvertices  )

static

Definition at line 282 of file legal.c.

References vertex::active, after, agerrorf(), active_edge_list::final, find_intersection(), active_edge_list::first, free(), gt(), gv_alloc(), gv_calloc(), active_edge::last, active_edge::name, active_edge::next, active_edge_list::number, nvertices, and prior.

Referenced by Plegal_arrangement(), and Plegal_arrangement().

Here is the call graph for this function:

Here is the caller graph for this function:

findInside()

static int findInside ( Ppoly_t **  polys, int  n_polys, polygon *  polygon_list  )

static

Definition at line 386 of file legal.c.

References in_poly(), NESTED, and Ppoly_t::ps.

Referenced by Plegal_arrangement().

Here is the call graph for this function:

Here is the caller graph for this function:

gt()

static int gt ( const void *  a, const void *  b  )

static

Definition at line 260 of file legal.c.

Referenced by find_ints().

Here is the caller graph for this function:

intpoint()

static int intpoint ( vertex *  l, vertex *  m, double *  x, double *  y, int  cond  )

static

Definition at line 130 of file legal.c.

References after, le, online(), vertex::pos, SLOPE, pointf_s::x, and pointf_s::y.

Referenced by find_intersection().

Here is the call graph for this function:

Here is the caller graph for this function:

online()

static int online ( vertex *  l, vertex *  m, int  i  )

static

Definition at line 118 of file legal.c.

References after, between(), vertex::pos, pointf_s::x, and pointf_s::y.

Referenced by find_intersection(), and intpoint().

Here is the call graph for this function:

Here is the caller graph for this function:

Plegal_arrangement()

int Plegal_arrangement	(	Ppoly_t **	polys,
		int	n_polys
	)

Definition at line 413 of file legal.c.

References vertex::active, polygon::bb, find_ints(), findInside(), polygon::finish, free(), gv_calloc(), boxf::LL, Ppoly_t::pn, vertex::poly, vertex::pos, Ppoly_t::ps, polygon::start, boxf::UR, pointf_s::x, Pxy_t::x, pointf_s::y, and Pxy_t::y.

Referenced by compoundEdges(), spline_edges_(), and vc_refresh().

Here is the call graph for this function:

Here is the caller graph for this function:

putSeg()

static void putSeg ( int  i, vertex *  v  )

static

Definition at line 195 of file legal.c.

References after, vertex::pos, pointf_s::x, and pointf_s::y.

Referenced by realIntersect().

Here is the caller graph for this function:

realIntersect()

static int realIntersect ( vertex *  firstv, vertex *  secondv, pointf  p  )

static

Definition at line 205 of file legal.c.

References after, EQ_PT, vertex::pos, putSeg(), Verbose, pointf_s::x, and pointf_s::y.

Referenced by find_intersection().

Here is the call graph for this function:

Here is the caller graph for this function:

sgnarea()

static void sgnarea ( vertex *  l, vertex *  m, int  i[]  )

static

Definition at line 65 of file legal.c.

References after, vertex::pos, sign(), pointf_s::x, and pointf_s::y.

Referenced by find_intersection().

Here is the call graph for this function:

Here is the caller graph for this function:

sign()

static int sign ( double  v )

static

Definition at line 54 of file legal.c.

Referenced by _sfcvt(), countHorzCross(), countVertCross(), sfprint(), and sgnarea().

Here is the caller graph for this function: