add a function that generate filled gerberdata with representing internal shape by fliping polarity

3 files changed, 406 insertions, 10 deletions

diff --git a/gerberex/dxf.py b/gerberex/dxf.py
index 00b7695..95a3114 100644
--- a/gerberex/dxf.py
+++ b/gerberex/dxf.py
@@ -12,12 +12,88 @@ from gerber.gerber_statements import ADParamStmt
 from gerber.excellon_statements import ExcellonTool
 from gerber.excellon_statements import CoordinateStmt
 from gerberex.utility import is_equal_point, is_equal_value
-from gerberex.dxf_path import generate_paths
+from gerberex.dxf_path import generate_paths, judge_containment
 from gerberex.excellon import write_excellon_header
 from gerberex.rs274x import write_gerber_header
 
 ACCEPTABLE_ERROR = 0.001
 
+def _normalize_angle(start_angle, end_angle):
+    angle = end_angle - start_angle
+    if angle > 0:
+        start = start_angle % 360
+    else:
+        angle = -angle
+        start = end_angle % 360
+    angle = min(angle, 360)
+    start = start - 360 if  start > 180 else start
+
+    regions = []
+    while angle > 0:
+        end = start + angle
+        if  end <= 180:
+            regions.append((start * pi / 180, end * pi / 180))
+            angle = 0
+        else:
+            regions.append((start * pi / 180, pi))
+            angle = end - 180
+            start = -180
+    return regions
+
+def _intersections_of_line_and_circle(start, end, center, radius, error_range):
+    x1 = start[0] - center[0]
+    y1 = start[1] - center[1]
+    x2 = end[0] - center[0]
+    y2 = end[1] - center[1]
+
+    dx = x2 - x1
+    dy = y2 - y1
+    dr = sqrt(dx * dx + dy * dy)
+    D = x1 * y2 - x2 * y1
+
+    D2 = D * D
+    dr2 = dr * dr
+    r2 = radius * radius
+    delta = r2 * dr2 - D2
+    e4 = error_range * error_range * error_range * error_range * 10
+    if delta > - e4 and delta < e4:
+        delta = 0
+    if delta < 0:
+        return None
+
+    sqrt_D = sqrt(delta)
+    E_x = -dx * sqrt_D if dy < 0 else dx * sqrt_D
+    E_y = abs(dy) * sqrt_D
+
+    p1_x = (D * dy + E_x) / dr2
+    p2_x = (D * dy - E_x) / dr2
+    p1_y = (-D * dx + E_y) / dr2
+    p2_y = (-D * dx - E_y) / dr2
+
+    p1_angle = atan2(p1_y, p1_x)
+    p2_angle = atan2(p2_y, p2_x)
+    if dx == 0: 
+        p1_t = (p1_y - y1) / dy
+        p2_t = (p2_y - y1) / dy
+    else:
+        p1_t = (p1_x - x1) / dx
+        p2_t = (p2_x - x1) / dx
+
+    if delta == 0:
+        return (
+            (p1_x + center[0], p1_y + center[1]),
+            None,
+            p1_angle, None,
+            p1_t, None
+        )
+    else:
+        return (
+            (p1_x + center[0], p1_y + center[1]),
+            (p2_x + center[0], p2_y + center[1]),
+            p1_angle, p2_angle,
+            p1_t, p2_t
+        )
+
 class DxfStatement(object):
     def __init__(self, entity):
         self.entity = entity
@@ -51,6 +127,13 @@ class DxfLineStatement(DxfStatement):
         end = (entity.end[0], entity.end[1])
         return cls(entity, start, end)
 
+    @property
+    def bounding_box(self):
+        return (min(self.start[0], self.end[0]),
+                min(self.start[1], self.end[1]),
+                max(self.start[0], self.end[0]),
+                max(self.start[1], self.end[1]))
+
     def __init__(self, entity, start, end):
         super(DxfLineStatement, self).__init__(entity)
         self.start = start
@@ -110,6 +193,53 @@ class DxfLineStatement(DxfStatement):
     def rotate(self, angle, center=(0, 0)):
         self.start = rotate_point(self.start, angle, center)
         self.end = rotate_point(self.end, angle, center)
