CGAL users discussion list

[Efi Fogel <>]

Hi Chris,

Yes, you probably could use CGAL, and probably in more ways than you can think of.

CGAL, as you may already know, is huge, but it seems that for your needs the packages below provide most of your needs:

• 2D Arrangements,
• 2D Regularized Boolean Operations, and
• 2D Minkowski Sum

There is also a book, entitled "CGAL Arrangements and Their Applications", that explains, among other things, how are these packages applied to perform various tasks. As a matter of fact there is an example in Chapter 8 "Operations on (Curved) Polygons" that demonstrates how to unify PCB components. It seems though that Chapter 9 "Minkowksi Sums and Offset Polygons" has more value for you, as it has some motion-planning examples. More information about the book can be found here.

Best,

Efi

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Sun, Mar 20, 2016 at 11:45 AM, Ch'Gans <> wrote:

Hi there,

I am investigating if I could use CGAL to drive interactive routing of
PCBs (Printed Circuit Board). The problem is quite simple, you have to
create electrical connections using copper deposit on a 2D surface.
Interactive routing is different from automatic routing, with
interactive routing the software assists the user by providing ad-hoc
obstacle avoidance while letting him/her decides on the overall
strategy.

Basically, the user have to create a route from point A to point B,
while respecting some design rules (no short-circuit/overlap, minimum
clearance, stay within the board boundary, etc...). Typical algorithms
used in this case are called "Push", "Shove", "Hug", "Walk around",
... The CERN has recently added this feature to KiCad, an open source
ECAD/EDA (Electronics Computer Aided Design, Electronic Design
Automation). For a short demo, please have a look at
https://www.youtube.com/watch?v=zxHDAHpR5Ls

To explain quickly what I'm trying to do I have attached a few
pictures (made with QCAD. an open source 2D mechanical drawing
application):
- 01-path.png: My 2 intersecting path (This is a design violation situation)
- 02-tracks.png: The physical objects (copper deposit) are actually
the path stroked with a given witdh (10 for the 1st one, 6.2 for the
second one)
- 03-clearance.png: Design enforces a given clearance between 2 tracks
(4.0 in this case), this is equivalent to stroking the path with
width+clearance
- 04-collision.png: The collision boundary represents the path around
a track that if stroked with the width of the other track will avoid
collision between the 2 tracks. Again this is obtained by stroking the
path with thisWidth + clearance +otherWidth
- 05-escape.png: The escape points are the intersection of a track's
path with the collision boundary of the other track, By walking the
escape point along the collision boundary, the 2 tracks don't violate
anymore the design rules.
- 06-result.png: My new path/tracks after applying the "walk around"
collision avoidance technique
- next steps: After this, you have to run more algorithm to optimise
the resulting track (cleanup by removing sharp turn, make the track
shorter by simplifying the path, ...) but I'm getting off-topic here.

OK, so to do all of this, I need a system that allow me to manage
non-closed path made of line and arc segments in a 2D space and that
provides:
- path stroking (Seems to be doable with offset_polygon_2 )
- calculate intersections points of the stroke shapes (The stroke
shape is actually a closed path. Haven't understood yet which package
should I use)
- calculate the avoidance path based on intersection and collision
boundary path.

I want to do all of these using the Qt5 C++ toolkit, I have
implemented some proof of concepts using their the QGraphicsView
framework (I use a dedicated QGraphicsScene to manage the item
spatial-indexing, and another QGraphicsScene/QgraphicsView pair for
visualisation purpose). I managed to do part of what I have described
here by relying solely on QPainterPath and QPainterPathStroker. But as
their name state, these 2 classes are specialised for drawing and I
definitely need a geometry specialised library to address my needs,
hence CGAL.

I've just discovered CGAL (maybe 4/6 hours ago), so please bear with
me, I haven't read all the documentation yet (very comprehensive
documentation btw!)

For now, as a proof of concept, I would like to solve the problem
described in my drawing using CGAL, but I'm having problems to get
started.
Do you think that CGAL is really a good fit for what I'm trying to achieve?
Could anyone kindly provide links and/or point-out, especially which
package/class to use to create my path, my strokes and handle all the
geometry calculation?

/me back to CGAL documentation and examples.

Thanks,
Chris

PS: The reason I'm looking for a proper geometry toolkit is that this
track/path collision avoidance algorithm is just the tip of the
iceberg, if I'm happy with CGAL, the next steps are:
- manage keep-in and keep-out zones (defined as segment/arc polygon
and that needs offset/inset)
- manage filled polygon: like a track but use a 2D closed contour
instead of an "open" path
- manage poured polygon: like a filled polygon that magically changes
its shape so that any path crossing it doesn't intersect with it
anymore (this is done by removing the intersected track/polygon shape
from the polygon itself)
- and more ...

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss