邁向王者的旅途

偶然間需要用到把直角多邊形 (rectilinear polygon) 切割成數個互相不重疊的矩形 (沒有其他最佳化要求)，因為大多數找到的方法有最佳化的需求 (像是用最少的矩形或是舉行要盡可能大之類的)，所以實作起來都還挺煩的，不過今天偶然間找到一篇方法超簡單的論文，雖然有點久了，不過已經滿合乎我需求了，就把它實作出來了

我已經放上 github 了，連帶相關的論文跟方法簡介
https://github.com/shininglion/rectirization

2017年9月6日

[EDA] Pin Accessibility Evaluation Model for Improving Routability of VLSI Designs

其實這就是我在日本一個月做出來的成果。探討的是 standard cell design 的 pin accessibility 的影響

2017年8月27日

[EDA] Negotiation-Based Maze Routing 的部分困擾

Negotiation-based maze routing 可以說是現在 router 的基礎架構了，這個主要因素來自於當有許多 Net 要共同競爭相同的路徑以便縮短線長時，這個機制會讓競爭激烈的地區有相對大的成本，讓有其他選擇的 Net 可以轉而選擇相對較差但仍能完成繞線的路徑。當然，這種機制聽起來很單純美好，實作起來時總是會有其他許許多多衍伸的問題

2017年7月26日

[EDA] Transmission Gate (傳輸閘) - Logic Switch using CMOS design

目前數位 IC 設計上所用到的電晶體分成兩種型態 P-type MOSFET (P-MOS) & N-type MOSFET (N-MOS)，兩者在數位 IC 設計上的功用都是當做開關 (switch)，用以控制電流是否能通過。另外由於 MOSFET 本身的特性：電壓要低於一定閥值 (threshold voltage) 才能導通，同時這個閥值不是固定的，會受到源極 (source) 訊號以及汲極 (drain) 訊號的電壓影響 (好像是叫 body effect，先進製程應該會有更多會影響 threshold voltage 的問題)，因此 P-MOS 跟 N-MOS 在啟動開關跟傳輸電流上各有差異：

2017年7月23日

[C++] boost::geometry::overlaps 的檢查與預期不符

目前的程式因為需要大量的多邊形操作，所以現在是直接用 boost::geometry 來做相關的運算，其中很常用的是要檢查 2 個多邊形是否重疊到，在 boost::geometry 中有提供 2 種操作：intersects & overlaps，兩者差異如下：

intersects：2 個多邊形只要有 "一個點" 重疊到就算有相交
overlaps：2 個多邊形必須要有重疊到 "一塊面" 才算

所以如果今天要檢查 2 個多邊形是否只有重疊到 "一條邊" 就必須自己想辦法兜出來，但這不是這次的重點，這次的重點在 overlaps 有另一個隱藏的細節：

其中一個多邊形不能完全包含住另一個多邊形

這種情形下，overlaps 的回傳值是 false，然後我 TMD 踩到這狀況結果問題找超久阿阿阿阿

舉個例子，下面這隻程式的 p1 被包在 p2 裡，但是這情況 overlaps 的回傳值是 false (也就是沒有重疊)：

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
typedef boost::geometry::model::point<int, 2, boost::geometry::cs::cartesian> point_t;
typedef boost::geometry::model::box<point_t> box_t;
// point should be in clockwise order
typedef boost::geometry::model::polygon<point_t> polygon_t;

int main()
{
    const polygon_t p1 {{{0, 0}, {0, 2}, {2, 2}, {2, 0}, {0, 0}}};
    const polygon_t p2 {{{0, 0}, {0, 3}, {3, 3}, {3, 0}, {0, 0}}};
    printf("is overlap? %d\n", boost::geometry::overlaps(p2, p1));
    return 0;
}

boost geometry 的實作從 document 來看應該是有遵照一定的規範在處理，不過我到現在還沒仔細看過，搞不好那規範裡面有一些跟一般預期不同的結果...Orz