/****************************************************************************** * MVar_Pll.c - process polylines out of MvarPlnStruct. * ******************************************************************************* * (C) Gershon Elber, Technion, Israel Institute of Technology * ******************************************************************************* * Written by Gershon Elber, Aug 2003. * ******************************************************************************/ #include "irit_sm.h" #include "mvar_loc.h" #define TEST_CLOSEST_DIST(P1, P2, IsStart1, IsStart2) { \ RealType DstSqr; \ if ((DstSqr = MvarPtDistSqrTwoPoints(P1, P2)) < MinSqr) { \ MinSqr = DstSqr; \ *Start1 = IsStart1; \ *Start2 = IsStart2; \ } \ } typedef struct MVPlPlDistStruct { MvarPolyStruct *Pl; int Idx, MinIdx, MinStart1, MinStart2; RealType MinDistSqr; } MVPlPlDistStruct; static RealType MVGetPlPlDist(MvarPolyStruct *Pl1, MvarPolyStruct *Pl2, int *Start1, int *Start2); #if defined(ultrix) && defined(mips) static int ComparePlPlDist(VoidPtr PlPlDist1, VoidPtr PlPlDist2); #else static int ComparePlPlDist(const VoidPtr PlPlDist1, const VoidPtr PlPlDist2); #endif /* ultrix && mips (no const support) */ /***************************************************************************** * DESCRIPTION: M * Returns the last element in the list. M * * * PARAMETERS: M * Pts: List of points to fetch last one. M * * * RETURN VALUE: M * MvarPtStruct *: Last element in list. M * * * KEYWORDS: M * MvarGetLastPt M *****************************************************************************/ MvarPtStruct *MvarGetLastPt(MvarPtStruct *Pts) { if (Pts == NULL) return NULL; while (Pts -> Pnext != NULL) Pts = Pts -> Pnext; return Pts; } /***************************************************************************** * DESCRIPTION: * * Computes the distance between two polylines. * * * * PARAMETERS: * * Pl1, Pl2: To compute the minimal distance between the end points of. * * Start1, Start2: TRUE if start of polyline, FALSE if end of polyline. * * * * RETURN VALUE: * * RealType: Minimal distance squared computed. * *****************************************************************************/ static RealType MVGetPlPlDist(MvarPolyStruct *Pl1, MvarPolyStruct *Pl2, int *Start1, int *Start2) { RealType MinSqr = IRIT_INFNTY; MvarPtStruct *P1Start = Pl1 -> Pl, *P1End = MvarGetLastPt(P1Start), *P2Start = Pl2 -> Pl, *P2End = MvarGetLastPt(P2Start); if (P1Start == P1End) { if (P2Start == P2End) { TEST_CLOSEST_DIST(P1Start, P2Start, 1, 1); } else { TEST_CLOSEST_DIST(P1Start, P2Start, 1, 1); TEST_CLOSEST_DIST(P1Start, P2End, 1, 0); } } else { if (P2Start == P2End) { TEST_CLOSEST_DIST(P1Start, P2Start, 1, 1); TEST_CLOSEST_DIST(P1End, P2Start, 0, 1); } else { TEST_CLOSEST_DIST(P1Start, P2Start, 1, 1); TEST_CLOSEST_DIST(P1End, P2Start, 0, 1); TEST_CLOSEST_DIST(P1Start, P2End, 1, 0); TEST_CLOSEST_DIST(P1End, P2End, 0, 0); } } return MinSqr; } /***************************************************************************** * DESCRIPTION: M * A comparison function to examine if the given two points are the same. M * * * PARAMETERS: M * P1, P2: Tow multivariate points to compare. M * Eps: N.S.F.I. M * * * RETURN VALUE: M * int: 0 if identical, -1 or +1 if first point is less than /greater M * than second point, in lexicographic order over dimensions. M * * * SEE ALSO: M * MvarPtDistTwoPoints, MvarPtDistSqrTwoPoints M * * * KEYWORDS: M * MvarPtCmpTwoPoints M *****************************************************************************/ int MvarPtCmpTwoPoints(MvarPtStruct *P1, MvarPtStruct *P2, CagdRType Eps) { int i, Dim = P1 -> Dim; if (Dim != P2 -> Dim) return FALSE; for (i = 0; i < Dim; i++) { if (!APX_EQ_EPS(P1 -> Pt[i], P2 -> Pt[i], Eps)) return SIGN(P1 -> Pt[i] - P2 -> Pt[i]); } return TRUE; } /***************************************************************************** * DESCRIPTION: M * Compute the Eucildean distance between two multivariate points. M * * * PARAMETERS: M * P1, P2: Two points to compute the distance between. M * * * RETURN VALUE: M * CagdRType: Distance computed. M * * * SEE ALSO: M * MvarPtCmpTwoPoints, MvarPtDistSqrTwoPoints M * * * KEYWORDS: M * MvarPtDistTwoPoints M *****************************************************************************/ CagdRType MvarPtDistTwoPoints(MvarPtStruct *P1, MvarPtStruct *P2) { return sqrt(MvarPtDistSqrTwoPoints(P1, P2)); } /***************************************************************************** * DESCRIPTION: M * Compute the Eucildean distance between two multivariate points. M * * * PARAMETERS: M * P1, P2: Two points to compute the distance between. M * * * RETURN VALUE: M * CagdRType: Distance computed. M * * * SEE ALSO: M * MvarPtCmpTwoPoints, MvarPtDistTwoPoints M * * * KEYWORDS: M * MvarPtDistSqrTwoPoints M *****************************************************************************/ CagdRType MvarPtDistSqrTwoPoints(MvarPtStruct *P1, MvarPtStruct *P2) { int i, Dim = P1 -> Dim; CagdRType Dist = 0.0; if (Dim != P2 -> Dim) return 0.0; for (i = 0; i < Dim; i++) { Dist += SQR(P1 -> Pt[i] - P2 -> Pt[i]); } return Dist; } /***************************************************************************** * DESCRIPTION: M * Merges seperated multivariate polylines into longer ones, in place, as M * possible. M Given a list of multivariate polylines, matches end points and merged as M * possible multivariate polylines with common end points, in place. M * * * PARAMETERS: M * Polys: Multivariate polylines to merge, in place. M * Eps: Epslion of similarity to merge multivariate polylines at. M * * * RETURN VALUE: M * MvarPolyStruct *: Merged as possible multivariate polylines. M * * * SEE ALSO: M * GMMergePolylines M * * * KEYWORDS: M * MvarPolyMergePolylines, merge, polyline M *****************************************************************************/ MvarPolyStruct *MvarPolyMergePolylines(MvarPolyStruct *Polys, RealType Eps) { MvarPolyStruct *Pl, *Pl2, *Pl2Prev; for (Pl = Polys; Pl != NULL; ) { int HasChanged = FALSE; MvarPtStruct *P1 = Pl -> Pl, *P2 = MvarGetLastPt(P1); for (Pl2Prev = Pl, Pl2 = Pl -> Pnext; Pl2 != NULL && !HasChanged; ) { MvarPtStruct *P, *Pl2P1 = Pl2 -> Pl, *Pl2P2 = MvarGetLastPt(Pl2P1); int FoundMatch = TRUE; if (MvarPtCmpTwoPoints(P1, Pl2P1, Eps)) { Pl -> Pl = MvarPolyReverseList(Pl -> Pl); P = MvarGetLastPt(Pl -> Pl); P -> Pnext = Pl2 -> Pl -> Pnext; } else if (MvarPtCmpTwoPoints(P1, Pl2P2, Eps)) { Pl -> Pl = MvarPolyReverseList(Pl -> Pl); Pl2 -> Pl = MvarPolyReverseList(Pl2 -> Pl); P = MvarGetLastPt(Pl -> Pl); P -> Pnext = Pl2 -> Pl -> Pnext; } else if (MvarPtCmpTwoPoints(P2, Pl2P1, Eps)) { P2 -> Pnext = Pl2P1 -> Pnext; } else if (MvarPtCmpTwoPoints(P2, Pl2P2, Eps)) { Pl2 -> Pl = MvarPolyReverseList(Pl2 -> Pl); P2 -> Pnext = Pl2 -> Pl -> Pnext; } else FoundMatch = FALSE; if (FoundMatch) { Pl2Prev -> Pnext = Pl2 -> Pnext; Pl2 -> Pl -> Pnext = NULL; MvarPolyFree(Pl2); Pl2 = Pl2Prev -> Pnext; HasChanged = TRUE; } else { Pl2Prev = Pl2; Pl2 = Pl2 -> Pnext; } } if (!HasChanged) Pl = Pl -> Pnext; } return Polys; } /***************************************************************************** * DESCRIPTION: * * Routine to compare two GMPlPlDistStruct for sorting purposes. * * * * PARAMETERS: * * PlPlDist1, PlPlDist2: Two pointers to PlPlDist structs. * * * * RETURN VALUE: * * int: >0, 0, or <0 as the relation between the two distances (squared). * *****************************************************************************/ #if defined(ultrix) && defined(mips) static int ComparePlPlDist(VoidPtr PlPlDist1, VoidPtr PlPlDist2) #else static int ComparePlPlDist(const VoidPtr PlPlDist1, const VoidPtr PlPlDist2) #endif /* ultrix && mips (no const support) */ { RealType Diff = ((MVPlPlDistStruct *) PlPlDist1) -> MinDistSqr - ((MVPlPlDistStruct *) PlPlDist2) -> MinDistSqr; return SIGN(Diff); } /***************************************************************************** * DESCRIPTION: M * Connect the list of multivariate points into multivariate polylines by M * connecting the closest multivariate point pairs, until the distances M * between adjacent multivariate points/polylines is more than MaxTol. M * * * PARAMETERS: M * PtsList: Point list to connect into multivariate polylines. M * MaxTol: Maximum distance allowed to connect multivariate points. M * * * RETURN VALUE: M * MvarPolyStruct *: Connected multivariate polylines, upto MaxTol M * tolerance. M * * * SEE ALSO: M * GMMatchPointListIntoPolylines M * * * KEYWORDS: M * MvarMatchPointListIntoPolylines M *****************************************************************************/ MvarPolyStruct *MvarMatchPointListIntoPolylines(MvarPtStruct *PtsList, RealType MaxTol) { int i, LastN, n; RealType MaxTolSqr = SQR(MaxTol); MvarPtStruct *Pt; MvarPolyStruct *Pl1, *PllList; /* Convert the poly list to polyline linked list with one point in */ /* each polyline so we can start and match-connect them. */ for (PllList = NULL, Pt = PtsList; Pt != NULL; Pt = Pt -> Pnext) { Pl1 = MvarPolyNew(MvarPtCopy(Pt)); LIST_PUSH(Pl1, PllList); } n = CagdListLength(PllList); do { int j, *InvIdxMap = (int *) IritMalloc(sizeof(int) * n); MVPlPlDistStruct *Plls = (MVPlPlDistStruct *) IritMalloc(sizeof(MVPlPlDistStruct) * n); LastN = n; # ifdef DEBUG { IRIT_SET_IF_DEBUG_ON_PARAMETER(_DebugPtsToPlsSteps, FALSE) fprintf(stderr, IRIT_EXP_STR("Num of Polylines = %5d\n"), n); } # endif /* DEBUG */ /* Make the list into an array. */ for (i = 0; i < n; i++) LIST_POP(Plls[i].Pl, PllList); /* Compute minimal distance between all points/polylines. */ for (i = 0; i < n; i++) { RealType MinDistSqr = IRIT_INFNTY; int MinStart1 = -1, MinStart2 = -1, MinIdx = -1; for (j = i + 1; j < n; j++) { int Start1, Start2; RealType DistSqr = MVGetPlPlDist(Plls[i].Pl, Plls[j].Pl, &Start1, &Start2); if (DistSqr < MinDistSqr) { MinIdx = j; MinStart1 = Start1; MinStart2 = Start2; MinDistSqr = DistSqr; } } Plls[i].Idx = i; Plls[i].MinIdx = MinIdx; Plls[i].MinStart1 = MinStart1; Plls[i].MinStart2 = MinStart2; Plls[i].MinDistSqr = MinDistSqr; } /* Sort the array based on MinDistSqr slot and build an inverse map. */ qsort(Plls, n - 1, sizeof(MVPlPlDistStruct), ComparePlPlDist); for (i = 0; i < n; i++) InvIdxMap[Plls[i].Idx] = i; /* Merge all polyline we can (no merged polyline will be remerged). */ for (i = 0, PllList = NULL; i < n - 1 && Plls[i].MinDistSqr < MaxTolSqr; i++) { j = InvIdxMap[Plls[i].MinIdx]; if (Plls[i].Pl != NULL && Plls[j].Pl != NULL) { /* Merge plln index i with plln index j, j > i. */ if (Plls[i].MinStart1) Plls[i].Pl -> Pl = MvarPolyReverseList(Plls[i].Pl -> Pl); if (!Plls[i].MinStart2) Plls[j].Pl -> Pl = MvarPolyReverseList(Plls[j].Pl -> Pl); MvarGetLastPt(Plls[i].Pl -> Pl) -> Pnext = Plls[j].Pl -> Pl; Plls[j].Pl -> Pl = NULL; MvarPolyFree(Plls[j].Pl); LIST_PUSH(Plls[i].Pl, PllList); Plls[j].Pl = Plls[i].Pl = NULL; } } /* Regroup into a linked list the rest of the polylines. */ for (i = 0; i < n; i++) if (Plls[i].Pl != NULL) LIST_PUSH(Plls[i].Pl, PllList); IritFree(Plls); IritFree(InvIdxMap); n = CagdListLength(PllList); } while (n < LastN); return PllList; }