Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Point inside Arrangment

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Point inside Arrangment


Chronological Thread 
  • From: Ben Supnik <>
  • To:
  • Cc: Winnie Hellmann <>
  • Subject: Re: [cgal-discuss] Point inside Arrangment
  • Date: Wed, 05 Oct 2011 13:23:52 -0400

Hi Winnie,

My understanding of arrangement_2 is that it does what you need:

I thought about vertical ray shooting, but since it does not return the
feature a query point is located nor all edges/vertices above or below,
I can't count the intersected CCBs that way. I can't make multiple ray
shoots either since the total query should be of linear complexity.

But you can figure out what face you are in (or what edge/vertex you are on) from this or from arr_walk_along_a_line_point_location - each should run in linear time, more or less.

So are you saying that you have the contours of the polygon in an arrangement but you do not have any of the containment information?

If you have not saved containment information, I think that (for well formed general polygons you can figure out if the face you fall in is a 'hole' by comparing the twin of each edge on its outer CCB to the unbounded face. This means you'll be double-linear time - once for the location, and again for the resolution of whether you're in a hole or not.

You could in theory do slightly better by writing your own walk on top of the zone visitor, which is a visitor that traverses individual faces. You could then count windings as you walk from along a line to your query point.

There are a bunch of ways to get more speed...you can tag your faces as holes or not in linear time and then retain that on the arrangement, and batched queries will beat individual ones if that is useful.

cheers
ben



--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://www.x-plane.com/blog/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list:

Developer mailing list:




Archive powered by MHonArc 2.6.16.

Top of Page