43 return sqrtf(
sq(a[0]-b[0]) +
sq(a[1]-b[1]));
60 for (
int i = 0; i < sz; i++)
70 double z[2] = { 0, 0 };
72 for (
int i = 0; i < sz; i++)
82 double total_theta = 0;
83 double last_theta = 0;
89 for (
int i = 0; i <= sz; i++) {
94 double this_theta = atan2(p1[1]-p0[1], p1[0]-p0[0]);
97 double dtheta =
mod2pi(this_theta-last_theta);
98 total_theta += dtheta;
101 last_theta = this_theta;
104 int ccw = (total_theta > 0);
108 for (
int i = 0; i < sz / 2; i++) {
126 double acc_theta = 0;
130 for (
int i = 0; i <= psz; i++) {
135 double this_theta = atan2(q[1]-p[1], q[0]-p[0]);
138 acc_theta +=
mod2pi(this_theta - last_theta);
140 last_theta = this_theta;
143 return acc_theta >
M_PI;
202 double *pleft = NULL;
203 for (
int i = 0; i < insz; i++) {
207 if (pleft == NULL || p[0] < pleft[0])
212 assert(pleft != NULL);
227 double n0 = 0, n1 = 0;
234 for (
int i = 0; i < insz; i++) {
249 double e0 = thisq[0] - p[0], e1 = thisq[1] - p[1];
250 double dot = e0*n0 + e1*n1;
276 double e0 = o[0] - p[0];
277 double e1 = o[1] - p[1];
279 if (n0*e0 + n1*e1 == 0)
299 double min_dist = HUGE_VALF;
301 for (
int i = 0; i < psz; i++) {
314 if (dist < min_dist) {
315 memcpy(p, thisp,
sizeof(
double[2]));
332 for (
int i = 0; i <= psz; i++) {
351 quadrant = (p[1] < q[1]) ? 2 : 1;
353 quadrant = (p[1] < q[1]) ? 3 : 0;
356 int dquadrant = quadrant - last_quadrant;
385 double nx = p[1] - q[1];
386 double ny = -p[0] + q[0];
388 double dot = nx*(p0[0]-q[0]) + ny*(p0[1]-q[1]);
399 last_quadrant = quadrant;
402 int v = (quad_acc >= 2) || (quad_acc <= -2);
405 printf(
"FAILURE %d %d\n", v, quad_acc);
416 line->
u[0] = p1[0]-p0[0];
417 line->
u[1] = p1[1]-p0[1];
418 double mag = sqrtf(
sq(line->
u[0]) +
sq(line->
u[1]));
426 return (q[0]-line->
p[0])*line->
u[0] + (q[1]-line->
p[1])*line->
u[1];
437 double m00, m01, m10, m11;
447 double det = m00*m11-m01*m10;
450 if (fabs(det) < 0.00000001)
457 b00 = lineb->
p[0] - linea->
p[0];
458 b10 = lineb->
p[1] - linea->
p[1];
461 x00 = i00*b00+i01*b10;
464 p[0] = linea->
u[0]*x00 + linea->
p[0];
465 p[1] = linea->
u[1]*x00 + linea->
p[1];
510 if ((c<a && c<b) || (c>a && c>b))
518 if ((c<a && c<b) || (c>a && c>b))
544 if ((c<a && c<b) || (c>a && c>b))
562 double pa0[2], pa1[2];
570 double pb0[2], pb1[2];
604 double a[2], b[2], c[2];
610 p[0] = (a[0]+b[0]+c[0])/3;
611 p[1] = (a[1]+b[1]+c[1])/3;
638 double a = *((
double*) _a);
639 double b = *((
double*) _b);
687 double p0[2] = { 0, y };
688 double p1[2] = { 1, y };
695 for (
int i = 0; i < sz; i++) {
726 int main(
int argc,
char *argv[])
763 {0,0}, {4,0}, {4, 1}, {1,1},
764 {1,2}, {3,2}, {3,3}, {1,3},
765 {1,4}, {4,4}, {4,5}, {0,5}}, 12);
774 for (
int i = 0; i < niters; i++) {
776 q[0] = 10.0f * random() / RAND_MAX - 2;
777 q[1] = 10.0f * random() / RAND_MAX - 2;
784 for (
int i = 0; i < niters; i++) {
786 q[0] = 10.0f * random() / RAND_MAX - 2;
787 q[1] = 10.0f * random() / RAND_MAX - 2;
794 for (
int i = 0; i < niters; i++) {
796 q[0] = 10.0f * random() / RAND_MAX - 2;
797 q[1] = 10.0f * random() / RAND_MAX - 2;
812 for (
double y = 5.2; y >= -.5; y -= res) {
818 for (
double x = -3; x < 6; x += res) {
819 while (x > xs[xpos] && xpos < xsz) {
831 for (
double x = -3; x < 6; x += res) {
832 double q[2] = {x, y};
854 double q[2] = { 10, 10 };
863 q[0] = 1.2; q[1] = 2.1;
881 printf(
"%15f, %15f\n", h[0], h[1]);
885 for (
int i = 0; i < 100000; i++) {
888 for (
int j = 0; j < 100; j++) {
890 q[0] = 10.0f * random() / RAND_MAX - 2;
891 q[1] = 10.0f * random() / RAND_MAX - 2;
int g2d_polygon_intersects_polygon(const zarray_t *polya, const zarray_t *polyb)
void g2d_polygon_get_interior_point(const zarray_t *poly, double *p)
int g2d_line_intersect_line(const g2d_line_t *linea, const g2d_line_t *lineb, double *p)
static void zarray_get_volatile(const zarray_t *za, int idx, void *p)
double g2d_line_get_coordinate(const g2d_line_t *line, const double q[2])
static void timeprofile_stamp(timeprofile_t *tp, const char *name)
void g2d_polygon_closest_boundary_point(const zarray_t *poly, const double q[2], double *p)
static int zarray_size(const zarray_t *za)
static int double_sort_up(const void *_a, const void *_b)
static void zarray_destroy(zarray_t *za)
static void zarray_set(zarray_t *za, int idx, const void *p, void *outp)
void g2d_line_segment_init_from_points(g2d_line_segment_t *seg, const double p0[2], const double p1[2])
static void timeprofile_display(timeprofile_t *tp)
int g2d_line_segment_intersect_line(const g2d_line_segment_t *seg, const g2d_line_t *line, double *p)
static double mod2pi(double vin)
zarray_t * g2d_polygon_create_data(double v[][2], int sz)
int g2d_polygon_contains_point(const zarray_t *poly, double q[2])
zarray_t * g2d_polygon_create_zeros(int sz)
static zarray_t * zarray_create(size_t el_sz)
int g2d_polygon_overlaps_polygon(const zarray_t *polya, const zarray_t *polyb)
int g2d_polygon_contains_point_ref(const zarray_t *poly, double q[2])
double g2d_distance(const double a[2], const double b[2])
int g2d_line_segment_intersect_segment(const g2d_line_segment_t *sega, const g2d_line_segment_t *segb, double *p)
zarray_t * g2d_convex_hull(const zarray_t *points)
static double sq(double v)
static timeprofile_t * timeprofile_create()
zarray_t * g2d_polygon_create_empty()
static void zarray_get(const zarray_t *za, int idx, void *p)
void g2d_polygon_make_ccw(zarray_t *poly)
static double dclamp(double a, double min, double max)
void g2d_line_segment_closest_point(const g2d_line_segment_t *seg, const double *q, double *p)
int g2d_polygon_contains_polygon(const zarray_t *polya, const zarray_t *polyb)
void g2d_polygon_add(zarray_t *poly, double v[2])
int g2d_polygon_rasterize(const zarray_t *poly, double y, double *x)
void g2d_line_init_from_points(g2d_line_t *line, const double p0[2], const double p1[2])
static void zarray_add(zarray_t *za, const void *p)