Create a Hertel-Mehlhorn Partition as part of a DRC run

Comments

• gyger

  January 23

  And a slightly improved version that changes the way it iterates over the triangles, checks for triangles to touch each other before merging and also calles the GC every 1000 runs, because before KLayout would crash.

  class DRC::DRCLayer
    def decompose_HM()
      result = RBA::Region.new 
      self.data.each.with_index do |p, idx|
        if p.is_convex?
          result.insert(p)
          next
        end
  
        # Get initial triangulation
        triangles_a = RBA::Region::new(p).delaunay.each.to_a
  
        i = 0
        while i < triangles_a.length
          j = i + 1
          merged_found = false
  
          while j < triangles_a.length
          # Try each pair of triangles
            if triangles_a[i].touches?(triangles_a[j])
              merged = RBA::Region.new
              merged.insert(triangles_a[i])
              merged.insert(triangles_a[j])
              # Perform merge
              merged.merge
  
                # Check if result is a single convex polygon
              if merged.count == 1 and merged[0].is_convex?
                # Update triangle list
                triangles_a[i] = merged[0]
                triangles_a.delete_at(j)
                merged_found = true
                break
              end
            end
            j += 1
          end
  
          # Only increment if no merge was found
          i += 1 unless merged_found        
        end
        result.insert(triangles_a)
        GC.start if idx % 1000 == 0 # Force Garbage Collection
      end
      return DRC::DRCLayer::new(@engine, result)
    end
  end
  
  polys = polygons("M1_Pos_Blade")
  polys.decompose_HM.output("holes")
  
• Matthias

  January 23 edited January 23

  Hi @gyger,

  That is actually very interesting. You seem to have done some research and maybe you can share some publication links? You can also send information privately through the contact mail address if you wish.

  I found this nice overview page: https://bjpcjp.github.io/pdfs/math/polygon-partitions-ADM.pdf, but a more detailed overview is appreciated.

  I am aware that my implementation is a pretty stupid one. I was mainly interested in the trapezoid decomposition as that is the basis of the MEBES format I am utilizing myself. There is a constrained Delaunay triangulation based on Chews second algorithm, but I assume this is not what you are looking for. However, as I understand, Delaunay triangulation can serve as a basis for Hertel-Mehlhorn, so that is appears a viable implementation path. What do you think?

  I am aware there is CGAL or other libraries which contain lots of awesome algorithms. But frankly, it's always a pain to integrate third-party libraries - some may not be thread safe, others don't specify anything in that respect, some are not compatible with certain systems, some are written in Fortran (which I won't ever touch again after my old days with VAX/VMS) and debugging is never fun. I prefer having the original publication and being able to implement it myself. Usually there is a lot of overlap with existing data structures I can reuse and I can take care of things like thread safety.

  Kind regards,

  Matthias
• Matthias

  January 23

  Update: I would be specifically interested in a quality convex decomposition that guarantees rectangular pieces when possible, ideally maximizing the aspect ratios of the pieces. Another thing I am interested in is an algorithm that finds the maximum rectangle that fits inside a polygon.
• gyger

  January 29

  Hello Matthias,
  sorry for responding so slow. I came only across now.

  The Hertel Mehlhorn Algorithm is original published as Fast triangulation of simple polygons (https://link.springer.com/chapter/10.1007/3-540-12689-9_105).

  I found a lot of O’Rourke, J. books very nice on Computational Geometry.
  1) O’Rourke, J. Art Gallery Theorems and Algorithms; The international series of monographs on computer science; Oxford Univ. Press: New York, NY, 1987.
  Put online by the author: https://www.science.smith.edu/~jorourke/books/ArtGalleryTheorems/
  2) O’Rourke, J. Computational Geometry in C, 2nd ed.; Cambridge University Press: Cambridge, UK, ; New York, NY, USA, 1998. https://www.science.smith.edu/~jorourke/books/compgeom.html
  3) Handbook of Discrete and Computational Geometry, Third edition.; Tóth, C., O’Rourke, J., Goodman, J. E., Eds.; CRC Press: Boca Raton, 2017.
  Preprint online: http://www.csun.edu/~ctoth/Handbook/HDCG3.html
  They usually always reference the original publication.

  Yeah, I think the constrained Delaunay triangulation is a good starting point for the Hertel-Mehlhorn algorithm.

  About libraries, I absolutely agree that these algorithms are probably best integrated into the code base of KLayout.

  On the updated message, I am currently unable to answer this, but I will keep looking.
  With maximizing aspect ratio, I guess you mean, to make them as equal as possible.
  I think they call that a fat object in geometry. Perhaps somebody else reading this has more experience there.
• Matthias

  January 30

  Hi @gyger,

  thanks for these pointers. I will take a look.

  I basically feel that A* search can be tailored to my needs, but I need to investigate that. Anyway, thanks a lot.

  Matthias