+    
+    def intersections_with_halfline(self, point_from, point_to, error_range):
+        denominator = (self.end[0] - self.start[0]) * (point_to[1] - point_from[1]) - \
+                      (self.end[1] - self.start[1]) * (point_to[0] - point_from[0])
+        de = error_range * error_range
+        if denominator > -de and denominator < de:
+            return []
+        from_dx = point_from[0] - self.start[0]
+        from_dy = point_from[1] - self.start[1]
+        r = ((point_to[1] - point_from[1]) * from_dx - 
+             (point_to[0] - point_from[0]) * from_dy) / denominator
+        s = ((self.end[1] - self.start[1]) * from_dx -
+             (self.end[0] - self.start[0]) * from_dy) / denominator
+        dx = (self.end[0] - self.start[0])
+        dy = (self.end[1] - self.start[1])
+        le = error_range / sqrt(dx * dx + dy * dy)
+        if s < 0 or r < -le or r > 1 + le:
+            return []
+        
+        pt = (self.start[0] + (self.end[0] - self.start[0]) * r,
+              self.start[1] + (self.end[1] - self.start[1]) * r)
+        if is_equal_point(pt, self.start, error_range):
+            return []
+        else:
+            return [pt]
+
+    def intersections_with_arc(self, center, radius, angle_regions, error_range):
+        intersection = \
+            _intersections_of_line_and_circle(self.start, self.end, center, radius, error_range)
+        if intersection is None:
+            return []
+        else:
+            p1, p2, p1_angle, p2_angle, p1_t, p2_t = intersection
+
+        pts = []
+        if p1_t >= 0 and p1_t <= 1:
+            for region in angle_regions:
+                if p1_angle >= region[0] and p1_angle <= region[1]:
+                    pts.append(p1)
+                    break
+        if p2 is not None and p2_t >= 0 and p2_t <= 1:
+            for region in angle_regions:
+                if p2_angle >= region[0] and p2_angle <= region[1]:
+                    pts.append(p2)
+                    break
+
+        return pts
 
 class DxfArcStatement(DxfStatement):
     def __init__(self, entity):
@@ -139,6 +269,12 @@ class DxfArcStatement(DxfStatement):
             self.is_closed = angle >= 360 or angle <= -360
         else:
             raise Exception('invalid DXF type was specified')
+        self.angle_regions = _normalize_angle(self.start_angle, self.end_angle)
+
+    @property
+    def bounding_box(self):
+        return (self.center[0] - self.radius, self.center[1] - self.radius,
+                self.center[0] + self.radius, self.center[1] + self.radius)
 
     def to_inch(self):
         self.radius = inch(self.radius)
@@ -204,6 +340,82 @@ class DxfArcStatement(DxfStatement):
         self.center = rotate_point(self.center, angle, center)
         self.start = rotate_point(self.start, angle, center)
         self.end = rotate_point(self.end, angle, center)
+        self.angle_regions = _normalize_angle(self.start_angle, self.end_angle)
+
+    def intersections_with_halfline(self, point_from, point_to, error_range):
+        intersection = \
+            _intersections_of_line_and_circle(
+                point_from, point_to, self.center, self.radius, error_range)
+        if intersection is None:
+            return []
+        else:
+            p1, p2, p1_angle, p2_angle, p1_t, p2_t = intersection
+        
+        if is_equal_point(p1, self.start, error_range):
+            p1 = None
+        elif p2 is not None and is_equal_point(p2, self.start, error_range):
+            p2 = None
+
+        aerror = error_range * self.radius
+        pts = []
+        if p1 is not None and p1_t >= 0 and not is_equal_point(p1, self.start, error_range):
+            for region in self.angle_regions:
+                if p1_angle >= region[0] - aerror and p1_angle <= region[1] + aerror:
+                    pts.append(p1)
+                    break
+        if p2 is not None and p2_t >= 0 and not is_equal_point(p2, self.start, error_range):
+            for region in self.angle_regions:
+                if p2_angle >= region[0] - aerror and p2_angle <= region[1] + aerror:
+                    pts.append(p2)
+                    break
+
+        return pts
+
+    def intersections_with_arc(self, center, radius, angle_regions, error_range):
+        x1 = center[0] - self.center[0]
+        y1 = center[1] - self.center[1]
+        r1 = self.radius
+        r2 = radius
+        cd_sq = x1 * x1 + y1 * y1
+        cd = sqrt(cd_sq)
+        rd = abs(r1 - r2)
+
+        if (cd >= 0 and cd <= rd) or cd >= r1 + r2:
+            return []
+        
+        A = (cd_sq + r1 * r1 - r2 * r2) / 2
+        scale = sqrt(cd_sq * r1 * r1 - A * A) / cd_sq
+        xl = A * x1 / cd_sq
+        xr = y1 * scale
+        yl = A * y1 / cd_sq
+        yr = x1 * scale
+
+        pt1_x = xl + xr
+        pt1_y = yl - yr
+        pt2_x = xl - xr
+        pt2_y = yl + yr
+        pt1_angle1 = atan2(pt1_y, pt1_x)
+        pt1_angle2 = atan2(pt1_y - y1, pt1_x - x1)
+        pt2_angle1 = atan2(pt2_y, pt2_x)
+        pt2_angle2 = atan2(pt2_y - y1, pt2_x - x1)
+
+        aerror = error_range * self.radius
+        pts=[]
+        for region in self.angle_regions:
+            if pt1_angle1 >= region[0] and pt1_angle1 <= region[1]:
+                for region in angle_regions:
+                    if pt1_angle2 >= region[0] - aerror and pt1_angle2 <= region[1] + aerror:
+                        pts.append((pt1_x + self.center[0], pt1_y + self.center[1]))
+                        break
+                break
+        for region in self.angle_regions:
+            if pt2_angle1 >= region[0] and pt2_angle1 <= region[1]:
+                for region in angle_regions:
+                    if pt2_angle2 >= region[0] - aerror and pt2_angle2 <= region[1] + aerror:
+                        pts.append((pt2_x + self.center[0], pt2_y + self.center[1]))
+                        break
+                break
+        return pts
 
 class DxfPolylineStatement(DxfStatement):
     def __init__(self, entity):
