Intersection removal for simple polygons

被引：0

作者：

Lahorani, S

Krithivasan, K

机构：

[1] Dept. of Comp. Sci. and Engineering, Indian Institute of Technology

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1997年 / 64卷 / 3-4期

关键词：

computational geometry; simple polygons; intensity of collision;

D O I：

10.1080/00207169708804585

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given two intersecting simple polygons A and B and a direction, theta, we have to find the minimum distance by which B should be translated along direction theta so that A and B no longer intersect. We present two algorithms for this problem for the case that A and B are in 2 dimensions and one algorithm for the case that they are in 3 dimensions. The 2 dimensional algorithms run in O(N-4) and O(N-3 log N) time respectively where N is the total number of vertices in both the polygons while the 3 dimensional algorithm runs in O(N-4) time.

引用

页码：211 / 223

页数：13