Thursday, March 14, 2013
How to Jam an Arrangement_2 into a General_polygon_set_2
昨天我花了近3个小时追踪一个怪异的CGAL的bug——我写那个程序是为了从arrangement中构建出多边形的集合，然后导出这些多边形，而奇怪的多边形
To my annoyance, I discovered today as I went to write the bug up that I knew about this bug...over three
years ago. :-( I get annoyed when I search for the answer to an obscure OpenGL problem and find my own post (e.g. I'm not going to find anything I didn't already know), but it's even more annoying to waste hours on the bug and then have that happen.
让我气愤只是的是，我今天去记录这个问题是发现我事实上在三年前就遇到过了。:-(当我搜索明显的OpengGL问题然后发现了自己的博文（我不会找到不论什么我不知道的）。可是更令人火大的是我居然花了数小时调代码并产生这个错误。
Basically if you are going to build a general polygon set by providing a pre-built arrangement, there are two things you must do:
- Remove redundant edges - the GPS code assumes that the arrangement doesn't have needless edges (which will screw up traversal). Fortunately, the GPS code has a utility to do this, which I just call.
- Then you have to ensure that the direction of the underlying curves along the various edges are consistent - that is, for a given counter-clockwise boundary, every underlying curve goes either with or against the edge.
(After redundant edge removal, the arrangement will contain no antennas, so it will always be possible to get consistency on both sides of a CCB.)
基本上，假设你要从一个预先构建的arrangement中拿出通用多边形集合。有两件事必须做：
With this, polygon set operations work on arbitrary map input.
Why Did You Try This?
It also requires your arrangement to have the containment flag on the face data mixed in. Why go to the trouble? I did this for two reasons:
- Sometimes the polygonal set data I want to process came from an arrangement, and that arrangement is fairly huge. Having to construct the arrangement out of polygons the normal way requires geometry tests - topology data would be lost and rediscovered.
For big maps this is really performance-painful. - I have some operations that work on arrangements that are precursors to boolean sets. For example, the airport surface area data are fundamentally polygon sets (e.g. in the set is the airport surface area) but some of the constructive processing (e.g. simplifying
the contour) run on arrangements.
When an arrangement is turned into a polygon set, one of the results is a rather drastic map cleaning. Since the polygon set cares only about containment (what points are in, what are out), random features like roads tend to get blown away.
PM