/****************************************************************************
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);
}
}