@@ -293,31 +505,69 @@ class DxfPolylineStatement(DxfStatement):
             self.entity.points[idx] = rotate_point(self.entity.points[idx], angle, center)
 
 class DxfStatements(object):
-    def __init__(self, statements, units, dcode=10, draw_mode=None):
-        if draw_mode == None:
+    def __init__(self, statements, units, dcode=10, draw_mode=None, fill_mode=None):
+        if draw_mode is None:
             draw_mode = DxfFile.DM_LINE
+        if fill_mode is None:
+            fill_mode = DxfFile.FM_TURN_OVER
         self._units = units
         self.dcode = dcode
         self.draw_mode = draw_mode
+        self.fill_mode = fill_mode
         self.pitch = inch(1) if self._units == 'inch' else 1
         self.width = 0
         self.error_range = inch(ACCEPTABLE_ERROR) if self._units == 'inch' else ACCEPTABLE_ERROR
-        self.statements = statements
+        self.statements = list(filter(
+            lambda i: not (isinstance(i, DxfLineStatement) and \
+                          is_equal_point(i.start, i.end, self.error_range)),
+            statements
+        ))
         self.close_paths, self.open_paths = generate_paths(self.statements, self.error_range)
+        self.sorted_close_paths = []
+        self.polarity = True # True means dark, False means clear
 
     @property
     def units(self):
         return _units
 
+    def _polarity_command(self, polarity=None):
+        if polarity is None:
+            polarity = self.polarity
+        return '%LPD*%' if polarity else '%LPC*%'
+
+    def _prepare_sorted_close_paths(self):
+        if self.sorted_close_paths:
+            return
+        for i in range(0, len(self.close_paths)):
+            for j in range(i + 1, len(self.close_paths)):
+                containee, container = judge_containment(
+                    self.close_paths[i], self.close_paths[j], self.error_range)
+                if containee is not None:
+                    containee.containers.append(container)
+        self.sorted_close_paths = sorted(self.close_paths, key=lambda path: len(path.containers))
+
     def to_gerber(self, settings=FileSettings()):
         def gerbers():
             yield 'G75*'
-            yield '%LPD*%'
+            yield self._polarity_command()
             yield 'D{0}*'.format(self.dcode)
             if self.draw_mode == DxfFile.DM_FILL:
                 yield 'G36*'
-                for path in self.close_paths:
-                    yield path.to_gerber(settings)
+                if self.fill_mode == DxfFile.FM_TURN_OVER:
+                    self._prepare_sorted_close_paths()
+                    polarity = self.polarity
+                    level = 0
+                    for path in self.sorted_close_paths:
+                        if len(path.containers) > level:
+                            level = len(path.containers)
+                            polarity = not polarity
+                            yield 'G37*'
+                            yield self._polarity_command(polarity)
+                            yield 'G36*'
+                        yield path.to_gerber(settings)
+                else:
+                    for path in self.close_paths:
+                        yield path.to_gerber(settings)
                 yield 'G37*'
             else:
                 pitch = self.pitch if self.draw_mode == DxfFile.DM_MOUSE_BITES else 0
@@ -378,6 +628,9 @@ class DxfFile(CamFile):
     DM_FILL = 1
     DM_MOUSE_BITES = 2
 
+    FM_SIMPLE = 0
+    FM_TURN_OVER = 1
+
     FT_RX274X = 0
     FT_EXCELLON = 1
 
