1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314 |
- #include "sys-defines.h"
- #include "extern.h"
- #include "g_arc.h"
- #define NUM_ARC_SUBDIVISIONS 5
- #define MAX_NUM_BEZIER2_SUBDIVISIONS 6
- #define MAX_NUM_BEZIER3_SUBDIVISIONS 7
- #define REL_QUAD_FLATNESS 5e-4
- #define REL_CUBIC_FLATNESS 5e-4
- #define DATAPOINTS_BUFSIZ PL_MAX_UNFILLED_PATH_LENGTH
- #define DIST(p0,p1) (sqrt( ((p0).x - (p1).x)*((p0).x - (p1).x) \
- + ((p0).y - (p1).y)*((p0).y - (p1).y)))
- #define MIDWAY(x0, x1) (0.5 * ((x0) + (x1)))
- static void _prepare_chord_table (double sagitta, double custom_chord_table[TABULATED_ARC_SUBDIVISIONS]);
- static void _fakearc (plPath *path, plPoint p0, plPoint p1, int arc_type, const double *custom_chord_table, const double m[4]);
- plPath *
- _new_plPath (void)
- {
- plPath *path;
-
- path = (plPath *)_pl_xmalloc (sizeof (plPath));
- path->type = PATH_SEGMENT_LIST;
- path->segments = (plPathSegment *)NULL;
- path->segments_len = 0;
- path->num_segments = 0;
- path->primitive = false;
- path->llx = DBL_MAX;
- path->lly = DBL_MAX;
- path->urx = -(DBL_MAX);
- path->ury = -(DBL_MAX);
- return path;
- }
-
- void
- _delete_plPath (plPath *path)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type == PATH_SEGMENT_LIST
- && path->segments_len > 0)
- free (path->segments);
- free (path);
- }
- void
- _reset_plPath (plPath *path)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type == PATH_SEGMENT_LIST
- && path->segments_len > 0)
- free (path->segments);
- path->segments = (plPathSegment *)NULL;
- path->segments_len = 0;
- path->type = PATH_SEGMENT_LIST;
- path->num_segments = 0;
-
- path->primitive = false;
- path->llx = DBL_MAX;
- path->lly = DBL_MAX;
- path->urx = -(DBL_MAX);
- path->ury = -(DBL_MAX);
- }
- void
- _add_moveto (plPath *path, plPoint p)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments > 0)
- return;
-
-
- path->segments = (plPathSegment *)
- _pl_xmalloc (DATAPOINTS_BUFSIZ * sizeof(plPathSegment));
- path->segments_len = DATAPOINTS_BUFSIZ;
-
- path->segments[0].type = S_MOVETO;
- path->segments[0].p = p;
- path->num_segments = 1;
-
- path->llx = p.x;
- path->lly = p.y;
- path->urx = p.x;
- path->ury = p.y;
- }
- void
- _add_line (plPath *path, plPoint p)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
- if (path->num_segments == 0)
-
- {
- path->segments = (plPathSegment *)
- _pl_xmalloc (DATAPOINTS_BUFSIZ * sizeof(plPathSegment));
- path->segments_len = DATAPOINTS_BUFSIZ;
- }
-
- if (path->num_segments == path->segments_len)
-
- {
- path->segments = (plPathSegment *)
- _pl_xrealloc (path->segments,
- 2 * path->segments_len * sizeof(plPathSegment));
- path->segments_len *= 2;
- }
-
- path->segments[path->num_segments].type = S_LINE;
- path->segments[path->num_segments].p = p;
- path->num_segments++;
-
- path->llx = DMIN(path->llx, p.x);
- path->lly = DMIN(path->lly, p.y);
- path->urx = DMAX(path->urx, p.x);
- path->ury = DMAX(path->ury, p.y);
- }
- void
- _add_closepath (plPath *path)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
- if (path->num_segments == 0)
- return;
-
- if (path->num_segments == path->segments_len)
-
- {
- path->segments = (plPathSegment *)
- _pl_xrealloc (path->segments,
- 2 * path->segments_len * sizeof(plPathSegment));
- path->segments_len *= 2;
- }
-
- path->segments[path->num_segments].type = S_CLOSEPATH;
- path->segments[path->num_segments].p = path->segments[0].p;
- path->num_segments++;
- }
- void
- _add_bezier2 (plPath *path, plPoint pc, plPoint p)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
- if (path->num_segments == 0)
-
- {
- path->segments = (plPathSegment *)
- _pl_xmalloc (DATAPOINTS_BUFSIZ * sizeof(plPathSegment));
- path->segments_len = DATAPOINTS_BUFSIZ;
- }
-
- if (path->num_segments == path->segments_len)
-
- {
- path->segments = (plPathSegment *)
- _pl_xrealloc (path->segments,
- 2 * path->segments_len * sizeof(plPathSegment));
- path->segments_len *= 2;
- }
-
- path->segments[path->num_segments].type = S_QUAD;
- path->segments[path->num_segments].p = p;
- path->segments[path->num_segments].pc = pc;
- path->num_segments++;
- }
- void
- _add_bezier3 (plPath *path, plPoint pc, plPoint pd, plPoint p)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
- if (path->num_segments == 0)
-
- {
- path->segments = (plPathSegment *)
- _pl_xmalloc (DATAPOINTS_BUFSIZ * sizeof(plPathSegment));
- path->segments_len = DATAPOINTS_BUFSIZ;
- }
-
- if (path->num_segments == path->segments_len)
-
- {
- path->segments = (plPathSegment *)
- _pl_xrealloc (path->segments,
- 2 * path->segments_len * sizeof(plPathSegment));
- path->segments_len *= 2;
- }
-
- path->segments[path->num_segments].type = S_CUBIC;
- path->segments[path->num_segments].p = p;
- path->segments[path->num_segments].pc = pc;
- path->segments[path->num_segments].pd = pd;
- path->num_segments++;
- }
- void
- _add_arc (plPath *path, plPoint pc, plPoint p1)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
- if (path->num_segments == 0)
-
- {
- path->segments = (plPathSegment *)
- _pl_xmalloc (DATAPOINTS_BUFSIZ * sizeof(plPathSegment));
- path->segments_len = DATAPOINTS_BUFSIZ;
- }
-
- if (path->num_segments == path->segments_len)
-
- {
- path->segments = (plPathSegment *)
- _pl_xrealloc (path->segments,
- 2 * path->segments_len * sizeof(plPathSegment));
- path->segments_len *= 2;
- }
-
- path->segments[path->num_segments].type = S_ARC;
- path->segments[path->num_segments].p = p1;
- path->segments[path->num_segments].pc = pc;
- path->num_segments++;
- }
- void
- _add_ellarc (plPath *path, plPoint pc, plPoint p1)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
- if (path->num_segments == 0)
-
- {
- path->segments = (plPathSegment *)
- _pl_xmalloc (DATAPOINTS_BUFSIZ * sizeof(plPathSegment));
- path->segments_len = DATAPOINTS_BUFSIZ;
- }
-
- if (path->num_segments == path->segments_len)
-
- {
- path->segments = (plPathSegment *)
- _pl_xrealloc (path->segments,
- 2 * path->segments_len * sizeof(plPathSegment));
- path->segments_len *= 2;
- }
-
- path->segments[path->num_segments].type = S_ELLARC;
- path->segments[path->num_segments].p = p1;
- path->segments[path->num_segments].pc = pc;
- path->num_segments++;
- }
- void
- _add_box (plPath *path, plPoint p0, plPoint p1, bool clockwise)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments > 0)
- return;
-
- path->type = PATH_BOX;
- path->p0 = p0;
- path->p1 = p1;
- path->clockwise = clockwise;
-
- path->llx = DMIN(path->llx, p0.x);
- path->lly = DMIN(path->lly, p0.y);
- path->urx = DMAX(path->urx, p0.x);
- path->ury = DMAX(path->ury, p0.y);
-
- path->llx = DMIN(path->llx, p1.x);
- path->lly = DMIN(path->lly, p1.y);
- path->urx = DMAX(path->urx, p1.x);
- path->ury = DMAX(path->ury, p1.y);
- }
- void
- _add_circle (plPath *path, plPoint pc, double radius, bool clockwise)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments > 0)
- return;
-
- path->type = PATH_CIRCLE;
- path->pc = pc;
- path->radius = radius;
- path->clockwise = clockwise;
- }
- void
- _add_ellipse (plPath *path, plPoint pc, double rx, double ry, double angle, bool clockwise)
- {
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments > 0)
- return;
-
- path->type = PATH_ELLIPSE;
- path->pc = pc;
- path->rx = rx;
- path->ry = ry;
- path->angle = angle;
- path->clockwise = clockwise;
- }
- void
- _add_arc_as_lines (plPath *path, plPoint pc, plPoint p1)
- {
-
- plPoint p0;
-
- plPoint pb, pm;
-
- double m[4];
-
- plVector v, v0, v1;
- double radius, sagitta;
- double cross, orientation;
-
- double custom_chord_table[TABULATED_ARC_SUBDIVISIONS];
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
-
- p0 = path->segments[path->num_segments - 1].p;
- if (p0.x == p1.x && p0.y == p1.y)
-
- _add_line (path, p0);
- else
-
- {
-
- v0.x = p0.x - pc.x;
- v0.y = p0.y - pc.y;
- v1.x = p1.x - pc.x;
- v1.y = p1.y - pc.y;
-
-
- cross = v0.x * v1.y - v1.x * v0.y;
-
-
- orientation = (cross >= 0.0 ? 1.0 : -1.0);
-
- radius = DIST(pc, p0);
-
- pm.x = 0.5 * (p0.x + p1.x);
- pm.y = 0.5 * (p0.y + p1.y);
-
- v.x = p1.x - p0.x;
- v.y = p1.y - p0.y;
-
- _vscale(&v, radius);
- pb.x = pc.x + orientation * v.y;
- pb.y = pc.y - orientation * v.x;
-
- sagitta = DIST(pb, pm) / radius;
-
-
- _prepare_chord_table (sagitta, custom_chord_table);
-
-
- m[0] = 0.0, m[1] = orientation, m[2] = -orientation, m[3] = 0.0;
- _fakearc (path, p0, p1, USER_DEFINED_ARC, custom_chord_table, m);
- }
- }
- void
- _add_ellarc_as_lines (plPath *path, plPoint pc, plPoint p1)
- {
- plPoint p0;
- plVector v0, v1;
- double cross;
- double m[4];
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
-
- p0 = path->segments[path->num_segments - 1].p;
-
- v0.x = p0.x - pc.x;
- v0.y = p0.y - pc.y;
- v1.x = p1.x - pc.x;
- v1.y = p1.y - pc.y;
-
- cross = v0.x * v1.y - v1.x * v0.y;
- if (FROUND(cross) == 0.0)
-
- _add_line (path, p1);
- else
- {
-
- m[0] = - (v0.x * v0.y + v1.x * v1.y) / cross;
- m[1] = (v0.x * v0.x + v1.x * v1.x) / cross;
- m[2] = - (v0.y * v0.y + v1.y * v1.y) / cross;
- m[3] = (v0.x * v0.y + v1.x * v1.y) / cross;
-
-
- _fakearc (path, p0, p1, QUARTER_ARC, (double *)NULL, m);
- }
- }
- void
- _add_arc_as_bezier3 (plPath *path, plPoint pc, plPoint p1)
- {
- plPoint p0;
- plVector v0, v1;
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
-
- p0 = path->segments[path->num_segments - 1].p;
-
- v0.x = p0.x - pc.x;
- v0.y = p0.y - pc.y;
- v1.x = p1.x - pc.x;
- v1.y = p1.y - pc.y;
-
- if ((v0.x == 0.0 && v0.y == 0.0) || (v1.x == 0.0 && v1.y == 0.0)
- || (v0.x == v1.x && v0.y == v1.y))
-
- _add_line (path, p1);
- else
-
- {
- double oldangle, newangle, anglerange;
- double cross;
- int orientation;
-
-
- cross = v0.x * v1.y - v1.x * v0.y;
-
-
- orientation = (cross >= 0.0 ? 1 : -1);
-
-
- oldangle = _xatan2 (v0.y, v0.x);
- newangle = _xatan2 (v1.y, v1.x);
- anglerange = newangle - oldangle;
- if (anglerange > M_PI)
- anglerange -= (2 * M_PI);
- if (anglerange <= -(M_PI))
- anglerange += (2 * M_PI);
- if (FABS(anglerange) > 0.51 * M_PI)
-
- {
- double radius;
- plPoint pb;
- plVector v;
- radius = DIST(pc, p0);
-
- v.x = p1.x - p0.x;
- v.y = p1.y - p0.y;
-
- _vscale(&v, radius);
- pb.x = pc.x + orientation * v.y;
- pb.y = pc.y - orientation * v.x;
-
- _add_arc_as_bezier3 (path, pc, pb);
- _add_arc_as_bezier3 (path, pc, p1);
- }
- else
-
- {
- double halfangle, sinhalf, coshalf, kappa;
- plPoint pc_bezier3, pd_bezier3;
- halfangle = 0.5 * FABS(anglerange);
- sinhalf = sin (halfangle);
- coshalf = cos (halfangle);
-
- if (FABS(sinhalf) < 0.5)
- kappa = (4.0/3.0) * sinhalf / (1.0 + coshalf);
- else
- kappa = (4.0/3.0) * (1.0 - coshalf) / sinhalf;
-
- pc_bezier3.x = p0.x - kappa * orientation * v0.y;
- pc_bezier3.y = p0.y + kappa * orientation * v0.x;
- pd_bezier3.x = p1.x + kappa * orientation * v1.y;
- pd_bezier3.y = p1.y - kappa * orientation * v1.x;
- _add_bezier3 (path, pc_bezier3, pd_bezier3, p1);
- }
- }
- }
- #define KAPPA_FOR_QUARTER_CIRCLE 0.552284749825
- void
- _add_ellarc_as_bezier3 (plPath *path, plPoint pc, plPoint p1)
- {
- plPoint p0, pc_bezier3, pd_bezier3;
- plVector v0, v1;
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
-
- p0 = path->segments[path->num_segments - 1].p;
-
- v0.x = p0.x - pc.x;
- v0.y = p0.y - pc.y;
- v1.x = p1.x - pc.x;
- v1.y = p1.y - pc.y;
-
-
- pc_bezier3.x = p0.x + KAPPA_FOR_QUARTER_CIRCLE * v1.x;
- pc_bezier3.y = p0.y + KAPPA_FOR_QUARTER_CIRCLE * v1.y;
- pd_bezier3.x = p1.x + KAPPA_FOR_QUARTER_CIRCLE * v0.x;
- pd_bezier3.y = p1.y + KAPPA_FOR_QUARTER_CIRCLE * v0.y;
- _add_bezier3 (path, pc_bezier3, pd_bezier3, p1);
- }
- void
- _add_bezier2_as_lines (plPath *path, plPoint pc, plPoint p)
- {
- plPoint r0[MAX_NUM_BEZIER2_SUBDIVISIONS + 1], r1[MAX_NUM_BEZIER2_SUBDIVISIONS + 1], r2[MAX_NUM_BEZIER2_SUBDIVISIONS + 1];
- int level[MAX_NUM_BEZIER2_SUBDIVISIONS + 1];
- int n = 0;
- int segments_drawn = 0;
- plPoint p0;
- double sqdist, max_squared_length;
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
-
- p0 = path->segments[path->num_segments - 1].p;
-
-
- sqdist = (p.x - p0.x) * (p.x - p0.x) + (p.y - p0.y) * (p.y - p0.y);
- max_squared_length = REL_QUAD_FLATNESS * REL_QUAD_FLATNESS * sqdist;
- r0[0] = p0;
- r1[0] = pc;
- r2[0] = p;
- level[0] = 0;
- while (n >= 0)
- {
- int current_level;
- plPoint q0, q1, q2;
-
- current_level = level[n];
- q0 = r0[n];
- q1 = r1[n];
- q2 = r2[n];
-
- if (current_level >= MAX_NUM_BEZIER2_SUBDIVISIONS)
-
- {
- _add_line (path, q2);
- segments_drawn++;
- n--;
- }
- else
-
- {
- plPoint qq0, qq1;
- plPoint qqq0;
- plVector vec1;
-
- vec1.x = q0.x - 2 * q1.x + q2.x;
- vec1.y = q0.y - 2 * q1.y + q2.y;
-
- if (vec1.x * vec1.x + vec1.y * vec1.y < max_squared_length)
-
- {
- _add_line (path, q2);
- segments_drawn++;
- n--;
- }
- else
-
-
- {
- qq0.x = MIDWAY(q0.x, q1.x);
- qq0.y = MIDWAY(q0.y, q1.y);
- qq1.x = MIDWAY(q1.x, q2.x);
- qq1.y = MIDWAY(q1.y, q2.y);
-
- qqq0.x = MIDWAY(qq0.x, qq1.x);
- qqq0.y = MIDWAY(qq0.y, qq1.y);
-
-
- r0[n+1] = q0;
- r1[n+1] = qq0;
- r2[n+1] = qqq0;
- level[n+1] = current_level + 1;
-
-
- r0[n] = qqq0;
- r1[n] = qq1;
- r2[n] = q2;
- level[n] = current_level + 1;
-
- n++;
- }
- }
- }
- }
- void
- _add_bezier3_as_lines (plPath *path, plPoint pc, plPoint pd, plPoint p)
- {
- plPoint r0[MAX_NUM_BEZIER3_SUBDIVISIONS + 1], r1[MAX_NUM_BEZIER3_SUBDIVISIONS + 1], r2[MAX_NUM_BEZIER3_SUBDIVISIONS + 1], r3[MAX_NUM_BEZIER3_SUBDIVISIONS + 1];
- int level[MAX_NUM_BEZIER3_SUBDIVISIONS + 1];
- int n = 0;
- int segments_drawn = 0;
- plPoint p0;
- double sqdist, max_squared_length;
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments == 0)
- return;
-
-
- p0 = path->segments[path->num_segments - 1].p;
-
-
- sqdist = (p.x - p0.x) * (p.x - p0.x) + (p.y - p0.y) * (p.y - p0.y);
- max_squared_length = REL_CUBIC_FLATNESS * REL_CUBIC_FLATNESS * sqdist;
- r0[0] = p0;
- r1[0] = pc;
- r2[0] = pd;
- r3[0] = p;
- level[0] = 0;
-
- while (n >= 0)
- {
- int current_level;
- plPoint q0, q1, q2, q3;
-
- current_level = level[n];
- q0 = r0[n];
- q1 = r1[n];
- q2 = r2[n];
- q3 = r3[n];
-
- if (current_level >= MAX_NUM_BEZIER3_SUBDIVISIONS)
-
- {
- _add_line (path, q3);
- segments_drawn++;
- n--;
- }
- else
-
- {
- plPoint qq0, qq1, qq2;
- plPoint qqq0, qqq1;
- plPoint qqqq0;
- plVector vec1, vec2;
-
- vec1.x = q0.x - 2 * q1.x + q2.x;
- vec1.y = q0.y - 2 * q1.y + q2.y;
- vec2.x = q1.x - 2 * q2.x + q3.x;
- vec2.y = q1.y - 2 * q2.y + q3.y;
-
- if (vec1.x * vec1.x + vec1.y * vec1.y < max_squared_length
- && vec2.x * vec2.x + vec2.y * vec2.y < max_squared_length)
-
- {
- _add_line (path, q3);
- segments_drawn++;
- n--;
- }
- else
-
-
- {
- qq0.x = MIDWAY(q0.x, q1.x);
- qq0.y = MIDWAY(q0.y, q1.y);
- qq1.x = MIDWAY(q1.x, q2.x);
- qq1.y = MIDWAY(q1.y, q2.y);
- qq2.x = MIDWAY(q2.x, q3.x);
- qq2.y = MIDWAY(q2.y, q3.y);
-
- qqq0.x = MIDWAY(qq0.x, qq1.x);
- qqq0.y = MIDWAY(qq0.y, qq1.y);
- qqq1.x = MIDWAY(qq1.x, qq2.x);
- qqq1.y = MIDWAY(qq1.y, qq2.y);
-
- qqqq0.x = MIDWAY(qqq0.x, qqq1.x);
- qqqq0.y = MIDWAY(qqq0.y, qqq1.y);
-
-
- level[n+1] = current_level + 1;
- r0[n+1] = q0;
- r1[n+1] = qq0;
- r2[n+1] = qqq0;
- r3[n+1] = qqqq0;
-
-
- level[n] = current_level + 1;
- r0[n] = qqqq0;
- r1[n] = qqq1;
- r2[n] = qq2;
- r3[n] = q3;
-
- n++;
- }
- }
- }
- }
-
- void
- _add_box_as_lines (plPath *path, plPoint p0, plPoint p1, bool clockwise)
- {
- bool x_move_is_first;
- plPoint newpoint;
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments > 0)
- return;
-
- _add_moveto (path, p0);
-
-
- x_move_is_first = ((p1.x >= p0.x && p1.y >= p0.y)
- || (p1.x < p0.x && p1.y < p0.y) ? true : false);
-
- if (clockwise)
-
- x_move_is_first = (x_move_is_first == true ? false : true);
-
- if (x_move_is_first)
- {
- newpoint.x = p1.x;
- newpoint.y = p0.y;
- }
- else
- {
- newpoint.x = p0.x;
- newpoint.y = p1.y;
- }
- _add_line (path, newpoint);
-
- _add_line (path, p1);
-
- if (x_move_is_first)
- {
- newpoint.x = p0.x;
- newpoint.y = p1.y;
- }
- else
- {
- newpoint.x = p1.x;
- newpoint.y = p0.y;
- }
- _add_line (path, newpoint);
-
- _add_line (path, p0);
-
- path->primitive = true;
- }
- void
- _add_ellipse_as_bezier3s (plPath *path, plPoint pc, double rx, double ry, double angle, bool clockwise)
- {
- plPoint startpoint, newpoint;
- double theta, costheta, sintheta;
- double xc, yc;
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments > 0)
- return;
-
-
- theta = (M_PI / 180.0) * angle;
- costheta = cos (theta);
- sintheta = sin (theta);
-
- xc = pc.x;
- yc = pc.y;
- startpoint.x = xc + rx * costheta;
- startpoint.y = yc + rx * sintheta;
- _add_moveto (path, startpoint);
-
- if (clockwise)
- {
- newpoint.x = xc + ry * sintheta;
- newpoint.y = yc - ry * costheta;
- }
- else
- {
- newpoint.x = xc - ry * sintheta;
- newpoint.y = yc + ry * costheta;
- }
- _add_ellarc_as_bezier3 (path, pc, newpoint);
-
- newpoint.x = xc - rx * costheta;
- newpoint.y = yc - rx * sintheta;
- _add_ellarc_as_bezier3 (path, pc, newpoint);
-
- if (clockwise)
- {
- newpoint.x = xc - ry * sintheta;
- newpoint.y = yc + ry * costheta;
- }
- else
- {
- newpoint.x = xc + ry * sintheta;
- newpoint.y = yc - ry * costheta;
- }
- _add_ellarc_as_bezier3 (path, pc, newpoint);
-
- _add_ellarc_as_bezier3 (path, pc, startpoint);
-
- path->primitive = true;
- }
- void
- _add_ellipse_as_ellarcs (plPath *path, plPoint pc, double rx, double ry, double angle, bool clockwise)
- {
- plPoint startpoint, newpoint;
- double theta, costheta, sintheta;
- double xc, yc;
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments > 0)
- return;
-
-
- theta = (M_PI / 180.0) * angle;
- costheta = cos (theta);
- sintheta = sin (theta);
-
- xc = pc.x;
- yc = pc.y;
- startpoint.x = xc + rx * costheta;
- startpoint.y = yc + rx * sintheta;
- _add_moveto (path, startpoint);
-
- if (clockwise)
- {
- newpoint.x = xc + ry * sintheta;
- newpoint.y = yc - ry * costheta;
- }
- else
- {
- newpoint.x = xc - ry * sintheta;
- newpoint.y = yc + ry * costheta;
- }
- _add_ellarc (path, pc, newpoint);
-
- newpoint.x = xc - rx * costheta;
- newpoint.y = yc - rx * sintheta;
- _add_ellarc (path, pc, newpoint);
-
- if (clockwise)
- {
- newpoint.x = xc - ry * sintheta;
- newpoint.y = yc + ry * costheta;
- }
- else
- {
- newpoint.x = xc + ry * sintheta;
- newpoint.y = yc - ry * costheta;
- }
- _add_ellarc (path, pc, newpoint);
-
- _add_ellarc (path, pc, startpoint);
-
- path->primitive = true;
- }
- void
- _add_ellipse_as_lines (plPath *path, plPoint pc, double rx, double ry, double angle, bool clockwise)
- {
- plPoint startpoint, newpoint;
- double theta, costheta, sintheta;
- double xc, yc;
-
- if (path == (plPath *)NULL)
- return;
-
- if (path->type != PATH_SEGMENT_LIST || path->num_segments > 0)
- return;
-
-
- theta = (M_PI / 180.0) * angle;
- costheta = cos (theta);
- sintheta = sin (theta);
-
- xc = pc.x;
- yc = pc.y;
- startpoint.x = xc + rx * costheta;
- startpoint.y = yc + rx * sintheta;
- _add_moveto (path, startpoint);
-
- if (clockwise)
- {
- newpoint.x = xc + ry * sintheta;
- newpoint.y = yc - ry * costheta;
- }
- else
- {
- newpoint.x = xc - ry * sintheta;
- newpoint.y = yc + ry * costheta;
- }
- _add_ellarc_as_lines (path, pc, newpoint);
-
- newpoint.x = xc - rx * costheta;
- newpoint.y = yc - rx * sintheta;
- _add_ellarc_as_lines (path, pc, newpoint);
-
- if (clockwise)
- {
- newpoint.x = xc - ry * sintheta;
- newpoint.y = yc + ry * costheta;
- }
- else
- {
- newpoint.x = xc + ry * sintheta;
- newpoint.y = yc - ry * costheta;
- }
- _add_ellarc_as_lines (path, pc, newpoint);
-
- _add_ellarc_as_lines (path, pc, startpoint);
-
- path->primitive = true;
- }
- void
- _add_circle_as_bezier3s (plPath *path, plPoint pc, double radius, bool clockwise)
- {
- if (path == (plPath *)NULL)
- return;
-
- _add_ellipse_as_bezier3s (path, pc, radius, radius, 0.0, clockwise);
- path->primitive = true;
- }
- void
- _add_circle_as_ellarcs (plPath *path, plPoint pc, double radius, bool clockwise)
- {
- if (path == (plPath *)NULL)
- return;
-
- _add_ellipse_as_ellarcs (path, pc, radius, radius, 0.0, clockwise);
- path->primitive = true;
- }
- void
- _add_circle_as_lines (plPath *path, plPoint pc, double radius, bool clockwise)
- {
- if (path == (plPath *)NULL)
- return;
-
- _add_ellipse_as_lines (path, pc, radius, radius, 0.0, clockwise);
- path->primitive = true;
- }
- static void
- _fakearc (plPath *path, plPoint p0, plPoint p1, int arc_type, const double *custom_chord_table, const double m[4])
- {
- plPoint p[NUM_ARC_SUBDIVISIONS + 1], q[NUM_ARC_SUBDIVISIONS + 1];
- int level[NUM_ARC_SUBDIVISIONS + 1];
- int n = 0;
- int segments_drawn = 0;
- const double *our_chord_table;
- if (arc_type == USER_DEFINED_ARC)
- our_chord_table = custom_chord_table;
- else
- our_chord_table = _chord_table[arc_type];
- p[0] = p0;
- q[0] = p1;
- level[0] = 0;
- while (n >= 0)
- {
- if (level[n] >= NUM_ARC_SUBDIVISIONS)
- {
- _add_line (path, q[n]);
- segments_drawn++;
- n--;
- }
-
- else
- {
- plVector v;
- plPoint pm, pb;
-
- v.x = q[n].x - p[n].x;
- v.y = q[n].y - p[n].y;
-
- pm.x = p[n].x + 0.5 * v.x;
- pm.y = p[n].y + 0.5 * v.y;
-
-
-
- pb.x = pm.x +
- our_chord_table[level[n]] * (m[0] * v.x + m[1] * v.y);
- pb.y = pm.y +
- our_chord_table[level[n]] * (m[2] * v.x + m[3] * v.y);
-
-
- p[n+1] = p[n];
- q[n+1] = pb;
- level[n+1] = level[n] + 1;
-
- p[n] = pb;
- q[n] = q[n];
- level[n] = level[n] + 1;
-
- n++;
- }
- }
- }
- static void
- _prepare_chord_table (double sagitta, double custom_chord_table[TABULATED_ARC_SUBDIVISIONS])
- {
- double half_chord_length;
- int i;
- half_chord_length = sqrt ( sagitta * (2.0 - sagitta) );
- for (i = 0; i < TABULATED_ARC_SUBDIVISIONS; i++)
- {
- custom_chord_table[i] = 0.5 * sagitta / half_chord_length;
- sagitta = 1.0 - sqrt (1.0 - 0.5 * sagitta);
- half_chord_length = 0.5 * half_chord_length / (1.0 - sagitta);
- }
- }
- plPath *
- _flatten_path (const plPath *path)
- {
- plPath *newpath;
-
- if (path == (plPath *)NULL)
- return (plPath *)NULL;
- switch (path->type)
- {
- case PATH_SEGMENT_LIST:
- {
- bool do_flatten = false;
- int i;
- for (i = 0; i < path->num_segments; i++)
- {
- if (path->segments[i].type != S_MOVETO
- && path->segments[i].type != S_LINE
- && path->segments[i].type != S_CLOSEPATH)
- {
- do_flatten = true;
- break;
- }
- }
-
- if (do_flatten == false)
- newpath = (plPath *)path;
- else
- {
- newpath = _new_plPath ();
- for (i = 0; i < path->num_segments; i++)
- {
- switch ((int)(path->segments[i].type))
- {
- case (int)S_MOVETO:
- _add_moveto (newpath, path->segments[i].p);
- break;
- case (int)S_LINE:
- _add_line (newpath, path->segments[i].p);
- break;
- case (int)S_CLOSEPATH:
- _add_closepath (newpath);
- break;
-
- case (int)S_ARC:
- _add_arc_as_lines (newpath,
- path->segments[i].pc,
- path->segments[i].p);
- break;
- case (int)S_ELLARC:
- _add_ellarc_as_lines (newpath,
- path->segments[i].pc,
- path->segments[i].p);
- break;
- case (int)S_QUAD:
- _add_bezier2_as_lines (newpath,
- path->segments[i].pc,
- path->segments[i].p);
- break;
- case (int)S_CUBIC:
- _add_bezier3_as_lines (newpath,
- path->segments[i].pc,
- path->segments[i].pd,
- path->segments[i].p);
- break;
- default:
- break;
- }
- }
- }
- break;
- }
- case PATH_CIRCLE:
- newpath = _new_plPath ();
- _add_circle_as_lines (newpath,
- path->pc, path->radius, path->clockwise);
- break;
- case PATH_ELLIPSE:
- newpath = _new_plPath ();
- _add_ellipse_as_lines (newpath,
- path->pc, path->rx, path->ry, path->angle,
- path->clockwise);
- break;
- case PATH_BOX:
- newpath = _new_plPath ();
- _add_box_as_lines (newpath, path->p0, path->p1, path->clockwise);
- break;
- default:
- newpath = _new_plPath ();
- break;
- }
- return newpath;
- }
- typedef struct subpath_struct
- {
- plPathSegment *segments;
- int num_segments;
- struct subpath_struct **parents;
- struct subpath_struct *parent;
- struct subpath_struct **children;
- int num_children;
- int num_outside;
- double llx, lly, urx, ury;
- bool inserted;
- } subpath;
- static subpath * new_subpath (void);
- static subpath ** new_subpath_array (int n);
- static void delete_subpath (subpath *s);
- static void delete_subpath_array (subpath **s, int n);
- static bool is_inside_of (const subpath *s, const subpath *other);
- static double _cheap_lower_bound_on_distance (const subpath *path1, const subpath *path2);
- static void linearize_subpath (subpath *s);
- static void read_into_subpath (subpath *s, const plPath *path);
- static void find_parents_in_subpath_list (subpath **annotated_paths, int num_paths);
- static void insert_subpath (plPathSegment *parent_segments, const plPathSegment *child_segments, int parent_size, int child_size, int parent_index, int child_index);
- static void _compute_closest (const plPathSegment *p1, const plPathSegment *p2, int size1, int size2, double *distance, int *index1, int *index2);
- static subpath *
- new_subpath (void)
- {
- subpath *s;
-
- s = (subpath *)_pl_xmalloc (sizeof (subpath));
- s->segments = (plPathSegment *)NULL;
- s->num_segments = 0;
- s->parents = (subpath **)NULL;
- s->parent = (subpath *)NULL;
- s->children = (subpath **)NULL;
- s->num_children = 0;
- s->num_outside = 0;
- s->llx = DBL_MAX;
- s->lly = DBL_MAX;
- s->urx = -DBL_MAX;
- s->ury = -DBL_MAX;
- s->inserted = false;
- return s;
- }
-
- static subpath **
- new_subpath_array (int n)
- {
- int i;
- subpath **s;
-
- s = (subpath **)_pl_xmalloc (n * sizeof (subpath *));
- for (i = 0; i < n; i++)
- s[i] = new_subpath ();
- return s;
- }
-
- static void
- delete_subpath (subpath *s)
- {
- if (s)
- {
- if (s->segments)
- free (s->segments);
- if (s->children)
- free (s->children);
- if (s->parents)
- free (s->parents);
- free (s);
- }
- }
- static void
- delete_subpath_array (subpath **s, int n)
- {
- int i;
- if (s)
- {
- for (i = 0; i < n; i++)
- delete_subpath (s[i]);
- free (s);
- }
- }
- static void
- linearize_subpath (subpath *s)
- {
-
- s->segments[0].type = S_LINE;
-
- if (s->segments[s->num_segments-1].type == S_CLOSEPATH)
- {
- s->segments[s->num_segments-1].type = S_LINE;
- s->segments[s->num_segments-1].p = s->segments[0].p;
- }
- }
- static void
- read_into_subpath (subpath *s, const plPath *path)
- {
- bool need_to_close = false;
- int i;
-
-
- if (path->type != PATH_SEGMENT_LIST)
- return;
-
- s->segments = (plPathSegment *)_pl_xmalloc((path->num_segments + 1) * sizeof (plPathSegment));
- s->num_segments = path->num_segments;
-
- if (path->num_segments == 0)
- return;
-
- if (path->segments[path->num_segments - 1].type != S_CLOSEPATH
- &&
- (path->segments[path->num_segments - 1].p.x != path->segments[0].p.x
- || path->segments[path->num_segments - 1].p.y != path->segments[0].p.y))
- need_to_close = true;
-
- for (i = 0; i < path->num_segments; i++)
- {
- plPathSegment e;
-
- e = path->segments[i];
- s->segments[i] = e;
- if (e.p.x < s->llx)
- s->llx = e.p.x;
- if (e.p.y < s->lly)
- s->lly = e.p.y;
- if (e.p.x > s->urx)
- s->urx = e.p.x;
- if (e.p.y > s->ury)
- s->ury = e.p.y;
- }
- if (need_to_close)
- {
- #if 0
- s->segments[path->num_segments].type = S_CLOSEPATH;
- #else
- s->segments[path->num_segments].type = S_LINE;
- #endif
- s->segments[path->num_segments].p = path->segments[0].p;
- s->num_segments++;
- }
- }
- static bool
- is_inside_of (const subpath *s, const subpath *other)
- {
- int inside = 0;
- int outside = 0;
- int i;
-
-
- if (!((s->llx >= other->llx) && (s->lly >= other->lly) &&
- (s->urx <= other->urx) && (s->ury <= other->ury)))
- return false;
-
-
- for (i = 0; i < s->num_segments; i++)
- {
- bool point_is_inside;
- if (s->segments[i].type == S_CLOSEPATH)
-
- continue;
-
- {
-
- #define SMALL_X_FACTOR (M_SQRT2 * M_PI)
- #define SMALL_Y_FACTOR (M_SQRT2 + M_PI)
-
- plPoint p;
-
- int k, crossings;
-
- double x1, y1;
-
- double x2, y2;
-
-
- p = s->segments[i].p;
-
-
- x1 = (DMAX(p.x, other->urx)
- + SMALL_X_FACTOR * (DMAX(p.x, other->urx)
- - DMIN(p.x, other->llx)));
- y1 = (DMAX(p.y, other->ury)
- + SMALL_Y_FACTOR * (DMAX(p.y, other->ury)
- - DMIN(p.y, other->lly)));
-
-
- x2 = p.x;
- y2 = p.y;
-
- crossings = 0;
- for (k = 0; k < other->num_segments; k++)
- {
- int j;
- double x3, y3, x4, y4, det, det1, det2;
-
- if (other->segments[k].type == S_CLOSEPATH)
- {
- x3 = other->segments[k-1].p.x;
- y3 = other->segments[k-1].p.y;
- }
- else
- {
- x3 = other->segments[k].p.x;
- y3 = other->segments[k].p.y;
- }
-
- j = (k == other->num_segments - 1 ? 0 : k + 1);
- if (other->segments[j].type == S_CLOSEPATH)
- continue;
-
- x4 = other->segments[j].p.x;
- y4 = other->segments[j].p.y;
-
-
-
-
-
- det = (x2 - x1) * (-(y4 - y3)) - (-(x4 - x3)) * (y2 - y1);
- if (det == 0.0)
-
- continue;
-
- det1 = (x3 - x1) * (-(y4 - y3)) - (-(x4 - x3)) * (y3 - y1);
- det2 = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
-
- if ((det<0.0 && (det1>0.0 || det2>0.0 || det1<det || det2<det))
- ||
- (det>0.0 && (det1<0.0 || det2<0.0 || det1>det || det2>det)))
-
- continue;
-
-
-
- crossings++;
- }
-
-
- point_is_inside = (crossings & 1) ? true : false;
- }
-
- if (point_is_inside)
- inside++;
- else
- outside++;
- }
-
- return (inside > outside ? true : false);
- }
- static void
- find_parents_in_subpath_list (subpath **annotated_paths, int num_paths)
- {
- int i, j;
- subpath *parent;
-
-
- for (i = 0; i < num_paths; i++)
- {
- annotated_paths[i]->parents = new_subpath_array (num_paths);
- for (j = 0; j < num_paths; j++)
- {
- if (j != i)
- {
- if (is_inside_of (annotated_paths[i], annotated_paths[j]))
- {
- annotated_paths[i]->parents[annotated_paths[i]->num_outside] =
- annotated_paths[j];
- annotated_paths[i]->num_outside++;
- }
- }
- }
- }
-
- for (i = 0; i < num_paths; i++)
- {
- if ((annotated_paths[i]->num_outside & 1) == 0)
-
- {
-
- annotated_paths[i]->children = new_subpath_array (num_paths);
- }
- }
-
-
- for (i = 0; i < num_paths; i++)
- {
- if ((annotated_paths[i]->num_outside & 1) == 0)
-
- continue;
- else
-
- {
- for (j = 0; j < annotated_paths[i]->num_outside; j++)
- {
- if (annotated_paths[i]->num_outside ==
- annotated_paths[i]->parents[j]->num_outside + 1)
-
- {
- parent = annotated_paths[i]->parents[j];
- annotated_paths[i]->parent = parent;
- parent->children[parent->num_children] = annotated_paths[i];
- parent->num_children++;
- break;
- }
- }
- }
- }
- }
- static void
- _compute_closest (const plPathSegment *p1, const plPathSegment *p2, int size1, int size2, double *distance, int *index1, int *index2)
- {
- int best_i = 0, best_j = 0;
- double best_distance = DBL_MAX;
- int ii, jj;
-
- for (ii = 0; ii < size1; ii++)
- {
- plPoint point1;
-
- point1 = p1[ii].p;
- for (jj = 0; jj < size2; jj++)
- {
- double tmp1, tmp2, distance;
- plPoint point2;
-
- point2 = p2[jj].p;
- tmp1 = point1.x - point2.x;
- tmp2 = point1.y - point2.y;
- distance = tmp1 * tmp1 + tmp2 * tmp2;
- if (distance < best_distance)
- {
- best_distance = distance;
- best_i = ii;
- best_j = jj;
- }
- }
- }
-
-
- *distance = best_distance;
- *index1 = best_i;
- *index2 = best_j;
- }
- static double
- _cheap_lower_bound_on_distance (const subpath *path1, const subpath *path2)
- {
- double xdist = 0.0, ydist = 0.0, dist;
-
- if (path1->urx < path2->llx)
- xdist = path2->llx - path1->urx;
- else if (path2->urx < path1->llx)
- xdist = path1->llx - path2->urx;
-
- if (path1->ury < path2->lly)
- ydist = path2->lly - path1->ury;
- else if (path2->ury < path1->lly)
- ydist = path1->lly - path2->ury;
- dist = xdist * xdist + ydist * ydist;
- return dist;
- }
-
- #define CHILD_VERTEX_IN_MERGED_PATH(i,parent_index,parent_size,child_index,child_size) ((i) <= (child_index) ? (i) + (parent_index) + (child_size) - (child_index) : (i) + (parent_index) - (child_index) + 1)
- #define PARENT_VERTEX_IN_MERGED_PATH(i,parent_index,parent_size,child_index,child_size) ((i) <= (parent_index) ? (i) : (i) + (child_size) + 1)
- static void
- insert_subpath (plPathSegment *parent, const plPathSegment *child, int parent_size, int child_size, int parent_index, int child_index)
- {
- int i;
- plPathSegment e1, e2;
- int src_index;
-
- /* map case when joining vertex is final vertex of child to case when
- it's the 0'th vertex */
- if (child_index == child_size - 1)
- child_index = 0;
- /* move up: add child_size+1 empty slots to parent path */
- for (i = parent_size - 1; i >= parent_index + 1; i--)
- parent[i + child_size + 1] = parent[i];
-
-
- e1 = child[child_index];
- e1.type = S_LINE;
- parent[parent_index + 1] = e1;
-
-
- src_index = child_index;
- for (i = 0; i < child_size - 1; i++)
- {
- src_index++;
- if (src_index == child_size - 1)
- src_index = 0;
- parent[parent_index + 2 + i] = child[src_index];
- }
-
-
- e2 = parent[parent_index];
- e2.type = S_LINE;
- parent[parent_index + child_size + 1] = e2;
- }
- plPath **
- _merge_paths (const plPath **paths, int num_paths)
- {
- int i;
- subpath **annotated_paths;
- plPath **flattened_paths;
- plPath **merged_paths;
-
- flattened_paths = (plPath **)_pl_xmalloc (num_paths * sizeof(plPath *));
- for (i = 0; i < num_paths; i++)
- {
- flattened_paths[i] = _flatten_path (paths[i]);
- #ifdef DEBUG
- fprintf (stderr, "path %d: %d segments, flattened to %d segments\n",
- i, paths[i]->num_segments, flattened_paths[i]->num_segments);
- #endif
- }
-
- annotated_paths = new_subpath_array (num_paths);
- for (i = 0; i < num_paths; i++)
- read_into_subpath (annotated_paths[i], flattened_paths[i]);
-
- for (i = 0; i < num_paths; i++)
- if (flattened_paths[i] != paths[i])
- _delete_plPath (flattened_paths[i]);
-
- find_parents_in_subpath_list (annotated_paths, num_paths);
-
- for (i = 0; i < num_paths; i++)
- if (annotated_paths[i]->parent != (subpath *)NULL)
-
- linearize_subpath (annotated_paths[i]);
-
-
- merged_paths = (plPath **)_pl_xmalloc (num_paths * sizeof(plPath *));
- for (i = 0; i < num_paths; i++)
- {
- int j, k, num_segments_in_merged_path;
- subpath *parent;
- plPath *merged_path;
- double *parent_to_child_distances;
- int *child_best_indices, *parent_best_indices;
- if (annotated_paths[i]->parent != (subpath *)NULL)
-
- {
- merged_paths[i] = (plPath *)NULL;
- continue;
- }
- if (annotated_paths[i]->num_children == 0)
-
- {
- merged_paths[i] = (plPath *)paths[i];
- continue;
- }
-
- parent = annotated_paths[i];
- num_segments_in_merged_path = parent->num_segments;
- for (j = 0; j < parent->num_children; j++)
- num_segments_in_merged_path
- += (parent->children[j]->num_segments + 1);
- merged_path = _new_plPath ();
- merged_path->segments = (plPathSegment *)_pl_xmalloc(num_segments_in_merged_path * sizeof (plPathSegment));
- merged_path->num_segments = 0;
- merged_path->segments_len = num_segments_in_merged_path;
-
- for (j = 0; j < parent->num_segments; j++)
- merged_path->segments[j] = parent->segments[j];
- merged_path->num_segments = parent->num_segments;
-
-
- parent_to_child_distances = (double *)_pl_xmalloc(parent->num_children * sizeof (double));
- parent_best_indices = (int *)_pl_xmalloc(parent->num_children * sizeof (int));
- child_best_indices = (int *)_pl_xmalloc(parent->num_children * sizeof (int));
-
- for (j = 0; j < parent->num_children; j++)
- _compute_closest (parent->segments,
- parent->children[j]->segments,
- parent->num_segments,
- parent->children[j]->num_segments,
- &(parent_to_child_distances[j]),
- &(parent_best_indices[j]),
- &(child_best_indices[j]));
-
- for (k = 0; k < parent->num_children; k++)
-
- {
- double min_distance;
- int closest = 0;
- double *new_parent_to_child_distances;
- int *new_child_best_indices, *new_parent_best_indices;
-
- new_parent_to_child_distances = (double *)_pl_xmalloc(parent->num_children * sizeof (double));
- new_parent_best_indices = (int *)_pl_xmalloc(parent->num_children * sizeof (int));
- new_child_best_indices = (int *)_pl_xmalloc(parent->num_children * sizeof (int));
-
- for (j = 0; j < parent->num_children; j++)
- {
- new_parent_to_child_distances[j] = parent_to_child_distances[j];
- new_parent_best_indices[j] = parent_best_indices[j];
- new_child_best_indices[j] = child_best_indices[j];
- }
-
- min_distance = DBL_MAX;
- for (j = 0; j < parent->num_children; j++)
- {
- if (parent->children[j]->inserted)
- continue;
-
- if (parent_to_child_distances[j] < min_distance)
- {
- closest = j;
- min_distance = parent_to_child_distances[j];
- }
- }
-
-
-
- for (j = 0; j < parent->num_children; j++)
- {
- double inter_child_distance;
- int inter_child_best_index1, inter_child_best_index2;
- double lower_bound_on_inter_child_distance;
- bool compute_carefully;
- if (parent->children[j]->inserted)
- continue;
-
- if (j == closest)
- continue;
-
-
- lower_bound_on_inter_child_distance =
- _cheap_lower_bound_on_distance (parent->children[j],
- parent->children[closest]);
- compute_carefully =
- (lower_bound_on_inter_child_distance <
- parent_to_child_distances[j]) ? true : false;
- if (compute_carefully)
-
- _compute_closest (parent->children[j]->segments,
- parent->children[closest]->segments,
- parent->children[j]->num_segments,
- parent->children[closest]->num_segments,
- &inter_child_distance,
- &inter_child_best_index1,
- &inter_child_best_index2);
-
-
- if (compute_carefully &&
- inter_child_distance < parent_to_child_distances[j])
-
- {
- int nearest_index_in_closest_child;
- new_parent_to_child_distances[j] = inter_child_distance;
- new_child_best_indices[j] = inter_child_best_index1;
- nearest_index_in_closest_child = inter_child_best_index2;
-
-
- if (nearest_index_in_closest_child ==
- parent->children[closest]->num_segments - 1)
- nearest_index_in_closest_child = 0;
- new_parent_best_indices[j] =
- CHILD_VERTEX_IN_MERGED_PATH(nearest_index_in_closest_child,
- parent_best_indices[closest],
- merged_path->num_segments,
- child_best_indices[closest],
- parent->children[closest]->num_segments);
- }
- else
-
- {
- int nearest_index_in_parent;
- nearest_index_in_parent = parent_best_indices[j];
-
- new_parent_best_indices[j] =
- PARENT_VERTEX_IN_MERGED_PATH(nearest_index_in_parent,
- parent_best_indices[closest],
- merged_path->num_segments,
- child_best_indices[closest],
- parent->children[closest]->num_segments);
- }
- }
-
-
- insert_subpath (merged_path->segments,
- parent->children[closest]->segments,
- merged_path->num_segments,
- parent->children[closest]->num_segments,
- parent_best_indices[closest],
- child_best_indices[closest]);
- merged_path->num_segments +=
- (parent->children[closest]->num_segments + 1);
- parent->children[closest]->inserted = true;
-
- for (j = 0; j < parent->num_children; j++)
- {
- parent_to_child_distances[j] = new_parent_to_child_distances[j];
- parent_best_indices[j] = new_parent_best_indices[j];
- child_best_indices[j] = new_child_best_indices[j];
- }
- free (new_parent_to_child_distances);
- free (new_parent_best_indices);
- free (new_child_best_indices);
- }
-
- merged_path->segments[0].type = S_MOVETO;
- merged_paths[i] = merged_path;
-
-
- free (parent_to_child_distances);
- free (parent_best_indices);
- free (child_best_indices);
- }
-
-
- delete_subpath_array (annotated_paths, num_paths);
- return merged_paths;
- }
|