Geometry Boost List: [ggl] Re: Finding intersection points of a ray and polygon?

Subject: [ggl] Re: Finding intersection points of a ray and polygon?
From: Elvis Stansvik (elvstone)
Date: 2010-02-23 12:47:58

Hi Barend,

2010/2/23 Barend Gehrels <Barend.Gehrels_at_[hidden]>:
> 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.

Yes, I realized this after doing some research. It's however, given
the simple nature of my project, not a catastrophy as it would be OK
with me to work with "rays" of finite length. That is, line strings.

>
> 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.

Alright. As I'm pretty short on time and new to Boost and generic
programming in general (coming from a background of mostly Qt
programming, which is not so template intensive), I'm not sure
contributing this function to Boost.Geometry is something that I'll
have time to contribute, at least not within the constraints of my
project. Or did you mean it would be an easy addition for you
developers?

>
> 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.

Right. I could work with a linestring with just two points as my
"ray". No problem.

>
> 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.
>
>
>> Thanks!
>
> 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).

Okay. Until now I've just experimented some with a checkout of 0.6.0.
I guess I should get on trunk because grepping the sources i could not
find get_turn_points(), only self_get_turn_points(). I'll download the
trunk version.

But what does it mean that it's in "coded" form? Is this information
available to me right now (except that get_turn_points() would need to
be extended to do line-polygon intersection). And what information
will this give me if Boost.Geometry have no concept of rays? What is
the "direction" of a line (segment)?

>
> 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.

Yes I've come to realize that the library is in a bit of a flux. What
I really miss though is documentation of all the member functions of
the library. Very few of them are documented, sometimes not even their
arguments, which makes it a bit hard for a newcomer like me to get up
to speed with the library quickly.

When will the incorporation into Boost take place? Will there be any
added documentation when that happens?

Anyway, thanks a lot for your thorough answer.

Elvis

>
> Regards, Barend
>
>
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl
>
>