/**
* @file Class Matching
* @version March 26, 2017
*
* @author Olivier Pirson --- http://www.opimedia.be/
* @license GPLv3 --- Copyright (C) 2017 Olivier Pirson
*/
/**
* A geometric matching:
* - a "set" of points
* - a "set" of segments on these points
*
* The set of points may be shared with other linked matching.
*/
class Matching {
/**
* Construct a Matching.
*
* If linkedMatching !== null
* then shared points with it.
*
* @param {null|Matching} linkedMatching
*/
constructor(linkedMatching=null) {
assert((linkedMatching === null) || (linkedMatching instanceof Matching), linkedMatching);
if (linkedMatching === null) {
this._points = []; // ordonned sequence of Point
this._linkedMatchings = [this]; // ordonned sequence of Matching
}
else {
this._points = linkedMatching.points;
linkedMatching.linkedMatchings.push(this);
this._linkedMatchings = linkedMatching.linkedMatchings;
}
this._segments = []; // ordonned sequence of Segment (for each segment, the two points are ordonned)
this._numberPerfectMatchingsIfCalculated = null; // null or (if already calculated) the exact number of perfect matchings for theses points
}
/**
* Returns the ordonned sequence of linked matchings.
*
* @returns {Array} Array of Matching
*/
get linkedMatchings() { return this._linkedMatchings; }
/**
* If is already calculated or if it easy to calculate
* then returns the exact number of perfect matchings for theses points,
* else returns null.
*
* @returns {null|Number}
*/
get numberPerfectMatchingsIfCalculated() {
if (this.points.length % 2 !== 0) {
this._numberPerfectMatchingsIfCalculated = 0;
}
else if (this.points.length <= 2) {
this._numberPerfectMatchingsIfCalculated = this.points.length/2;
}
return this._numberPerfectMatchingsIfCalculated;
}
/**
* Returns the ordonned sequence of points.
*
* @returns {Array} Array of Point
*/
get points() { return this._points; }
/**
* Returns the sequence of segments.
*
* @returns {Array} Array of Segment (for each segment, the two points are ordonned)
*/
get segments() { return this._segments; }
/**
* Returns all possible perfect matchings
* with the points of this matching.
*
* If disjointMatching
* then keep only perfect matching disjoint with this matching.
*
* If compatibleMatching
* then keep only perfect matching disjoint with this matching.
*
* FIXME! Naive algorithm. Implement iterative building?
*
* @param {Boolean} disjointMatching
* @param {Boolean} compatibleMatching
*
* @returns {Array} Array of Matching
*/
allPerfectMatchings(disjointMatching, compatibleMatching) {
assert(typeof disjointMatching === "boolean", disjointMatching);
assert(typeof compatibleMatching === "boolean", compatibleMatching);
const matchings = [];
if (this.points.length % 2 !== 0) {
return matchings;
}
const thisMatching = this;
const points = this.points;
const nbPoints = points.length;
const assigns = [];
// Value in assigns:
// false: not assigned
// number: index of the first point of a segment
// true: index of the second point of a segment
// Fill with first assignation
for (let i = 0; i < nbPoints; ++i) {
assigns.push(i % 2 === 0
? i + 1
: true);
}
var available = new Set(); // available indices
const backtrackPos = function () { // return previous position with assignation
for (let i = nbPoints - 1; i >= 0; --i) {
if (typeof assigns[i] === "number") {
return i;
}
}
return null;
};
const nextPointIndex = function (pos, first=0) { // return next point index
for (let i = Math.max(first, pos + 1); i < nbPoints; ++i) {
if (available.has(i)) {
return i;
}
}
return null;
};
const assign = function (pos, pointIndex) { // assign two related indices
available.delete(pos);
available.delete(pointIndex);
assigns[pos] = pointIndex;
assigns[pointIndex] = true;
};
const unassign = function (pos) { // unassign two related indices
available.add(pos);
available.add(assigns[pos]);
assigns[assigns[pos]] = false;
assigns[pos] = false;
};
const toMatching = function () { // return a new perfect matching corresponding to assignations, or null
const matching = new Matching();
matching._points = thisMatching._points;
for (let i = 0; i < nbPoints; ++i) {
if (typeof assigns[i] === "number") {
const segment = new Segment(points[i], points[assigns[i]]);
if (matching.segmentIsIntersect(segment)) {
return null;
}
matching.segmentAdd(segment);
}
}
return matching;
};
while (true) {
// One possible matching
const matching = toMatching();
if (matching !== null) {
matchings.push(matching);
}
// Search first position to modify
var pos;
var next;
do {
pos = backtrackPos();
if (pos === null) {
this._numberPerfectMatchingsIfCalculated = matchings.length;
if (disjointMatching || compatibleMatching) { // keep only "good" matchings
for (let i = 0; i < matchings.length; ++i) {
if ((disjointMatching && !this.isDisjoint(matchings[i]))
|| (compatibleMatching && !this.isCompatible(matchings[i]))) {
matchings.splice(i, 1);
--i;
}
}
}
return matchings;
}
next = nextPointIndex(pos, assigns[pos] + 1);
unassign(pos);
} while (next === null);
// Set values from pos
assign(pos, next);
for (let i = pos + 1; i < nbPoints; ++i) {
if ((next !== null) && (assigns[i] === false)) {
next = nextPointIndex(i);
assign(i, next);
}
}
}
}
/**
* Returns an upper bound of number
* of all possible perfect matchings with the points of this matching.
*
* @returns {Number}
*/
allPerfectMatchingsUppedBound() {
if ((this.points.length === 0) || (this.points.length % 2 !== 0)) {
return 0;
}
var number = 1;
for (let i = 3; i < this._points.length; i += 2) {
number *= i;
}
return number;
}
/**
* Returns the canonical perfect matching
* corresponding to these points.
*
* @returns {Matching}
*/
canonical() {
assert(this._points.length % 2 === 0, this._points.length);
const matching = new Matching();
matching._points = this._points;
for (let i = 0; i < this._points.length; i += 2) {
const segment = new Segment(matching._points[i], matching._points[i + 1]);
matching.segmentAdd(segment);
}
return matching;
}
/**
* Empty sets of points and segments,
* and intermediary linked matchings.
*/
clear() {
this.clearIntermediaryLinkedMatchings();
this._points.splice(0, this._points.length);
this._segments.splice(0, this._segments.length);
this.clearIfModifyPoints();
}
/**
* Reset some data when add or remove point.
*/
clearIfModifyPoints() {
this._numberPerfectMatchingsIfCalculated = null;
for (let matching of this._linkedMatchings) {
matching._numberPerfectMatchingsIfCalculated = null;
}
}
/**
* Remove all intermediary linked matchings.
*/
clearIntermediaryLinkedMatchings() {
assert(this._linkedMatchings.length >= 2, this._linkedMatchings);
for (let i = 1; i < this._linkedMatchings.length - 1; ++i) {
this._linkedMatchings[i]._linkedMatchings = null;
}
this._linkedMatchings.splice(1, this._linkedMatchings.length - 2);
this._linkedMatchings[1]._linkedMatchings = this._linkedMatchings;
}
/**
* Returns a set of segments in common between this matching and other.
*
* @param {Matching} other
*
* @returns {Set} Set of Segment
*/
commonSegments(other) {
assert(other instanceof Matching, other);
const segments = new Set();
for (let segment of this._segments) {
for (let otherSegment of other._segments) {
if (segment.isEquals(otherSegment)) {
segments.add(segment);
}
}
}
return segments;
}
/**
* Returns a set of segments in common between this matching
* and previous or next one.
*
* @returns {Set} Set of Segment
*/
commonSegmentsWithConsecutiveMatchings() {
const i = this.linkedMatchingsIndex();
const left = (i > 0
? this.commonSegments(this._linkedMatchings[i - 1])
: new Set());
const right = (i < this._linkedMatchings.length - 1
? this.commonSegments(this._linkedMatchings[i + 1])
: new Set());
return setUnion(left, right);
}
/**
* Returns true iff the matching is the canonical perfect matching.
*
* @returns {boolean}
*/
isCanonical() {
if ((this._points.length % 2 !== 0) || (2*this._segments.length < this._points.length)) {
// Odd number of points or not enough segments, impossible to be perfect
return false;
}
const canonical = this.canonical();
return this.isEquals(canonical);
}
/**
* Returns true iff matching and other are compatible
* (union have no intersection segments, without their endpoints).
*
* @param {Matching} other
*
* @returns {boolean}
*/
isCompatible(other) {
assert(other instanceof Matching, other);
const segments = new Set();
for (let segment of this._segments) {
for (let otherSegment of other._segments) {
if (!segment.isEquals(otherSegment) && segment.isProperIntersect(otherSegment)) {
return false;
}
}
}
return true;
}
/**
* Returns true iff matching and other are disjoint (no common segments).
*
* @param {Matching} other
*
* @returns {boolean}
*/
isDisjoint(other) {
assert(other instanceof Matching, other);
if (this._segments === other._segments) {
return false;
}
for (let segment of this._segments) {
for (let otherSegment of other._segments) {
if (segment.isEquals(otherSegment)) {
return false;
}
}
}
return true;
}
/**
* Returns true iff are equals matchings (same points and same segments).
*
* @param {Matching} other
*
* @returns {boolean}
*/
isEquals(other) {
assert(other instanceof Matching, other);
if ((this._points === other._points)
&& (this._segments === other._segments)) {
return true;
}
if ((this._points.length !== other._points.length)
|| (this._segments.length !== other._segments.length)
|| !arrayIsEquals(this._points, other._points,
function (p, q) { return p.compare(q); })) {
return false;
}
for (let i = 0; i < this._segments.length; ++i) {
if (!this._segments[i].isEquals(other._segments[i])) {
return false;
}
}
return true;
}
/**
* Returns a set of all points without segment.
*
* @returns {Set} Set of points
*/
isolatedPoints() {
const points = new Set(this._points);
for (let segment of this._segments) {
points.delete(segment.a);
points.delete(segment.b);
}
return points;
}
/**
* Returns true iff the matching is perfect (each point is degree 1)
*
* @returns {boolean}
*/
isPerfect() {
if ((this._points.length % 2 !== 0) || (2*this._segments.length < this._points.length)) {
// Odd number of points or not enough segments, impossible to be perfect
return false;
}
const points = new Set();
for (let segment of this._segments) {
if (points.has(segment.a) || points.has(segment.b)) {
// Point in at least two segments
return false;
}
points.add(segment.a);
points.add(segment.b);
}
if (points.size !== this._points.length) {
// There is at least one isolated point
return false;
}
return true;
}
/**
* Returns true iff all segment are vertical or horizontal.
*
* @returns {boolean}
*/
isVerticalHorizontal() {
for (let segment of this._segments) {
if (!(segment.isVertical() || segment.isHorizontal())) {
return false;
}
}
return true;
}
/**
* Returns the index of this matching in the sequence of linked matchings.
*
* @returns {integer} >= 0
*/
linkedMatchingsIndex() {
for (let i = 0; i < this._linkedMatchings.length; ++i) {
if (this._linkedMatchings[i] === this) {
return i;
}
}
assert(false);
}
/**
* Returns all informations of all linked matchings in a string :
* # points
* x_0, y_0
* ...
* x_{n-1}, y_{n-1}
*
* # matching
*
* # segment for first matching
* index point a - index point b
* ...
*
* ...
*
* # segment for last matching
* index point a - index point b
* ...
*
* Warning! All point coordinates are rounded to integers.
*
* @returns {String}
*/
matchingsToString() {
const lines = [this._points.length + " points"];
for (let point of this._points) {
lines.push(Math.round(point.x) + ", " + Math.round(point.y));
}
lines.push("");
lines.push(this._linkedMatchings.length + " matchings");
const indices = this.pointsIndices();
for (let matching of this._linkedMatchings) {
lines.push("");
lines.push(matching._segments.length + " segments");
for (let segment of matching._segments) {
lines.push(indices[segment.a] + " - " + indices[segment.b]);
}
}
return lines.join("\n");
}
/**
* Returns the nearest point of the matching
* or null if no nearest point.
*
* @param {Point} point
*
* @returns {Point|null}
*/
nearestPoint(point) {
assert(point instanceof Point, point);
var minDistSqr = Number.POSITIVE_INFINITY;
var minP = null;
for (let p of this._points) {
const distSqr = point.distanceSqr(p);
if (minDistSqr > distSqr) {
minDistSqr = distSqr;
minP = p;
}
}
return (minDistSqr < 10*10
? minP
: null);
}
/**
* Add a point.
*
* @param {Point} point (not already in the matching)
*/
pointAdd(point) {
assert(point instanceof Point, point);
assert(!this.pointIsInMatching(point), point);
sortedArrayInsert(this._points, point, function (p, q) { return p.compare(q); } );
this.clearIfModifyPoints();
}
/**
* Returns an associative table Point: (it index in the sequence of points).
*
* @returns {Map} Point:(integer >= 0)
*/
pointsIndices() {
const indices = {};
for (let i = 0; i < this._points.length; ++i) {
indices[this._points[i]] = i;
}
return indices;
}
/**
* Returns true iff point is a point of the matching.
*
* @param {Point} point
*
* @returns {boolean}
*/
pointIsInMatching(point) {
assert(point instanceof Point, point);
for (let p of this._points) {
if (point.isEquals(p)) {
return true;
}
}
return false;
}
/**
* Remove the existing point.
*
* If there is a segment with this point
* then remove this segment.
*
* If removeInLinkedMatchings
* then remove also segments in all linked matchings.
*
* @param {Point} point (must be in the matching)
* @param {boolean} removeInLinkedMatchings
*/
pointRemove(point, removeInLinkedMatchings=true) {
assert(point instanceof Point, point);
assert(this.pointIsInMatching(point), point);
assert(typeof removeInLinkedMatchings === "boolean", removeInLinkedMatchings);
// Remove all segment on this point
for (let i = 0; i < this._segments.length; ++i) {
if (this._segments[i].isExtremityPoint(point)) {
this._segments.splice(i, 1);
--i;
}
}
if (removeInLinkedMatchings) {
// For each other linked matchings, remove all segment on this point
for (let linkedMatching of this._linkedMatchings) {
if (linkedMatching !== this) {
linkedMatching.pointRemove(point, false);
}
}
}
// Remove point
arrayRemoveFirst(this._points, point,
function (a, b) { return a.compare(b); });
this.clearIfModifyPoints();
}
/**
* Returns a set of segments that intersect (without their endpoints) one of other.
*
* @param {Matching} other
*
* @returns {Set} Set of Segment
*/
properIntersectSegments(other) {
assert(other instanceof Matching, other);
const segments = new Set();
for (let segment of this._segments) {
for (let otherSegment of other._segments) {
if (!segment.isEquals(otherSegment) && segment.isProperIntersect(otherSegment)) {
segments.add(segment);
}
}
}
return segments;
}
/**
* Returns a set of segments that intersect (without their endpoints)
* one of previous or next matching.
*
* @returns {Set} Set of Segment
*/
properIntersectSegmentsWithConsecutiveMatchings() {
const i = this.linkedMatchingsIndex();
const left = (i > 0
? this.properIntersectSegments(this._linkedMatchings[i - 1])
: new Set());
const right = (i < this._linkedMatchings.length - 1
? this.properIntersectSegments(this._linkedMatchings[i + 1])
: new Set());
return setUnion(left, right);
}
/**
* Add a segment.
*
* @param {Segment} segment (not already in the matching)
*/
segmentAdd(segment) {
assert(segment instanceof Segment, segment);
assert(!this.segmentIsInMatching(segment), segment);
segment = segment.ordonned(); // segment with point a <= point b
sortedArrayInsert(this._segments, segment, function (a, b) { return a.compare(b); } );
}
/**
* Returns true iff segment is a segment of the matching.
*
* @param {Segment} segment
*
* @returns {boolean}
*/
segmentIsInMatching(segment) {
assert(segment instanceof Segment, segment);
for (let s of this._segments) {
if (segment.isEquals(s)) {
return true;
}
}
return false;
}
/**
* Returns true iff segment intersect (*with* their endpoints) a segment of the matching.
*
* @param {Segment} segment
*
* @returns {boolean}
*/
segmentIsIntersect(segment) {
assert(segment instanceof Segment, segment);
for (let s of this._segments) {
if (segment.isIntersect(s)) {
return true;
}
}
return false;
}
/**
* Remove the existing segment.
*
* @param {Segment} segment (must be in the matching)
*/
segmentRemove(segment) {
assert(segment instanceof Segment, segment);
assert(this.segmentIsInMatching(segment), segment);
arrayRemoveFirst(this._segments, segment,
function (a, b) { return a.compare(b); });
}
/**
* Set segments to be the canonical perfect matching
* corresponding to these points.
*
* @returns {Matching}
*/
setCanonical() {
this._segments = this.canonical().segments;
}
/**
* Calculate all possible perfect matchings
* with the points of this matching
* and set this list as the linked matchings.
*
* If disjointMatching
* then keep only perfect matching disjoint with this matching.
*
* If compatibleMatching
* then keep only perfect matching disjoint with this matching.
*
* @param {Boolean} disjointMatching
* @param {Boolean} compatibleMatching
*/
setPerfectMatchings(disjointMatching, compatibleMatching) {
assert(typeof disjointMatching === "boolean", disjointMatching);
assert(typeof compatibleMatching === "boolean", compatibleMatching);
assert(this._linkedMatchings.length >= 2, this._linkedMatchings[0].length);
this.clearIntermediaryLinkedMatchings();
const matchings = this.allPerfectMatchings(disjointMatching, compatibleMatching);
if (matchings.length === 0) {
return;
}
const left = this._linkedMatchings[0];
if (!left.isPerfect()) {
// Set left matching with first perfect matching
left._segments = matchings[0]._segments;
}
const right = this._linkedMatchings[this._linkedMatchings.length - 1];
if (right.isEquals(left) || !right.isPerfect()) {
// Set right matching with last perfect matching
right._segments = matchings[matchings.length - 1]._segments;
}
if ((matchings.length > 1) && right.isEquals(left)) {
// Set right matching with previous perfect matching
right._segments = matchings[matchings.length - 2]._segments;
}
if (right.isEquals(left)) {
// In the case where there is only one perfect matching,
// then set right with a copy of segments.
right._segments = right._segments.slice(0);
}
this._linkedMatchings.splice(1, 1); // remove right from the list of linked matchings
// Add all perfect matchings different to left and right
for (let matching of matchings) {
if (!matching.isEquals(left) && !matching.isEquals(right)) {
this._linkedMatchings.push(matching);
}
}
// Add right perfect matching
this._linkedMatchings.push(right);
// Set all list of linked matchings
for (let matching of this._linkedMatchings) {
matching._linkedMatchings = this._linkedMatchings;
}
}
/**
* Set the list of linked matchings
* to be a transformation (a list of perfect matchings two to two compatible)
* from this matching to the last linked matching.
*
* If disjointTransformation
* then search a disjoint transformation.
*
* Returns true if a transformation was found,
* else return false.
*
* The two utmost matchings must be perfect and different.
*
* Warning! Only transformations of length 2 and 3 are implemented.
*
* FIXME! Naive algorithm that build before all perfect matchings and try possibilities.
*
*
* @param {Boolean} disjointTransformation
*
* @returns {boolean}
*/
setTransformation(disjointTransformation) {
assert(typeof disjointTransformation === "boolean", disjointTransformation);
assert(this._linkedMatchings.length >= 2, this._linkedMatchings[0].length);
assert(this.points.length % 2 === 0, this.points.length);
const matchings = this.allPerfectMatchings(false, false);
assert(matchings.length >= 2, matchings.length);
const left = this._linkedMatchings[0];
const right = this._linkedMatchings[this._linkedMatchings.length - 1];
assert(left.isPerfect(), left);
assert(right.isPerfect(), right);
assert(!left.isEquals(right));
this.clearIntermediaryLinkedMatchings();
this._linkedMatchings.splice(1, 1);
// Remove left and right matchings from the matchings list
for (let i = 0; i < matchings.length; ++i) {
const matching = matchings[0];
if (matching.isEquals(left) || matching.isEquals(right)) {
matchings.splice(i, 1);
}
}
// Try with only 1 intermediary matching
for (let matching of matchings) {
if ((!disjointTransformation
|| (matching.isDisjoint(left) && matching.isDisjoint(right)))
&& matching.isCompatible(left) && matching.isCompatible(right)) {
this._linkedMatchings.push(matching);
break;
}
}
if (this._linkedMatchings.length === 1) {
// Try with with 2 intermediary matchings
var found = false;
for (let matching1 of matchings) {
if ((!disjointTransformation || matching1.isDisjoint(left))
&& matching1.isCompatible(left)) {
for (let matching2 of matchings) {
if ((!disjointTransformation
|| (matching2.isDisjoint(matching1) && matching2.isDisjoint(right)))
&& matching2.isCompatible(matching1) && matching2.isCompatible(right)) {
this._linkedMatchings.push(matching1);
this._linkedMatchings.push(matching2);
found = true;
break;
}
}
if (found) {
break;
}
}
}
}
// Add the right matching
this._linkedMatchings.push(right);
// Set all list of linked matchings
for (let matching of this._linkedMatchings) {
matching._linkedMatchings = this._linkedMatchings;
}
return (this._linkedMatchings.length > 2);
}
/**
* Set segments at random to be a perfect matching
* corresponding to these points.
*
* @returns {Matching}
*/
shuffleSegments() {
if (this._segments.length <= 1) {
return;
}
const maxNb = getRandomInteger(3, 5);
for (let nb = 0; nb < maxNb; ++nb) {
for (let i = 0; i < this._segments.length; ++i) {
const j = getRandomInteger(0, this._segments.length);
if (i === j) {
continue;
}
const segmentI = this._segments[i];
const segmentJ = this._segments[j];
this.segmentRemove(segmentI);
this.segmentRemove(segmentJ);
const segmentA = new Segment(segmentI.a, segmentJ.a);
const segmentB = new Segment(segmentI.b, segmentJ.b);
var keep = false;
if (!this.segmentIsIntersect(segmentA)) {
this.segmentAdd(segmentA);
if (!this.segmentIsIntersect(segmentB)) {
this.segmentAdd(segmentB);
keep = true;
}
else {
this.segmentRemove(segmentA);
}
}
if (!keep) {
this.segmentAdd(segmentI);
this.segmentAdd(segmentJ);
}
}
}
}
}