Overlapping polygons on 2D plane

views:

answers:

+1 Q:

Overlapping polygons on 2D plane

i would like to build a dynamic data structure that can hold a list of polygons and return a list of polygons that overlaps a specified rectangle.

i looked into bst trees (and quad trees) but these dont seem to work too well when the polygons overlap heavily.

any good ideas i should check out before i roll my own nonsense?

edit

lets assume all the polygons are normal non rotated rectangles. im willing to take the hit (point in polygon test) during point tests (i might be doing it anyway), and during a region test getting their bounding boxes is just as good. only a small percentage of them will actually not overlap the region in question.

+2 A:

I would look at 2-d segment delaunay graphs. Look also at Nef polygons. CGAL has a lot of set operations on polygons. Answers to this question may also be of value

Edit If your polygons are non rotated rectangles see R-Trees

deinst 2010-08-10 11:52:24

that is a little more intense than i was looking for. it is also written in some academia dialect that i have trouble understanding. im gonna edit the question, hopefully more people will bite.

aepurniet 2010-08-10 12:00:21

I have updated it. CGAL has more general polygon handling routines. You are probably better off using pre-programmed routines because in geometry the corner cases will kill you.

deinst 2010-08-10 12:05:42

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Point_set_2/Chapter_main.html seemed more on point with what i need to do, but it only operates on point sets, could not find anything that operates on rectangles or polygons. that library is definitely a really cool reference though.

aepurniet 2010-08-10 12:25:37

You'll need to write some code to interface. The segment graphs give you a bunch of cells, and each cell does not cross any polygon boundary, and it is easy to enumerate the cells in a given rectangle. You would need to map from the cells to the polygons as you are building. Look also at the general polygon operations that I referenced.

deinst 2010-08-10 12:44:22

i thought the cells are built up from a point set, and cannot be created themselves?

aepurniet 2010-08-10 14:47:04

Why do you write that yourself? Java offers complex intersection tests. You can convert your polygon data structures and your rectangle to Java.awt.geom.Area and then call the Area.intersect() method which does all the math for you.

It also takes care of all the rarely occurring (but still important) special cases which are really nasty to catch.

2010-08-10 12:11:27

well you are suggesting an O(n) algorithm, which is a solution, but definitely not the best one; or a very good one, if, lets say, this needs to be done 60 times a second for 10k polygons. i dont want to write the intersection tests myself, just need to figure out what data structure to store the polys in in order to do my tests efficiently

aepurniet 2010-08-10 12:41:12

i just wrote a regular quadtree, that allowed each leaf node to hold unlimited polys, if the intersection of the bounds of the leaf and the bounds of each poly in the bucket were equivalent. otherwise leaf nodes are limited to 8 polys, before splitting.

aepurniet 2010-08-27 16:41:53

ansaurus

tags:

views:

answers:

Overlapping polygons on 2D plane

related questions