280 lines
11 KiB
C++
280 lines
11 KiB
C++
|
/*
|
||
|
|
1 interpolate.cpp is the home of the main interpolation recursion.
|
||
|
|
|
||
|
|
*/
|
||
|
|
|
||
|
|
#include "interpolate.h"
|
||
|
|
|
||
|
|
#include <string>
|
||
|
|
|
||
|
|
|
||
|
|
void handleIntersections(MFaces& children, MFace parent, bool evap);
|
||
|
|
vector<MFace> MergeFaces (Matches& m);
|
||
|
|
|
||
|
|
// This variable holds the pointer to the matching strategy to use
|
||
|
|
vector<Matches> (*matchingStrategy)(vector<Face>*,vector<Face>*,
|
||
|
|
int,string);
|
||
|
|
|
||
|
|
/*
|
||
|
|
1.1 ~Interpolate~
|
||
|
|
|
||
|
|
Main interpolation function between two lists of regions.
|
||
|
|
It calls the matching-function to create pairs of regions from the source- and
|
||
|
|
destination-list and interpolates the convex hulls of these regions using the
|
||
|
|
RotatingPlane algorithm. It then creates two new lists from the concavities and
|
||
|
|
holes of the region and recurses. The result of the recursion is then merged
|
||
|
|
into the current result. Intersections are detected and tried to be compensated
|
||
|
|
|
||
|
|
*/
|
||
|
|
MFaces interpolate(vector<Face> *sregs, vector<Face> *dregs, int depth,
|
||
|
|
bool evap, string args) {
|
||
|
|
MFaces ret;
|
||
|
|
|
||
|
|
DEBUG(1, "== Entering Interpolate depth " << depth << " ==");
|
||
|
|
|
||
|
|
if (sregs->empty() && dregs->empty()) // Nothing to do!
|
||
|
|
return ret;
|
||
|
|
|
||
|
|
// Remember the original faces-lists from which the result was created.
|
||
|
|
ret.sregs = sregs;
|
||
|
|
ret.dregs = dregs;
|
||
|
|
|
||
|
|
// Match the faces to pairs of faces in the source- and destination-realm
|
||
|
|
// If we are in the evaporation (or condensation) phase, just try to match
|
||
|
|
// equal faces by their lower left point.
|
||
|
|
vector<Matches> matches;
|
||
|
|
if (!evap)
|
||
|
|
matches = matchFaces(sregs, dregs, depth, args);
|
||
|
|
else
|
||
|
|
matches = matchFaces(sregs, dregs, depth, "lowerleft");
|
||
|
|
|
||
|
|
|
||
|
|
for (unsigned int i = 0; i < matches.size(); i++) {
|
||
|
|
Matches p = matches[i];
|
||
|
|
|
||
|
|
Face *src;
|
||
|
|
Face *dst;
|
||
|
|
|
||
|
|
// This is only a temporary hack to demonstrate face merging.
|
||
|
|
int merged = 0;
|
||
|
|
if (p.src.size() > 1 || p.dst.size() > 1) {
|
||
|
|
if (p.src.size() > 1)
|
||
|
|
merged = 1;
|
||
|
|
else
|
||
|
|
merged = 2;
|
||
|
|
vector<MFace> fcs = MergeFaces(p);
|
||
|
|
if (fcs.empty())
|
||
|
|
merged = 0;
|
||
|
|
for (unsigned int i = 0; i < fcs.size(); i++) {
|
||
|
|
fcs[i].half = merged;
|
||
|
|
ret.AddMFace(fcs[i]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
src = p.srcface();
|
||
|
|
dst = p.dstface();
|
||
|
|
|
||
|
|
if (src && dst) {
|
||
|
|
|
||
|
|
// Use the RotatingPlane-Algorithm to create an interpolation of
|
||
|
|
// the convex hull of src and dst and identify all concavities
|
||
|
|
RotatingPlane rp(src, dst, depth, evap);
|
||
|
|
|
||
|
|
// Recurse and try to match and interpolate the list of concavities
|
||
|
|
MFaces fcs = interpolate(&rp.scvs, &rp.dcvs, depth+1, evap, args);
|
||
|
|
if (merged) {
|
||
|
|
rp.mface.half = 3 - merged;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Now check if the interpolations intersect in any way
|
||
|
|
handleIntersections(fcs, rp.mface, evap);
|
||
|
|
|
||
|
|
// Inherit if the interpolation needs a evaporisation- or
|
||
|
|
// condensation-phase
|
||
|
|
ret.needSEvap = ret.needSEvap || fcs.needSEvap;
|
||
|
|
ret.needDEvap = ret.needDEvap || fcs.needDEvap;
|
||
|
|
|
||
|
|
// Try to merge the recursively created moving segments with the
|
||
|
|
// parent rp.mface
|
||
|
|
for (unsigned int i = 0; i < fcs.faces.size(); i++) {
|
||
|
|
// The holes of the faces are new faces now
|
||
|
|
// Since they should be completely contained by their parent,
|
||
|
|
// an intersection-check is unnecessary. Intersections with
|
||
|
|
// each other were already checked one recursion level lower.
|
||
|
|
for (unsigned int j = 0; j < fcs.faces[i].holes.size(); j++) {
|
||
|
|
MFace fc(fcs.faces[i].holes[j]);
|
||
|
|
ret.AddMFace(fc);
|
||
|
|
}
|
||
|
|
// Add the cycles to its parent
|
||
|
|
rp.mface.AddConcavity(fcs.faces[i]);
|
||
|
|
}
|
||
|
|
|
||
|
|
// and try to merge them into the cycle here (otherwise they are
|
||
|
|
// added as a hole)
|
||
|
|
vector<MFace> splits = rp.mface.MergeConcavities();
|
||
|
|
// Now the resulting moving face is added to the return value
|
||
|
|
ret.AddMFace(rp.mface);
|
||
|
|
for (unsigned int i = 0; i < splits.size(); i++)
|
||
|
|
ret.AddMFace(splits[i]);
|
||
|
|
} else if (src || dst) {
|
||
|
|
// Our face doesn't have a partner, so the recursion stops here and
|
||
|
|
// we collapse (or expand) the face together with its holes
|
||
|
|
Face *r = src ? src : dst;
|
||
|
|
MFace coll = r->collapseWithHoles(r == src);
|
||
|
|
ret.AddMFace(coll);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Toplevel-Intersections are still not handled yet, do that now.
|
||
|
|
if (depth == 0) {
|
||
|
|
handleIntersections(ret, MFace(), evap);
|
||
|
|
}
|
||
|
|
|
||
|
|
DEBUG(1, "== Leaving Interpolate depth " << depth << " ==");
|
||
|
|
|
||
|
|
return ret;
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
1.2 ~handleIntersections~ checks the newly created moving faces ~children~
|
||
|
|
for intersection with each other or their parent ~parent~.
|
||
|
|
|
||
|
|
If a real interpolation intersects, then we remove it and collapse/expand the
|
||
|
|
source- and destinationface of that moving face. If both intersecting moving
|
||
|
|
faces are already collapsed or expanded, then one of them is removed and we
|
||
|
|
need an evaporation- or condensationphase.
|
||
|
|
If we currently are in the evaporation- or condensationphase, then ~evap~ is
|
||
|
|
set and we handle intersections a little different.
|
||
|
|
|
||
|
|
*/
|
||
|
|
void handleIntersections(MFaces& children, MFace parent, bool evap) { return;
|
||
|
|
vector<MSegs> evp; // The list of evaporation-mfaces
|
||
|
|
|
||
|
|
// precalculate the bounding boxes of the children and the parent
|
||
|
|
for (int i = 0; i < (int) children.faces.size(); i++) {
|
||
|
|
children.faces[i].face.calculateBBox();
|
||
|
|
}
|
||
|
|
parent.face.calculateBBox();
|
||
|
|
|
||
|
|
// Now check all pairs of faces of children and the parent, but skip
|
||
|
|
// symmetric and reflexive pairs.
|
||
|
|
for (int i = 0; i < (int) children.faces.size(); i++) {
|
||
|
|
MFace *fs1 = &children.faces[i];
|
||
|
|
for (int j = 0; j <= i; j++) {
|
||
|
|
MFace *fs2 = (j == 0) ? &parent : &children.faces[j - 1];
|
||
|
|
if (fs1->half != fs2->half)
|
||
|
|
continue;
|
||
|
|
MSegs *s1 = &fs1->face;
|
||
|
|
MSegs *s2 = &fs2->face;
|
||
|
|
|
||
|
|
if (s1->intersects(*s2, false, false)) {
|
||
|
|
// We have found two intersecting moving faces.
|
||
|
|
pair<MSegs, MSegs> ss;
|
||
|
|
if (!s1->iscollapsed && !evap) {
|
||
|
|
// If this moving face is not collapsed and we do not
|
||
|
|
// evaporate then break the connection and collapse/expand
|
||
|
|
// the related faces.
|
||
|
|
ss = s1->kill(); // Create the pair of MSegs
|
||
|
|
// Remove the original object from the list
|
||
|
|
children.faces.erase(children.faces.begin()+i);
|
||
|
|
} else if (!s2->iscollapsed && (s2 != &parent.face)
|
||
|
|
&& !evap) {
|
||
|
|
// s1 already was collapsed but s2 is not, so this is the
|
||
|
|
// victim now. Refuse to remove the parent.
|
||
|
|
ss = s2->kill();
|
||
|
|
children.faces.erase(children.faces.begin() + (j-1));
|
||
|
|
} else {
|
||
|
|
// Both intersecting objects are already collapsing or
|
||
|
|
// expanding (or we are evaporating right now)
|
||
|
|
MSegs *rm;
|
||
|
|
if (evap) {
|
||
|
|
// Evaporation- or Condensation-Phase.
|
||
|
|
// Minimum one of the two definitively is already
|
||
|
|
// collapsing/expanding, choose this one
|
||
|
|
if (s1->iscollapsed && !s1->isevaporating)
|
||
|
|
rm = s1;
|
||
|
|
else if (!s2->isevaporating && (s2 != &parent.face))
|
||
|
|
rm = s2;
|
||
|
|
else // cannot be a real intersection, continue
|
||
|
|
continue;
|
||
|
|
vector<MSegs> ms;
|
||
|
|
// iscollapsed is 1, if the mface is collapsing,
|
||
|
|
// otherwise (2) it is expanding and we have to
|
||
|
|
// condensate it
|
||
|
|
if (rm->iscollapsed == 1) {
|
||
|
|
ms = rm->sreg.Evaporate(true);
|
||
|
|
} else {
|
||
|
|
ms = rm->dreg.Evaporate(false);
|
||
|
|
}
|
||
|
|
// Insert the evaporation-cycles into the list
|
||
|
|
children.faces.insert(children.faces.end(),
|
||
|
|
ms.begin(), ms.end());
|
||
|
|
evp.insert(evp.end(), ms.begin(), ms.end());
|
||
|
|
} else {
|
||
|
|
// We are in the main interpolation and cannot
|
||
|
|
// compensate this intersection. Remove one offending
|
||
|
|
// object and save, that we have to evaporate or
|
||
|
|
// condensate to fix that up.
|
||
|
|
rm = s1;
|
||
|
|
// iscollapsed is 1, if the mface is collapsing,
|
||
|
|
// otherwise (2) it is expanding and we have to
|
||
|
|
// do a condensation-phase
|
||
|
|
if (rm->iscollapsed == 1)
|
||
|
|
children.needSEvap = true;
|
||
|
|
else
|
||
|
|
children.needDEvap = true;
|
||
|
|
}
|
||
|
|
// Simply erase the offending object from the list now,
|
||
|
|
// either we have already created evaporisation/condensation
|
||
|
|
// cycles or we marked that we have to fix things up later
|
||
|
|
children.faces.erase(children.faces.begin()+
|
||
|
|
(rm == s1 ? i : j - 1));
|
||
|
|
// Restart the checks with the last face, since we changed
|
||
|
|
// the lists
|
||
|
|
i--;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
// Add the collapse- and expand-cycles
|
||
|
|
children.AddMFace(ss.first);
|
||
|
|
children.AddMFace(ss.second);
|
||
|
|
// Restart the checks one object earlier, since we removed
|
||
|
|
// the current object and the following objects filled the gap.
|
||
|
|
i-=2;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Insert the evaporation- and condensation-cycles into the list of faces
|
||
|
|
// children.faces.insert(children.faces.end(), evp.begin(), evp.end());
|
||
|
|
}
|
||
|
|
|
||
|
|
/*
|
||
|
|
1.3 ~regioninterpolate~ is the interface to the interpolation library.
|
||
|
|
|
||
|
|
Input:
|
||
|
|
src - Source region in nested list representation
|
||
|
|
dst - Destination region in nested list representation
|
||
|
|
start - Timestamp of source region in ms since 1970-01-01 00:00
|
||
|
|
end - Timestamp of destination region in ms since 1970-01-01 00:00
|
||
|
|
args - Parameterstring for the face matching strategy
|
||
|
|
|
||
|
|
Returns:
|
||
|
|
The moving region in nested list representation
|
||
|
|
|
||
|
|
*/
|
||
|
|
RList regioninterpolate(RList src, RList dst,
|
||
|
|
string start, string end, string args) {
|
||
|
|
|
||
|
|
vector<Face> sregs = Face::getFaces(src);
|
||
|
|
vector<Face> dregs = Face::getFaces(dst);
|
||
|
|
|
||
|
|
// Create the interpolation from the lists of faces
|
||
|
|
MFaces mf = interpolate(&sregs, &dregs, 0, false, args);
|
||
|
|
|
||
|
|
Interval iv(start, end, true, true);
|
||
|
|
|
||
|
|
return mf.ToMListExpr(iv);
|
||
|
|
}
|
||
|
|
|