I think Dave Eberly has a useful doc on 2D polygon booleans over at his sight, Magic Software.

Also, do a search on the keyphrase "polygon map overlay." That may result in some other useful docs.

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.