00001
00021
00022
00023
00024 #include "outlines.h"
00025
00026 #ifdef __UNIX__
00027 #include <assert.h>
00028 #endif
00029
00030
00031
00032
00033
00039 int crosses_outline(EDGEPT *p0,
00040 EDGEPT *p1,
00041 EDGEPT *outline) {
00042 EDGEPT *pt = outline;
00043 do {
00044 if (is_crossed (p0->pos, p1->pos, pt->pos, pt->next->pos))
00045 return (TRUE);
00046 pt = pt->next;
00047 }
00048 while (pt != outline);
00049 return (FALSE);
00050 }
00051
00052
00053
00061 int is_crossed(TPOINT a0, TPOINT a1, TPOINT b0, TPOINT b1) {
00062 int b0a1xb0b1, b0b1xb0a0;
00063 int a1b1xa1a0, a1a0xa1b0;
00064
00065 TPOINT b0a1, b0a0, a1b1, b0b1, a1a0;
00066
00067 b0a1.x = a1.x - b0.x;
00068 b0a0.x = a0.x - b0.x;
00069 a1b1.x = b1.x - a1.x;
00070 b0b1.x = b1.x - b0.x;
00071 a1a0.x = a0.x - a1.x;
00072 b0a1.y = a1.y - b0.y;
00073 b0a0.y = a0.y - b0.y;
00074 a1b1.y = b1.y - a1.y;
00075 b0b1.y = b1.y - b0.y;
00076 a1a0.y = a0.y - a1.y;
00077
00078 b0a1xb0b1 = CROSS (b0a1, b0b1);
00079 b0b1xb0a0 = CROSS (b0b1, b0a0);
00080 a1b1xa1a0 = CROSS (a1b1, a1a0);
00081
00082 a1a0xa1b0 = -CROSS (a1a0, b0a1);
00083
00084 return (b0a1xb0b1 > 0 && b0b1xb0a0 > 0
00085 || b0a1xb0b1 < 0 && b0b1xb0a0 < 0)
00086 && (a1b1xa1a0 > 0 && a1a0xa1b0 > 0 || a1b1xa1a0 < 0 && a1a0xa1b0 < 0);
00087 }
00088
00089
00090
00094 int is_same_edgept(EDGEPT *p1, EDGEPT *p2) {
00095 return (p1 == p2);
00096 }
00097
00098
00099
00104 EDGEPT *near_point(EDGEPT *point, EDGEPT *line_pt_0, EDGEPT *line_pt_1) {
00105 TPOINT p;
00106
00107 float slope;
00108 float intercept;
00109
00110 float x0 = line_pt_0->pos.x;
00111 float x1 = line_pt_1->pos.x;
00112 float y0 = line_pt_0->pos.y;
00113 float y1 = line_pt_1->pos.y;
00114
00115 if (x0 == x1) {
00116
00117 p.x = (INT16) x0;
00118 p.y = point->pos.y;
00119 }
00120 else {
00121
00122 slope = (y0 - y1) / (x0 - x1);
00123 intercept = y1 - x1 * slope;
00124
00125
00126 p.x = (INT16) ((point->pos.x + (point->pos.y - intercept) * slope) /
00127 (slope * slope + 1));
00128 p.y = (INT16) (slope * p.x + intercept);
00129 }
00130
00131 if (is_on_line (p, line_pt_0->pos, line_pt_1->pos) &&
00132 (!same_point (p, line_pt_0->pos)) && (!same_point (p, line_pt_1->pos)))
00133
00134 return (make_edgept (p.x, p.y, line_pt_1, line_pt_0));
00135 else
00136 return (closest (point, line_pt_0, line_pt_1));
00137 }
00138
00139
00140
00147 void reverse_outline(EDGEPT *outline) {
00148 EDGEPT *edgept = outline;
00149 EDGEPT *temp;
00150
00151 do {
00152
00153 temp = edgept->prev;
00154 edgept->prev = edgept->next;
00155 edgept->next = temp;
00156
00157 edgept->vec.x = edgept->next->pos.x - edgept->pos.x;
00158 edgept->vec.y = edgept->next->pos.y - edgept->pos.y;
00159
00160 edgept = edgept->prev;
00161 }
00162 while (edgept != outline);
00163 }