/**************************************************************************** Function Purpose: To compute the min total cost to connect all intersections. The list intersects[] stores the intersecting edges. The list is constructed by walking around the boundary of the flaw clockwise, adding edge(s) whenever two adjacent pixels have different pixel values. Then, do a stable sort on the list by the pixels' gray levels. The integer count is the total number of intersections. The 2-d array d[i][j] stores either the Euclidean distance between intersects[i] and intersects[j] when there is a legal connection between i and j or INF otherwise. The 2-d array t[i][j] stores the min total cost to interconnect edges from i through j. The 2-d array m[i][j] stores the index of the first cut when connecting from i through j. The 1-d array mid[i] stores the index of the edge in the list intersects[] that i will be connected to. The loop below following this function will connect all pairs of incoming/outgoing edges as computed: for (int i=0; i=j) t[i][j] = 0; else t[i][j] = INF; } } /* DP calculation */ int temp; for (m=2; m<=count; m+=2) { for (i=0; i<=count-m; i++) { j = i + m - 1; for (k=i+1; k<=j; k++) { temp = d[i][k] + t[i+1][k-1] + t[k+1][j]; if (temp=j) return; /* m[i][j] is the index of the first cut when connecting i through j */ int k = m[i][j]; if (k==j) /* the first connection is connecting i w/ j */ { mid[i] = j; mid[j] = i; FindMid (m, i+1, j-1); } else /* the first cut is between i and j */ { mid[i] = k; mid[k] = i; FindMid (m, i+1, k-1); FindMid (m, k+1, j); } }