Sign in to follow this  

2D Polygon Boolean Operation.

This topic is 4837 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm working on a game and my game editor requires 2D polygon boolean("OR") operation to union all the polygons of my game map together. I've hunt around for libraries but to no avail(GPC does not suit my game as the licence is murky). So I decided to do my own. However, upon reading a documentation on how to do polygon operation(http://www.xs4all.nl/~kholwerd/algdoc/top.html ), I got stuck. I just can't grasp the idea of scanbeams. Another problem that I face is that my polygon system have to beable to retain uniqe data for each line segment. This is because each line segment, which is basically a wall, have their own properties. If someone can help explain what the hell scanbeams are and why or how it is used in a polygon boolean operation, it'll help alot. Thanks in advance.

Share this post


Link to post
Share on other sites
Quote:
Original post by Lf3T-Hn4D
If someone can help explain what the hell scanbeams are and why or how it is used in a polygon boolean operation, it'll help alot.

Thanks in advance.


I won't explain that in details. First since it's edit time not real time. Try to find a solid lib, learn how to handle the interface and don't dig too much the abyssal arcanes of pure algorithmic geometry (based on graphs, and vectorial shapes). It's very complex to get accustommed to such algos, specially in practice with a lot of odd cases to handle.

Intersecting two 2D convex polyhedra is straightforward. It's even quite easy to find optimal algos. This starts by following the edges from top clock wise on the 'left' polygon and from top ccw on the right polygon this is done in parallel on both sides. Try to imagine what this parallelism means.

Tip : y coords are very important to keep the walk on both sides 'synchronized'. Step down carefully until you find the first and then the second intersection. It's also called an 'event' if you see y as time. Try to figure out deeply the equivalence between timing and walking on one axis. The words chosen are quite expressive.

Once you've got it you'll maybe understand the justification of the scan beams in more complex cases.

Scan beams are used in many algos that require to find interestions of edges efficiently.

If you have n-edges complexity is squared. For instance 100 edges require 99*50 tests (the handshakes enumeration problem).

Scan beams are in fact a space partition of the problem on one axis. It reduces computationnal complexity a lot. Once the vertices are ordered in X, the beams are defined. then you just have to parse the beams, testing if edges collide when beams collide.

You can see the beams as the projections of the edges on axis X. If the segments intersect in 2D their 1D projections also intersect. this helps reducing the complexity a lot, you test far less combinations of edges.

Projections :

A---------B E---------F
C----------D


You see that you'll never have to test AB against EF thanks to the X-sort made as the first pass of the algo.


Quote:

retain uniqe data for each line segment

This probably means you'll have to find some open source software and touch the code for your own needs even if you do not understand the algo very well. I doub a black box interface could let you add custom data and all you need specifically.

Share this post


Link to post
Share on other sites
Thanks for that explaination. Funny that I didn't see it from that approach. However, looking at it, I guess I'm better off getting an opensource implementation and start hacking away. But one is hard to find :/

Ah well, I guess inkscape's livarot have to do...

Share this post


Link to post
Share on other sites

This topic is 4837 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this