#ifndef cirpack_H
#define cirpack_H

/* Routines for circle packing. */
/* Last edited on 2005-02-04 06:30:43 by stolfi */

#include <i2.h>
#include <r2.h>
#include <vec.h>
#include <interval.h>
#include <cpkbasic.h>
#include <ps.h>
#include <stdio.h>
#include <stdlib.h>

r2_vec_t cpk_get_valid_points
  ( r2_t o,         /* Grid's reference point. */
    r2_t u,         /* Grid's X axis. */
    double step,    /* Grid step. */
    r2_vec_t R,     /* Vertices of polygon, ccw around interior. */
    r2_vec_t P,     /* Forbidden points. */
    double dP,      /* Minimum distance from forbidden points. */
    r2_vec_t L,     /* Vertices of forbidden polygonal lines. */
    double dL       /* Minimum distance from forbidden lines. */
  );
  /* Returns the list {V} of all points from a certain grid {G} that
    lie inside a given polygon {R}, are at least {dP} away from a
    given set of points {P}, and at least {dL} away from given
    polygonal line(s) {L}.
    
    The grid {G} is an hexagonal grid that includes the point {o}
    and such that the distance between nearest points is {step} along
    the direction of vector {u}.
    
    The enclosing polygon is specified by its vertices {R[0..]}. The
    even-odd rule is used to determine the interior points, so holes
    can be obtained by including their vertices too in the list {R}.
    The list {R} is assumed to be circular, so the polygon is always
    closed.
    
    Similarly, the forbidden polygonal lines are defined by their
    vertices {L[0..]}. Like {R}, the list {L} is implicitly closed.
    However open and/or multiple lines can be specified by inserting 
    a dummy vertex with infinite coordinates after each connected piece. */

i2_vec_t cpk_incompat_edges (r2_vec_t V, double d_min);
  /* Given a list of points {V[0..]}, returns a list of all 
    pairs {(i,j)} such that {i<j} and {dist(V[i],V[j]) < d_min}. */

r2_vec_t cpk_get_candidates
  ( r2_vec_t p,    /* Vertices of polygon, ccw around interior. */
    r2_vec_t f,    /* Fixed sites. */
    double d_min,  /* Minimum distance between sites. */
    double d_ext,  /* Minimum distance from exterior. */
    double step,   /* Granularity of locations. */
    r2_t u         /* Direction for greedy heuristic. */
  );
  /* Given a polygon {p} and a list {f} of /sites/ (points of R^2),
    returns a list {g[0..n-1]} of new sites such that 

      (1) {dist(g[i],g[j]) \geq d_min} for any {i\neq j};
      (2) {dist(g[i],f[j]} \geq d_min} for any {i,j};
      (3) {dist(g[i],q) \geq d_ext} for any {i} and any point {q} outside {p}.
    
    The procedure tries to maximize the number of new sites by a
    greedy heuristic using a sweepline perpendicular to {u}. The new
    sites are confined to a hexagonal grid with shortest edge
    {step}. */


r2_vec_t cpk_pack_sites
  ( r2_vec_t p,      /* Vertices of polygon, ccw around interior. */
    r2_vec_t f,      /* Fixed sites. */
    double d_min,    /* Minimum distance between sites. */
    double d_ext,    /* Minimum distance from exterior. */
    double step,     /* Granularity of locations. */
    r2_t u           /* Direction for greedy heuristic. */
  );
  /* Given a polygon {p} and a list {f} of /sites/ (points of R^2),
    returns a list {c[0..n-1]} of new sites such that 

      (1) {dist(c[i],c[j]) \geq d_min} for any {i\neq j};
      (2) {dist(c[i],f[j]} \geq d_min} for any {i,j};
      (3) {dist(c[i],q) \geq d_ext} for any {i} and any point {q} outside {p}.
    
    The procedure tries to maximize the number of new sites by a
    greedy heuristic using a sweepline perpendicular to {u}. The new
    sites are confined to a hexagonal grid with shortest edge
    {step}. */

#endif