/
detectContourHoles.ts
149 lines (129 loc) · 4 KB
/
detectContourHoles.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/**
* Functions for detecting and dealing with holes within contours.
* Expected Contour format:
* {
* type,
* contourPoints
* }
*/
/**
* Checks if point is inside polygon defined by vertices array
* Code from
* https://stackoverflow.com/questions/22521982/check-if-point-is-inside-a-polygon
* most original version based on:
* https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html/pnpoly.html
* @param {*} point
* @param {*} vertices
* @returns
*/
const getIsPointInsidePolygon = (point, vertices) => {
// Todo: this is a duplicated logic we should merge it with the other one
// which is containsPoint in the utilities
const x = point[0];
const y = point[1];
let inside = false;
for (let i = 0, j = vertices.length - 1; i < vertices.length; j = i++) {
const xi = vertices[i][0],
yi = vertices[i][1];
const xj = vertices[j][0],
yj = vertices[j][1];
const intersect =
yi > y != yj > y && x < ((xj - xi) * (y - yi)) / (yj - yi) + xi;
if (intersect) {
inside = !inside;
}
}
return inside;
};
/**
* Check if inner contour is completely surrounded by outer contour.
* @param {*} outerContour
* @param {*} innerContour
* @returns
*/
function checkEnclosed(outerContour, innerContour, points) {
const vertices = [];
outerContour.contourPoints.forEach((point) => {
vertices.push([points[point][0], points[point][1]]);
});
let pointsNotEnclosed = 0;
innerContour.contourPoints.forEach((point) => {
const result = getIsPointInsidePolygon(
[points[point][0], points[point][1]],
vertices
);
//console.log(result);
if (!result) {
pointsNotEnclosed++;
}
});
return pointsNotEnclosed === 0;
}
/**
* Check if contours have holes, if so update contour accordingly
* @param {*} polyData
* @param {*} bypass
*/
export function processContourHoles(contours, points, useXOR = true) {
//console.log(points);
// Add non-closed planars to contour list
const retContours = contours.filter(
(contour) => contour.type !== 'CLOSED_PLANAR'
);
// Find closed planar contours
const closedContours = contours.filter(
(contour) => contour.type === 'CLOSED_PLANAR'
);
// Iterate through each contour in list check for contours that have holes
const contourWithHoles = [];
let contourWithoutHoles = [];
closedContours.forEach((contour, index) => {
const holes = [];
// Check if any other contour is a hole surrounded by current contour
closedContours.forEach((hContour, hIndex) => {
if (index != hIndex) {
// Check if inner loop contour is a hole of outer loop contour
if (checkEnclosed(contour, hContour, points)) {
holes.push(hIndex);
}
}
});
// Check if holes were found
if (holes.length > 0) {
// Note current contour and reference of its holes
contourWithHoles.push({
contour,
holes,
});
} else {
// Note contour index without holes
contourWithoutHoles.push(index);
}
});
if (useXOR) {
// XOR method
contourWithHoles.forEach((contourHoleSet) => {
// Modify contour with hole to type CLOSEDPLANAR_XOR
contourHoleSet.contour.type = 'CLOSEDPLANAR_XOR';
retContours.push(contourHoleSet.contour);
contourHoleSet.holes.forEach((holeIndex) => {
// Modify hole type to CLOSEDPLANAR_XOR
// and add to contour list to be returned
closedContours[holeIndex].type = 'CLOSEDPLANAR_XOR';
retContours.push(closedContours[holeIndex]);
// Remove hole from list of contours without holes
contourWithoutHoles = contourWithoutHoles.filter((contourIndex) => {
return contourIndex !== holeIndex;
});
});
});
// Add remaining contours to list (neither hole nor have holes)
contourWithoutHoles.forEach((contourIndex) => {
retContours.push(closedContours[contourIndex]);
});
} else {
// Keyhole method, not implemented
}
return retContours;
}
export default { processContourHoles };