在二维/三维中求线段与一般多边形的交点

Question

我试图使用CGAL Python绑定来编写一个程序(用Python)来查找一个对象(它可以是线段或多边形/多面体)和另一个多边形/多面体之间的交叉。虽然我目前在2D工作，我想把程序扩展到3D。

我已经为CGAL安装了python绑定。我知道它还在开发中，但是它似乎已经可以做很多事情了。我已经设法让它输出线段和四面体之间的交点(使用AABB树算法)，以及dD面向异构的盒的交叉序列。然而，AABB树算法似乎只适用于3D对象。我想我可以用一个伪三维物体来表示我的一般形状，但是后来我遇到了实际构造三维物体的问题。python绑定中给出的例子只适用于四面体，我不知道如何创建一个通用的多面体。所以我的问题变成了两方面：

1. 如何使用CGAL python绑定定义通用多面体？
2. 如何使用已定义的多面体计算与其他一般形状(如线段和多边形)的交点和距离？

因此，对于四面体，包是这样做的(来自example.py)：

from CGAL.CGAL_Kernel import Point_3
from CGAL.CGAL_Polyhedron_3 import Polyhedron_3

p=Point_3(1.0, 0.0, 0.0)
q=Point_3(0.0, 1.0, 0.0)
r=Point_3(0.0, 0.0, 1.0)
s=Point_3(0.0, 0.0, 0.0)
polyhedron = Polyhedron_3()
polyhedron.make_tetrahedron(p, q, r, s)

#constructs AABB tree
tree = AABB_tree_Polyhedron_3_Facet_handle(polyhedron.facets())

#constructs segment query
a = Point_3(-0.2, 0.2, -0.2)
b = Point_3(1.3, 0.2, 1.3)
segment_query=Segment_3(a,b)

这就创建了一个四面体，它可以支持对交集、平方距离等的查询。然而，这并不适用于超过4个点。在我的例子中，多边形/多面体的定义大约是50点。如何使用创建这样的对象？

Answer 1

如果你不关心程序的效率。您可以通过以下方式试用我最新的python包Geometry3D

pip install Geometry3D

由于它是用纯Python编写的，它有点慢，不适合像图形这样的工作。但它在一般情况下运行良好，并且支持许多几何形状。

下面是一个例子

>>> from Geometry3D import *
>>>
>>> a = Point(1,1,1)
>>> b = Point(-1,1,1)
>>> c = Point(-1,-1,1)
>>> d = Point(1,-1,1)
>>> e = Point(1,1,-1)
>>> f = Point(-1,1,-1)
>>> g = Point(-1,-1,-1)
>>> h = Point(1,-1,-1)
>>> cph0 = Parallelepiped(Point(-1,-1,-1),Vector(2,0,0),Vector(0,2,0),Vector(0,0,2))
>>> cpg12 = ConvexPolygon((e,c,h))
>>> cpg13 = ConvexPolygon((e,f,c))
>>> cpg14 = ConvexPolygon((c,f,g))
>>> cpg15 = ConvexPolygon((h,c,g))
>>> cpg16 = ConvexPolygon((h,g,f,e))
>>> cph1 = ConvexPolyhedron((cpg12,cpg13,cpg14,cpg15,cpg16))
>>> a1 = Point(1.5,1.5,1.5)
>>> b1 = Point(-0.5,1.5,1.5)
>>> c1 = Point(-0.5,-0.5,1.5)
>>> d1 = Point(1.5,-0.5,1.5)
>>> e1 = Point(1.5,1.5,-0.5)
>>> f1 = Point(-0.2,1.5,-0.5)
>>> g1 = Point(-0.2,-0.5,-0.5)
>>> h1 = Point(1.5,-0.5,-0.5)
>>>
>>> cpg6 = ConvexPolygon((a1,d1,h1,e1))
>>> cpg7 = ConvexPolygon((a1,e1,f1,b1))
>>> cpg8 = ConvexPolygon((c1,b1,f1,g1))
>>> cpg9 = ConvexPolygon((c1,g1,h1,d1))
>>> cpg10 = ConvexPolygon((a1,b1,c1,d1))
>>> cpg11 = ConvexPolygon((e1,h1,g1,f1))
>>> cph2 = ConvexPolyhedron((cpg6,cpg7,cpg8,cpg9,cpg10,cpg11))
>>> cph3 = intersection(cph0,cph2)
>>>
>>> cph4 = intersection(cph1,cph2)
>>> r = Renderer()
>>> r.add((cph0,'r',1),normal_length = 0)
>>> r.add((cph1,'r',1),normal_length = 0)
>>> r.add((cph2,'g',1),normal_length = 0)
>>> r.add((cph3,'b',3),normal_length = 0.5)
>>> r.add((cph4,'y',3),normal_length = 0.5)
>>> r.show()

结果

您还可以查看文档Geomrtry3D