js多邊形(不規則的形狀)之合併

  1 /* Polygon 多邊形
  2 
  3 parameter: 
  4     path: Array[x, y];
  5 
  6 attribute:
  7 
  8     //只讀屬性
  9     path: Array[x, y]; 
 10 
 11 method:
 12     add(x, y): this;             //x,y添加至path;
 13     containsPoint(x, y): Bool;    //x,y是否在多邊形的內部(註意: 在路徑上也返回 true)
 14     merge(polygon): this;         //合併; 假設polygon與this存在重疊的部分
 15     
 16 */
 17 class Polygon{
 18 
 19     #position = null;
 20     #path2D = null;
 21 
 22     get path(){
 23         
 24         return this.#position;
 25 
 26     }
 27 
 28     constructor(path = []){
 29         this.#position = path;
 30 
 31         this.#path2D = new Path2D();
 32         
 33         var len = path.length;
 34         if(len >= 2){
 35             if(len % 2 !== 0){
 36                 len -= 1;
 37                 path.splice(len, 1);
 38             }
 39 
 40             const con = this.#path2D;
 41             con.moveTo(path[0], path[1]);
 42             for(let k = 2; k < len; k+=2) con.lineTo(path[k], path[k+1]);
 43             
 44         }
 45 
 46     }
 47 
 48     add(x, y){
 49         this.#position.push(x, y);
 50         this.#path2D.lineTo(x, y);
 51         return this;
 52     }
 53 
 54     containsPoint(x, y){
 55         
 56         return UTILS.emptyContext.isPointInPath(this.#path2D, x, y);
 57 
 58     }
 59 
 60     toPoints(){
 61         const path = this.path, len = path.length, result = [];
 62         
 63         for(let k = 0; k < len; k += 2) result.push(new Point(path[k], path[k+1]));
 64 
 65         return result;
 66     }
 67 
 68     toLines(){
 69         const path = this.path, len = path.length, result = [];
 70         
 71         for(let k = 0, x = NaN, y; k < len; k += 2){
 72 
 73             if(isNaN(x)){
 74                 x = path[k];
 75                 y = path[k+1];
 76                 continue;
 77             }
 78 
 79             const line = new Line(x, y, path[k], path[k+1]);
 80             
 81             x = line.x1;
 82             y = line.y1;
 83 
 84             result.push(line);
 85 
 86         }
 87 
 88         return result;
 89     }
 90 
 91     merge(polygon){
 92 
 93         const linesA = this.toLines(), linesB = polygon.toLines(), nodes = [], newLines = [];
 94 
 95         //收集所有的交點 (保存至 line)
 96         for(let k = 0, lenB = linesB.length, lenA = linesA.length, point = new Point(), pointB = new Point(); k < lenA; k++){
 97             const lineA = linesA[k];
 98             lineA.nodes = [];
 99 
100             for(let i = 0; i < lenB; i++){
101                 const lineB = linesB[i];
102                 if(lineB.nodes === undefined) lineB.nodes = [];
103                 if(lineA.intersectPoint(lineB, point) === point){
104                     const node = {
105                         lineA: lineA, 
106                         lineB: lineB, 
107                         point: point.clone(),
108                         disA: point.distanceCompare(pointB.set(lineA.x, lineA.y)),
109                         disB: point.distanceCompare(pointB.set(lineB.x, lineB.y)),
110                     }
111                     lineA.nodes.push(node);
112                     lineB.nodes.push(node);
113                     nodes.push(node);
114                 }
115 
116             }
117 
118         }
119 
120         //獲取介入點
121         var startLine = null;
122         for(let k = 0, len = nodes.length, node; k < len; k++){
123             node = nodes[k];
124             if(node.lineA.nodes.length === 1 || node.lineA.nodes.length === 2 && 
125             node.lineB.nodes.length === 1 || node.lineB.nodes.length === 2){
126                 startLine = node.lineA;
127                 break;
128             }
129         }
130 
131         if(startLine === null){
132             console.warn('Polygon: 找不到介入點, 終止了合併');
133             return newLines;
134         }
135 
136         //交點以原點為目標排序
137         for(let k = 0, sotr = function (a,b){return a.disA - b.disA;}, countA = linesA.length; k < countA; k++) linesA[k].nodes.sort(sotr);
138         for(let k = 0, sotr = function (a,b){return a.disB - b.disB;}, countB = linesB.length; k < countB; k++) linesB[k].nodes.sort(sotr);
139 
140         const result_loop = {
141             lines: linesA,
142             loopType: 'next',
143             line: startLine,
144             count: startLine.nodes.length,
145             indexed: linesA.indexOf(startLine),
146         },
147         
148         //遍歷某條線
149         loop = (lines, index, loopType) => {
150             const length = lines.length, indexed = index, model = lines === linesA ? polygon : this;
151 
152             var line = lines[index];
153 
154             while(true){
155                 if(loopType === 'back' && newLines.includes(line) === false && model.containsPoint(line.x, line.y) === false) newLines.push(line);
156                 if(loopType === 'next') index = index === length - 1 ? 0 : index + 1;
157                 else if(loopType === 'back') index = index === 0 ? length - 1 : index - 1;
158 
159                 line = lines[index];
160                 if(loopType === 'next' && newLines.includes(line) === false && model.containsPoint(line.x, line.y) === false) newLines.push(line);
161 
162                 result_loop.count = line.nodes.length;
163                 if(result_loop.count !== 0){
164                     result_loop.lines = lines;
165                     result_loop.loopType = loopType;
166                     result_loop.line = line;
167                     result_loop.indexed = index;
168                     return result_loop;
169                 }
170                 
171                 if(indexed === index) break;
172 
173             }
174 
175         },
176 
177         //更新或創建交點的索引
178         setNodeIndex = (lines, index, loopType) => {
179             const line = lines[index], count = line.nodes.length;
180             if(loopType === undefined) loopType = line.loopType;
181             else if(line.loopType === undefined) line.loopType = loopType;
182 
183             if(loopType === undefined) return;
184 
185             if(line.nodeIndex === undefined){
186                 line.nodeIndex = loopType === 'next' ? 0 : count - 1;
187                 line.nodeState = count === 1 ? 'end' : 'start';
188                 line._loopType = loopType;
189             }
190 
191             else{
192                 if(line.nodeState === 'end' || line.nodeState === ''){
193                     line.nodeState = '';
194                     return;
195                 }
196 
197                 if(line._loopType === 'next'){
198                     line.nodeIndex += 1;
199 
200                     if(line.nodeIndex === count - 1) line.nodeState = 'end';
201                     else line.nodeState = 'run';
202                 }
203 
204                 else if(line._loopType === 'back'){
205                     line.nodeIndex -= 1;
206 
207                     if(line.nodeIndex === 0) line.nodeState = 'end';
208                     else line.nodeState = 'run';
209                 }
210 
211             }
212 
213         },
214 
215         //只有在跳線的時候才執行此方法, 如果跳線的話: 某條線上的交點必然在兩端;
216         getLoopType = (lines, index, nodePoint) => {
217             const line = lines[index], lineNext = lines[index === lines.length - 1 ? 0 : index + 1],
218 
219             model = lines === linesA ? polygon : this,
220             isLineBack = newLines.includes(line) === false && model.containsPoint(line.x, line.y) === false,
221             isLineNext = newLines.includes(lineNext) === false && model.containsPoint(lineNext.x, lineNext.y) === false;
222             
223             if(isLineBack && isLineNext){
224                 const len = line.nodes.length;
225                 if(len >= 2){
226                     if(line.nodes[len - 1].point.equals(nodePoint)) return 'next';
227                     else if(line.nodes[0].point.equals(nodePoint)) return 'back';
228                 }
229                 
230                 else console.warn('路徑複雜', line);
231                 
232             }
233 
234             else if(isLineNext){
235                 return 'next';
236             }
237 
238             else if(isLineBack){
239                 return 'back';
240             }
241 
242             return '';
243         },
244 
245         //處理擁有交點的線
246         computeNodes = v => {
247             if(v === undefined) return;
248 
249             setNodeIndex(v.lines, v.lines.indexOf(v.line), v.loopType);
250             
251             //
252             const node = v.line.nodes[v.line.nodeIndex], model = v.lines === linesA ? polygon : this;
253             if(newLines.includes(node.point) === false) newLines.push(node.point);
254 
255             var lines, index, loopType, line;
256 
257             //
258             const lineR = v.lines === linesA ? node.lineB : node.lineA, 
259             linesR = lineR === node.lineA ? linesA : linesB;
260             setNodeIndex(linesR, linesR.indexOf(lineR));
261 
262             const nodeState = lineR.nodeState !== undefined ? lineR.nodeState : v.line.nodeState;
263 
264             switch(nodeState){
265 
266                 //不跳線
267                 case 'run': 
268                     lines = v.lines; 
269                     index = v.indexed; 
270                     loopType = v.loopType;
271                     computeNodes(loop(lines, index, loopType));
272                     break;
273 
274                 //跳線
275                 case 'start':
276                 case 'end': 
277                     lines = model === polygon ? linesB : linesA;
278                     line = lines === linesA ? node.lineA : node.lineB;
279                     index = lines.indexOf(line); 
280                     loopType = getLoopType(lines, index, node.point);
281                     
282                     if(loopType !== ''){
283                         line.loopType = loopType;
284                         //if(loopType === 'back' && newLines.includes(line) === false && model.containsPoint(line.x, line.y) === false) newLines.push(line);
285                         computeNodes(loop(lines, index, loopType));
286                     }
287                     break;
288                 
289 
290                 default: break;
291 
292             }
293 
294         }
295 
296         computeNodes(result_loop);
297     
298         return newLines;
299     }
300 
301 }

註意: Polygon 目前並不完美

parameter:

  1 /* PolygonTest 調試類 Polygon (可視化調試: 多邊形之合併)
  2 
  3     無任何屬性, new就完事了!
  4 
  5 */
  6 class PolygonTest{
  7 
  8     constructor(){
  9         const path = [], box = new Box(),
 10 
 11         car = new CanvasAnimateRender({
 12             width: window.innerWidth, 
 13             height: window.innerHeight,
 14         }).render(), 
 15     
 16         cab = car.add(new CanvasAnimateBox()).size(car.box.w, car.box.h, true);
 17         
 18         function draw(obj){
 19             console.log(obj);
 20     
 21             target._redraw();
 22     
 23             obj.forEach((v, i) => {
 24                 const str = String(i), 
 25                 size = cab.textWidth(str, 20), 
 26                 width = size < 20 ? 20 : size;
 27                 
 28                 cab.rect(2, box.set(v.x, v.y, width, width), 2).fill('#fff');
 29                 cab.text(str, '#0000ff', box.pos(v.x + (width - size)/2, v.y));
 30     
 31                 if(v.x1 === undefined) cab.stroke('#ffff00');
 32                 
 33             });
 34     
 35             car.redraw();
 36         }
 37     
 38     
 39         const target = {
 40             title: '測試多邊形之合併(此類並不完美)',
 41             polygonA: null,
 42             polygonB: null,
 43             centerA: new Box(),
 44             centerB: new Box(),
 45             length: 0,
 46             mergeType: 0,
 47     
 48             merge(){
 49                 if(this.polygonA === null || this.polygonB === null) return console.warn('必須已生成兩個多邊形');
 50                 if(this.mergeType === 0) draw(this.polygonA.merge(this.polygonB));
 51                 else draw(this.polygonB.merge(this.polygonA));
 52                 
 53             },
 54     
 55             setPolygonA(){
 56                 this.polygonA = new Polygon(path.concat());
 57                 this.centerA.setFromPolygon(this.polygonA, false);
 58                 update_offsetNum();
 59             },
 60     
 61             setPolygonB(){
 62                 this.polygonB = new Polygon(path.concat());
 63                 this.centerB.setFromPolygon(this.polygonB, false);
 64                 update_offsetNum();
 65             },
 66     
 67             generate(){
 68                 if(path.length < 6) return console.warn('路徑至少需要3個點');
 69     
 70                 if(this.polygonA !== null && this.polygonB !== null){
 71                     const _path = path.concat();
 72                     this.clear();
 73                     _path.forEach(v => path.push(v));
 74                     this.generate();
 75                     return;
 76                 }
 77     
 78                 else{
 79                     cab.path(path, true);
 80     
 81                     if(this.polygonA === null) this.setPolygonA();
 82                     else this.setPolygonB();
 83                     path.length = 0;
 84                     
 85                 }
 86                 
 87                 this._redraw();
 88                 car.redraw();
 89             },
 90     
 91             clear(){
 92                 path.length = 0;
 93                 this.polygonA = this.polygonB = null;
 94                 this.centerA.set(0,0,0,0);
 95                 this.centerB.set(0,0,0,0);
 96                 cab.clear();
 97                 car.clear();
 98             },
 99     
100             clearPath(){
101                 path.length = 0;
102                 cab.clear();
103                 this._redraw();
104                 car.redraw();
105             },
106     
107             _redraw(){
108                 if(this.polygonA !== null){
109                     cab.clear().path(this.polygonA.path).stroke('#00ff00', 1);
110                     this.sign(this.polygonA.path, 'rgba(0,255,0,1)', 'rgba(0,255,0,0.6)');
111                     if(this.polygonB !== null){
112                         cab.path(this.polygonB.path).stroke('#ff0000', 1);
113                         this.sign(this.polygonB.path, 'rgba(255,0,0,1)', 'rgba(255,0,0,0.6)');
114                     }
115                     
116                 }
117                 
118             },
119     
120             //標記線的第一和第二個點
121             sign(path, color1, color2){
122                 cab.rect(5, box.set(path[0]-5, path[1]-5, 10, 10), 2).fill(color1);
123                 cab.rect(5, box.set(path[2]-5, path[3]-5, 10, 10), 2).fill(color2);
124             },
125     
126             //偏移路徑
127             offsetTimer: new Timer(()=>target.offset(), 300, 1, false),
128             offsetNum: new Point(0, 0),
129             offsetTarget: 'polygonA',
130             offsetVN: 'x',
131             offsetPoint: new Point(),
132             offset(){
133                 if(this[this.offsetTarget] === null) return;
134                 path.length = 0;
135                 
136                 const pathNew = path, pathOld = this[this.offsetTarget].path, point = this.offsetPoint, 
137                 center = this.offsetTarget === 'polygonA' ? 'centerA' : 'centerB',
138                 x = this.offsetNum[this.offsetVN] * car.box[this.offsetVN === 'x' ? 'w' : 'h'];
139                 
140                 for(let k = 0, len = pathOld.length; k < len; k+=2){
141                     point.set(pathOld[k], pathOld[k+1]);
142                     point[this.offsetVN] = point[this.offsetVN] - this[center][this.offsetVN] + x;
143                     pathNew.push(point.x, point.y);
144                 }
145     
146                 this[this.offsetTarget === 'polygonA' ? 'setPolygonA' : 'setPolygonB']();
147                 path.length = 0;