Finding intersections between line and polygon in 2D/3D

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

Finding intersections between line and polygon in 2D/3D


I'm trying to use the CGAL python-bindings to write a program (in Python) to find intersections between 1 object (which could be a line segment(s) or a polygon/polyhedron) and another polygon/polyhedron. While I am currently working in 2D, I would like to extend the program to 3D as well. I have asked this question here as well:

I've installed the python-bindings for CGAL already. I understand it is still under development, but it seems it can already do a lot of things. I have managed to get it to output intersections between a line segment and a tetrahedron (using the AABB tree algorithms), and intersecting sequences of dD iso-oriented boxes. However, the AABB tree algorithms seem to only work with 3D objects. I guess I can represent my general shape as a pseudo-3D object, but then I ran into the problem of actually constructing the 3D object. The examples given in the python-bindings only work for tetrahedrons, and I cannot figure out how to create a general polyhedron. So my problem has become two-fold:

  1. How do I define a general polyhedron using the CGAL python-bindings?
  2. How do I use the defined polyhedron to calculate intersections and distances from other general shapes like line segments and polygons?

So for a tetrahedron, the package does (from :

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)

This creates a tetrahedron, which can support queries on intersection, squared distance etc. However, this does not work for more than 4 points. In my case, the polygon/polyhedron would be defined by around 50 points. How do I create such an object using CGAL-python?