@@ -430,6 +683,7 @@ class DxfFile(CamFile):
 
         super(DxfFile, self).__init__(settings=settings, filename=filename)
         self._draw_mode = draw_mode
+        self._fill_mode = self.FM_TURN_OVER
         
         self.aperture = ADParamStmt.circle(dcode=10, diameter=0.0)
         if settings.units == 'inch':
@@ -437,7 +691,7 @@ class DxfFile(CamFile):
         else:
             self.aperture.to_metric()
         self.statements = DxfStatements(
-            statements, self.units, dcode=self.aperture.d, draw_mode=self.draw_mode)
+            statements, self.units, dcode=self.aperture.d, draw_mode=self.draw_mode, fill_mode=self.filename)
 
     @property
     def dcode(self):
@@ -467,6 +721,15 @@ class DxfFile(CamFile):
         self.statements.draw_mode = value
 
     @property
+    def fill_mode(self):
+        return self._fill_mode
+    
+    @fill_mode.setter
+    def fill_mode(self, value):
+        self._fill_mode = value
+        self.statements.fill_mode = value
+
+    @property
     def pitch(self):
         return self.statements.pitch
     
@@ -512,6 +775,9 @@ class DxfFile(CamFile):
     def rotate(self, angle, center=(0, 0)):
         self.statements.rotate(angle, center)
 
+    def negate_polarity(self):
+        self.statements.polarity = not self.statements.polarity
+
 def loads(data, filename=None):
     if sys.version_info.major == 2:
         data = unicode(data)
diff --git a/gerberex/dxf_path.py b/gerberex/dxf_path.py
index 1307411..bb620ff 100644
--- a/gerberex/dxf_path.py
+++ b/gerberex/dxf_path.py
@@ -5,13 +5,17 @@
 
 from gerber.utils import inch, metric, write_gerber_value
 from gerber.cam import FileSettings
-from gerberex.utility import is_equal_point, is_equal_value
+from gerberex.utility import is_equal_point, is_equal_value, normalize_vec2d, dot_vec2d
 from gerberex.excellon import CoordinateStmtEx
 
 class DxfPath(object):
     def __init__(self, statements, error_range=0):
         self.statements = statements
         self.error_range = error_range
+        self.bounding_box = statements[0].bounding_box
+        self.containers = []
+        for statement in statements[1:]:
+            self._merge_bounding_box(statement.bounding_box)
     
     @property
     def start(self):
@@ -116,12 +120,15 @@ class DxfPath(object):
             if j > 0:
                 del mergee[-j]
                 del self.statements[0:j]
+            for statement in mergee:
+                self._merge_bounding_box(statement.bounding_box)
             self.statements.extend(mergee)
             return True
         else:
             if self.statements[-1].is_equal_to(element, error_range) or \
                self.statements[0].is_equal_to(element, error_range):
                 return False
+            self._merge_bounding_box(element.bounding_box)
             self.statements.appen(element)
             return True
 
@@ -153,6 +160,21 @@ class DxfPath(object):
             self.statements.insert(0, element)
             return True
 
+    def _merge_bounding_box(self, box):
+        self.bounding_box = (min(self.bounding_box[0], box[0]),
+                             min(self.bounding_box[1], box[1]),
+                             max(self.bounding_box[2], box[2]),
+                             max(self.bounding_box[3], box[3]))
+
+    def may_be_in_collision(self, path):
+        if self.bounding_box[0] >= path.bounding_box[2] or \
+           self.bounding_box[1] >= path.bounding_box[3] or \
+           self.bounding_box[2] <= path.bounding_box[0] or \
+           self.bounding_box[3] <= path.bounding_box[1]:
+            return False
+        else:
+            return True
+
     def to_gerber(self, settings=FileSettings(), pitch=0, width=0):
         from gerberex.dxf import DxfArcStatement
         if pitch == 0:
@@ -244,7 +266,61 @@ class DxfPath(object):
                 out += ploter(dot[0], dot[1])
         return out
 
+    def intersections_with_halfline(self, point_from, point_to, error_range=0):
+        def calculator(statement):
+            return statement.intersections_with_halfline(point_from, point_to, error_range)
+        def validator(pt, statement, idx):
+            if is_equal_point(pt, statement.end, error_range) and \
+                not self._judge_cross(point_from, point_to, idx, error_range):
+                    return False
+            return True
+        return self._collect_intersections(calculator, validator, error_range)
+
+    def intersections_with_arc(self, center, radius, angle_regions, error_range=0):
+        def calculator(statement):
+            return statement.intersections_with_arc(center, radius, angle_regions, error_range)
+        return self._collect_intersections(calculator, None, error_range)
 
