Boost logo

Geometry :

Subject: [ggl] Re: Finding intersection points of a ray and polygon?
From: Barend Gehrels (Barend.Gehrels)
Date: 2010-02-23 12:08:27

Hi Elvis,

Thanks for your interest in Boost.Geometry

>> For a very small high-school project I'm making a simple Qt
>> application that should let my teacher illustrate the Law of
>> refraction [1] to his students.
>> The idea is to let the user of the application place a set of simple
>> bodies (polygons) with optical properties into a scene and then let a
>> ray of light pass through them. With ray I mean a line which is finite
>> in one direction but infinite in the other.
>> This requires me to find the ray's first intersection point with a
>> polygon. As I don't have quite a lot of math under my belt, and the
>> project is very small and done under time constraints I started
>> looking for a computational geometry library and found Boost.Geometry
>> which seems to fit the bill.

Boost.Geometry does not (yet) have the ray Concept, or ray classes. So
out of the box it will not work.

>> Now my question is; can Boost.Geometry help me find the first
>> intersection point of a ray and a polygon, and after that also give me
>> access to the polygon edge that was hit? (I will need the angle of the
>> edge to do the refraction calculation).
There is a method get_turn_points (as it is now called), which is more
or less meant internally (it might be moved to namespace detail), which
will find all intersections between two polygons, including the edge
that was hit. However, between a segment and a polygon (the closest you
probably get now) it is not yet implemented. But that addition is easy.

>> I'm very open to to ways in which I can simplify my project, as I only
>> have a few weeks. Just using simple convex polygons for the optical
>> bodies would be OK, and also using a line segment of finite length
>> instead of a ray.
So yes, that might be an option.

>> Any pointers and tips to examples besides the one on the User Wiki and
>> reference documentation are much appriciated. My C++ proficiency is
>> OKish and my template programming knowledge definitely rusty ;)
>> Finally, congrats to getting GGL into Boost proper.

> I realized after sending my mail that I have an additional question:
> For my application I would need to know if (at the intersection point)
> the ray is passing into or out of the polygon. Can Boost.Geometry give
> me this information?
Yes, the turn information has this information in coded form. However,
until now it is only used internally, so it is subject to change - not
exactly figured out how it would look like for end users. But it is
probably the best you can get (with Boost.Geometry).

If segments are OK for you, and you realize the state the library is in
now (we're preparing it for incorporation, namespaces will change, etc),
I will come back soon about this.

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at