47:
92:. Using bitmaps in modeling polygon shapes has many drawbacks. One of the drawbacks is that the memory usage can be very large, since the resolution of polygons is proportional to the number of bits used to represent polygons. The higher the resolution is desired, the more the number of bits is required.
76:
60:
332:
208:
20:
301:
70:
437:
167:
165:
Katz, Matthew J.; Overmars, Mark H.; Sharir, Micha (1992), "Efficient hidden surface removal for objects with small union size",
377:
391:
315:
457:
424:
296:
462:
36:
133:
99:). A list of papers using plane sweep algorithms for Boolean operations on polygons can be found in References below.
343:
402:
65:
243:
Nievergelt, J.; Preparata, F. P. (October 1982). "Plane-Sweep
Algorithms for Intersecting Geometric Figures".
144:
252:
128:
32:
444:, C++ and COM libraries for 2D polygons (optimized for large polygon sets, built-in spatial indices).
282:
204:, and Otfried Schwarzkopf, Computational Geometry - Algorithms and Applications, Second Edition, 2000
96:
257:
139:
46:
329:
222:
270:
95:
Modern implementations for
Boolean operations on polygons tend to use plane sweep algorithms (or
40:
229:
214:
28:
262:
176:
107:
441:
428:
336:
123:
434:
103:
401:, an open-source freeware library (written in Delphi, C++ and C#) that's based on the
451:
201:
181:
356:
274:
211:, IEEE Transactions on Computers, Vol. C-28, No. 9, September 1979, pp. 643–647
136:, a method of defining three-dimensional shapes using a similar set of operations
398:
322:
218:
111:
421:
236:
225:, IEEE Transactions on Computers, Vol. C-29. No. 7, July 1980, pp. 571–577
285:," Computer Vision, Graphics, and Image Processing, 30, 1985, pp. 249–268
88:
Early algorithms for
Boolean operations on polygons were based on the use of
370:
266:
223:
An
Optimal Worst Case Algorithm for Reporting Intersections of Rectangles
89:
24:
330:
compared performance and memory utilization of three polygon clippers
414:
408:
384:
45:
27:
in computer graphics. These sets of operations are widely used in
147:, a C library which computes the results of clipping operations
359:, solutions to mathematical problems with 2D and 3D Polygons.
209:
Algorithms for
Reporting and Counting Geometric Intersections
363:
411:, a safe Rust wrapper for Angus Johnson's Clipper2 library.
349:
239:, 18th Design Automation Conference, 1981, pp. 571–579
232:, 18th Design Automation Conference, 1981, pp. 555–562
23:(AND, OR, NOT, XOR, ...) operating on one or more sets of
394:, a C++ library, which extends the Schutte algorithm.
230:
An O(N log N) Algorithm for
Boolean Mask Operations
281:Thomas Ottmann, Peter Widmayer, and Derick Wood, "
380:, a FORTRAN library based on the Vatti algorithm.
366:, a free C library for 2D polygons (BSD license).
348:A commercial library for 3D Boolean operations:
283:A Fast Algorithm for the Boolean Masking Problem
417:, a commercial library available in C++ and C#.
168:Computational Geometry: Theory and Applications
8:
43:physical design and verification software).
110:of the same direction may be performed in
256:
207:Jon Louis Bentley and Thomas A. Ottmann,
180:
342:A comparison of 5 clipping libraries at
237:Efficient Boolean Operations on IC Masks
157:
7:
387:, a polygon clipper written in C++.
431:, General Polygon Clipper library.
77:Weiler–Atherton clipping algorithm
61:Greiner–Hormann clipping algorithm
14:
323:compared three clipping libraries
297:UIUC Computational Geometry Pages
373:, a C++ library for 2D polygons.
200:Mark de Berg, Marc van Kreveld,
316:comparison of polygon clippers
314:Michael Leonov has compiled a
17:Boolean operations on polygons
1:
357:comp.graphics.algorithms FAQ
302:Constructive planar geometry
182:10.1016/0925-7721(92)90024-M
71:Sutherland–Hodgman algorithm
50:Different boolean operations
134:Constructive solid geometry
479:
344:rogue-modron.blogspot.com
245:Communications of the ACM
79:(special case algorithm)
73:(special case algorithm)
66:Vatti clipping algorithm
321:Angus Johnson has also
145:General Polygon Clipper
129:Computational geometry
102:Boolean operations on
51:
350:sgCore C++/C# library
267:10.1145/358656.358681
97:Sweep line algorithms
49:
458:Geometric algorithms
463:Geometry processing
140:Geometry processing
440:2012-11-16 at the
427:2011-02-27 at the
335:2012-11-16 at the
235:James A. Wilmore,
52:
41:integrated circuit
21:Boolean operations
390:Michael Leonov's
383:Klamer Schutte's
376:David Kennison's
369:Klaas Holwerda's
362:Matthias Kramm's
304:, by Dave Eberly.
215:Jon Louis Bentley
108:monotone polygons
29:computer graphics
470:
397:Angus Johnson's
278:
260:
228:Ulrich Lauther,
187:
185:
184:
162:
84:Uses in software
478:
477:
473:
472:
471:
469:
468:
467:
448:
447:
442:Wayback Machine
429:Wayback Machine
403:Vatti algorithm
337:Wayback Machine
328:SINED GmbH has
293:
288:
251:(10): 739–747.
242:
196:
191:
190:
164:
163:
159:
154:
124:Boolean algebra
120:
104:convex polygons
86:
57:
12:
11:
5:
476:
474:
466:
465:
460:
450:
449:
446:
445:
432:
418:
412:
409:clipper2 crate
406:
395:
388:
381:
374:
367:
360:
353:
346:
340:
326:
319:
311:
310:
306:
305:
299:
292:
291:External links
289:
287:
286:
279:
258:10.1.1.83.3275
240:
233:
226:
212:
205:
197:
195:
192:
189:
188:
175:(4): 223–234,
156:
155:
153:
150:
149:
148:
142:
137:
131:
126:
119:
116:
85:
82:
81:
80:
74:
68:
63:
56:
53:
13:
10:
9:
6:
4:
3:
2:
475:
464:
461:
459:
456:
455:
453:
443:
439:
436:
433:
430:
426:
423:
420:Alan Murta's
419:
416:
413:
410:
407:
404:
400:
396:
393:
389:
386:
382:
379:
375:
372:
368:
365:
361:
358:
354:
351:
347:
345:
341:
338:
334:
331:
327:
324:
320:
317:
313:
312:
308:
307:
303:
300:
298:
295:
294:
290:
284:
280:
276:
272:
268:
264:
259:
254:
250:
246:
241:
238:
234:
231:
227:
224:
220:
216:
213:
210:
206:
203:
202:Mark Overmars
199:
198:
193:
183:
178:
174:
170:
169:
161:
158:
151:
146:
143:
141:
138:
135:
132:
130:
127:
125:
122:
121:
117:
115:
113:
109:
105:
100:
98:
93:
91:
83:
78:
75:
72:
69:
67:
64:
62:
59:
58:
54:
48:
44:
42:
38:
34:
30:
26:
22:
19:are a set of
18:
392:poly_Boolean
248:
244:
194:Bibliography
172:
166:
160:
101:
94:
87:
16:
15:
219:Derick Wood
112:linear time
452:Categories
435:PolygonLib
55:Algorithms
253:CiteSeerX
35:, and in
438:Archived
425:Archived
385:Clippoly
378:Polypack
333:Archived
309:Software
275:16606107
118:See also
25:polygons
399:Clipper
371:Boolean
364:gfxpoly
90:bitmaps
415:GeoLib
273:
255:
271:S2CID
152:Notes
355:The
217:and
106:and
39:(in
422:GPC
263:doi
177:doi
37:EDA
33:CAD
454::
269:.
261:.
249:25
247:.
221:,
171:,
114:.
31:,
405:.
352:.
339:.
325:.
318:.
277:.
265::
186:.
179::
173:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