+    def _collect_intersections(self, calculator, validator, error_range):
+        allpts = []
+        last = allpts
+        for i in range(0, len(self.statements)):
+            statement = self.statements[i]
+            cur = calculator(statement)
+            if cur:
+                for pt in cur:
+                    for dest in allpts:
+                        if is_equal_point(pt, dest, error_range):
+                            break
+                    else:
+                        if validator is not None and not validator(pt, statement, i):
+                            continue
+                        allpts.append(pt)
+            last = cur
+        return allpts
+    
+    def _judge_cross(self, from_pt, to_pt, index, error_range):
+        standard = normalize_vec2d((to_pt[0] - from_pt[0], to_pt[1] - from_pt[1]))
+        normal = (standard[1], standard[0])
+        def statements():
+            for i in range(index, len(self.statements)):
+                yield self.statements[i]
+            for i in range(0, index):
+                yield self.statements[i]
+        dot_standard = None
+        for statement in statements():
+            tstart = statement.start
+            tend = statement.end
+            target = normalize_vec2d((tend[0] - tstart[0], tend[1] - tstart[1]))
+            dot= dot_vec2d(normal, target)
+            if dot_standard is None:
+                dot_standard = dot
+                continue
+            if is_equal_point(standard, target, error_range):
+                continue
+            return (dot_standard > 0 and dot > 0) or (dot_standard < 0 and dot < 0)
+        raise Exception('inconsistensy is detected while cross judgement between paths')
+            
 def generate_paths(statements, error_range=0):
     from gerberex.dxf import DxfPolylineStatement
 
@@ -287,3 +363,50 @@ def generate_paths(statements, error_range=0):
     closed_path = list(filter(lambda p: p.is_closed, paths))
     open_path = list(filter(lambda p: not p.is_closed, paths))
     return (closed_path, open_path)
+
+def judge_containment(path1, path2, error_range=0):
+    from gerberex.dxf import DxfArcStatement, DxfLineStatement
+
+    nocontainment = (None, None)
+    if not path1.may_be_in_collision(path2):
+        return nocontainment
+    
+    def is_in_line_segment(point_from, point_to, point):
+        dx = point_to[0] - point_from[0]
+        ratio = (point[0] - point_from[0]) / dx if dx != 0 else \
+                (point[1] - point_from[1]) / (point_to[1] - point_from[1])
+        return ratio >= 0 and ratio <= 1
+
+    def contain_in_path(statement, path):
+        if isinstance(statement, DxfLineStatement):
+            segment = (statement.start, statement.end)
+        elif isinstance(statement, DxfArcStatement):
+            if statement.start == statement.end:
+                segment = (statement.start, statement.center)
+            else:
+                segment = (statement.start, statement.end)
+        else:
+            raise Exception('invalid dxf statement type')
+        pts = path.intersections_with_halfline(segment[0], segment[1], error_range)
+        if len(pts) % 2 == 0:
+            return False
+        for pt in pts:
+            if is_in_line_segment(segment[0], segment[1], pt):
+                return False
+        if isinstance(statement, DxfArcStatement):
+            pts = path.intersections_with_arc(
+                statement.center, statement.radius, statement.angle_regions, error_range)
+            if len(pts) > 0:
+                return False
+        return True
+    
+    if contain_in_path(path1.statements[0], path2):
+        containment = [path1, path2]
+    elif contain_in_path(path2.statements[0], path1):
+        containment = [path2, path1]
+    else:
+        return nocontainment
+    for i in range(1, len(containment[0].statements)):
+        if not contain_in_path(containment[0].statements[i], containment[1]):
+            return nocontainment
+    return containment
diff --git a/gerberex/utility.py b/gerberex/utility.py
index 4c89fa6..37de5e8 100644
--- a/gerberex/utility.py
+++ b/gerberex/utility.py
@@ -3,7 +3,7 @@
 
 # Copyright 2019 Hiroshi Murayama <opiopan@gmail.com>
 
-from math import cos, sin, pi
+from math import cos, sin, pi, sqrt
 
 def rotate(x, y, angle, center):
     x0 = x - center[0]
@@ -18,3 +18,10 @@ def is_equal_value(a, b, error_range=0):
 def is_equal_point(a, b, error_range=0):
     return is_equal_value(a[0], b[0], error_range) and \
         is_equal_value(a[1], b[1], error_range)
+
+def normalize_vec2d(vec):
+    length = sqrt(vec[0] * vec[0] + vec[1] * vec[1])
+    return (vec[0] / length, vec[1] / length)
+
+def dot_vec2d(vec1, vec2):
+    return vec1[0] * vec2[0] + vec1[1] * vec2[1]
\ No newline at end of file