两个凸多边形的交集 [英] Intersection of two convex polygons
本文介绍了两个凸多边形的交集的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有两个凸多边形.多边形被实现为其顶点的循环列表.如何找到这两个多边形的交点?
I have two convex polygons. Polygons are implemented as cyclic lists of their vertices. How to find an intersection of this two polygons?
推荐答案
For each edge V1-V2 in the first polygon,
Let H := Half-plane tangenting V1-V2, with the remaining
vertices on the "inside".
Let C := New empty polygon.
For each edge V3-V4 in the second polygon,
Let X := The intersection between V3-V4 and H.
If V3 inside H, and V4 is outside H then,
Add V3 to C.
Add X to C.
Else if both V3 and V4 lies outside H then,
Skip.
Else if V3 outside H, and V4 is inside H then,
Add X to C.
Else
Add V3 to C.
Replace the second polygon with C.
这对于简单的使用应该足够了;10-20 个顶点,而不是每帧都重新计算.—O(n2)
This should suffice for simple usage; 10-20 vertices and not recalculating every frame. — O(n2)
这里有几个链接:
- Computer Graphics I – Polygon Clipping and Filling (pdf)
- rosettacode.org – Sutherland-Hodgman polygon clipping
这篇关于两个凸多边形的交集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文