region2d.hh

来自「Motion JPEG编解码器源代码」· HH 代码 · 共 1,013 行 · 第 1/2 页

		if (a_reStatus != g_kNoError)
			return;
	}
}



// Make the current region represent the union between itself
// and the other given region.
template <class INDEX, class SIZE>
template <class REGION, class REGION_O, class REGION_TEMP>
void
Region2D<INDEX,SIZE>::UnionDebug (Status_t &a_reStatus,
	REGION_O &a_rOther, REGION_TEMP &a_rTemp)
{
	typename REGION::ConstIterator itHere;
	typename REGION_O::ConstIterator itHereO;
	typename REGION_TEMP::ConstIterator itHereT;
	INDEX tnX;
		// Used to loop through points.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Calculate the union.
	a_rTemp.Assign (a_reStatus, *this);
	if (a_reStatus != g_kNoError)
		return;
	a_rTemp.Union (a_reStatus, a_rOther);
	if (a_reStatus != g_kNoError)
		return;
	
	// Loop through every point in the result, make sure it's in
	// one of the two input regions.
	for (itHereT = a_rTemp.Begin(); itHereT != a_rTemp.End(); ++itHereT)
	{
		const Extent &rHere = *itHereT;
		for (tnX = rHere.m_tnXStart; tnX < rHere.m_tnXEnd; ++tnX)
		{
			if (!a_rOther.DoesContainPoint (rHere.m_tnY, tnX)
			&& !this->DoesContainPoint (rHere.m_tnY, tnX))
				goto error;
		}
	}

	// Loop through every point in the first input region, make sure
	// it's in the result.
	for (itHere = this->Begin(); itHere != this->End(); ++itHere)
	{
		const Extent &rHere = *itHere;
		for (tnX = rHere.m_tnXStart; tnX < rHere.m_tnXEnd; ++tnX)
		{
			if (!a_rTemp.DoesContainPoint (rHere.m_tnY, tnX))
				goto error;
		}
	}

	// Loop through every point in the second input region, make sure
	// it's in the result.
	for (itHereO = a_rOther.Begin();
		 itHereO != a_rOther.End();
		 ++itHereO)
	{
		const Extent &rHere = *itHereO;
		for (tnX = rHere.m_tnXStart; tnX < rHere.m_tnXEnd; ++tnX)
		{
			if (!a_rTemp.DoesContainPoint (rHere.m_tnY, tnX))
				goto error;
		}
	}

	// The operation succeeded.  Commit it.
	Assign (a_reStatus, a_rTemp);
	if (a_reStatus != g_kNoError)
		return;

	// All done.
	return;

error:
	// Handle deviations.
	fprintf (stderr, "Region2D::Union() failed\n");
	fprintf (stderr, "First input region:\n");
	PrintRegion (*this);
	fprintf (stderr, "Second input region:\n");
	PrintRegion (a_rOther);
	fprintf (stderr, "Result:\n");
	PrintRegion (a_rTemp);
	assert (false);
}



// Subtract the other region from the current region, i.e.
// remove from the current region any areas that exist in the
// other region.
template <class INDEX, class SIZE>
template <class REGION>
void
Region2D<INDEX,SIZE>::Subtract (Status_t &a_reStatus,
	const REGION &a_rOther)
{
	typename REGION::ConstIterator itHere;
		// Where we are in the other region's extents.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Run through the extents in the other region, subtract them from
	// the current region.
	for (itHere = a_rOther.Begin();
		 itHere != a_rOther.End();
		 ++itHere)
	{
		// Subtract this extent from the current region.
		Subtract (a_reStatus, (*itHere).m_tnY, (*itHere).m_tnXStart,
			(*itHere).m_tnXEnd, a_rOther, itHere.itNext);
		if (a_reStatus != g_kNoError)
			return;
	}
}



// Subtract the other region from the current region, i.e.
// remove from the current region any areas that exist in the
// other region.
template <class INDEX, class SIZE>
template <class REGION, class REGION_O, class REGION_TEMP>
void
Region2D<INDEX,SIZE>::SubtractDebug (Status_t &a_reStatus,
	REGION_O &a_rOther, REGION_TEMP &a_rTemp)
{
	typename REGION::ConstIterator itHere;
	typename REGION_O::ConstIterator itHereO;
	typename REGION_TEMP::ConstIterator itHereT;
	INDEX tnX;
		// Used to loop through points.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Calculate the difference.
	a_rTemp.Assign (a_reStatus, *this);
	if (a_reStatus != g_kNoError)
		return;
	a_rTemp.Subtract (a_reStatus, a_rOther);
	if (a_reStatus != g_kNoError)
		return;
	
	// Loop through every point in the result, make sure it's in
	// the first input region but not the second.
	for (itHereT = a_rTemp.Begin(); itHereT != a_rTemp.End(); ++itHereT)
	{
		const Extent &rHere = *itHereT;
		for (tnX = rHere.m_tnXStart; tnX < rHere.m_tnXEnd; ++tnX)
		{
			if (!(this->DoesContainPoint (rHere.m_tnY, tnX)
			&& !a_rOther.DoesContainPoint (rHere.m_tnY, tnX)))
				goto error;
		}
	}

	// Loop through every point in the first input region, and if it's
	// not in the second input region, make sure it's in the result.
	for (itHere = this->Begin(); itHere != this->End(); ++itHere)
	{
		const Extent &rHere = *itHere;
		for (tnX = rHere.m_tnXStart; tnX < rHere.m_tnXEnd; ++tnX)
		{
			if (!a_rOther.DoesContainPoint (rHere.m_tnY, tnX))
			{
				if (!a_rTemp.DoesContainPoint (rHere.m_tnY, tnX))
					goto error;
			}
		}
	}

	// Loop through every point in the second input region, make sure
	// it's not in the result.
	for (itHereO = a_rOther.Begin();
		 itHereO != a_rOther.End();
		 ++itHereO)
	{
		const Extent &rHere = *itHere;
		for (tnX = rHere.m_tnXStart; tnX < rHere.m_tnXEnd; ++tnX)
		{
			if (a_rTemp.DoesContainPoint (rHere.m_tnY, tnX))
				goto error;
		}
	}

	// The operation succeeded.  Commit it.
	Assign (a_reStatus, a_rTemp);
	if (a_reStatus != g_kNoError)
		return;

	// All done.
	return;

error:
	// Handle deviations.
	fprintf (stderr, "Region2D::Subtract() failed\n");
	fprintf (stderr, "First input region:\n");
	PrintRegion (*this);
	fprintf (stderr, "Second input region:\n");
	PrintRegion (a_rOther);
	fprintf (stderr, "Result:\n");
	PrintRegion (a_rTemp);
	assert (false);
}



// Flood-fill the current region.
template <class INDEX, class SIZE>
template <class CONTROL>
void
Region2D<INDEX,SIZE>::FloodFill (Status_t &a_reStatus,
	CONTROL &a_rControl, bool a_bVerify)
{
	typename CONTROL::ConstIterator itExtent;
		// An extent we're examining.
	Extent oFoundExtent;
		// An extent we found to be part of the region.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// How we set up depends on whether we're to verify all existing
	// region extents.
	if (a_bVerify)
	{
		// The to-do-list becomes the current region, and we empty
		// out the current region too.
		a_rControl.m_oAlreadyDone.Clear();
		if (a_rControl.m_oToDo.CanMove (*this))
		{
			// Grab the extents right out of the current region.
			a_rControl.m_oToDo.Clear();
			a_rControl.m_oToDo.Move (*this);
		}
		else
		{
			// Copy the extents from the current region, then empty it.
			a_rControl.m_oToDo.Assign (a_reStatus, *this);
			if (a_reStatus != g_kNoError)
				return;
			Region2D<INDEX,SIZE>::Clear();
		}
	}
	else
	{
		// The already-done list starts with the region, i.e. every
		// extent already known to be in the region can avoid getting
		// tested.
		a_rControl.m_oAlreadyDone.Assign (a_reStatus, *this);
		if (a_reStatus != g_kNoError)
			return;
	
		// Start the to-do list with a border around all the extents in
		// the region.
		a_rControl.m_oToDo.MakeBorder (a_reStatus, *this);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Now pull each extent out of the to-do list.  Determine which
	// sub-extents are part of the region.  Add those found extents
	// to the region.  Then add all extent surrounding the found extents
	// to the to-do-next list.
	itExtent = a_rControl.m_oToDo.Begin();
	while (itExtent != a_rControl.m_oToDo.End())
	{
		bool bStartedExtent;
			// true if we've started finding an extent.
		INDEX tnX;
			// Where we're looking for extents.

		// Get the extent, converting the type if necessary.
		Extent oExtent;
		oExtent.m_tnY = (*itExtent).m_tnY;
		oExtent.m_tnXStart = (*itExtent).m_tnXStart;
		oExtent.m_tnXEnd = (*itExtent).m_tnXEnd;

		// We're about to check this extent.  Put it in the
		// already-checked list now.
		a_rControl.m_oAlreadyDone.Union (a_reStatus, oExtent.m_tnY,
			oExtent.m_tnXStart, oExtent.m_tnXEnd);
		if (a_reStatus != g_kNoError)
			return;
	
		// If this extent shouldn't be considered, skip it.
		if (!a_rControl.ShouldUseExtent (oExtent))
			goto nextExtent;

		// Make sure our client left us with a valid extent.
		assert (oExtent.m_tnXStart < oExtent.m_tnXEnd);
		
		// Run through the pixels described by this extent, see if
		// they can be added to the region, and remember where to
		// search next.
		oFoundExtent.m_tnY = oExtent.m_tnY;
		bStartedExtent = false;
		for (tnX = oExtent.m_tnXStart; tnX <= oExtent.m_tnXEnd; ++tnX)
		{
			// Is this point in the region?
			if (tnX < oExtent.m_tnXEnd
			&& a_rControl.IsPointInRegion (tnX, oExtent.m_tnY))
			{
				// This point is in the region.  Start a new extent
				// if we didn't have one already, and add the point
				// to it.
				if (!bStartedExtent)
				{
					oFoundExtent.m_tnXStart = tnX;
					bStartedExtent = true;
				}
				oFoundExtent.m_tnXEnd = tnX + 1;
			}

			// This point is not in the region.  Any extent we're
			// building is done.
			else if (bStartedExtent)
			{
				// Add this extent to the region.
				Union (a_reStatus, oFoundExtent.m_tnY,
					oFoundExtent.m_tnXStart, oFoundExtent.m_tnXEnd);
				if (a_reStatus != g_kNoError)
					return;

				// Now add all surrounding extents to the to-do-next
				// list.
				a_rControl.m_oNextToDo.UnionSurroundingExtents
					(a_reStatus, oFoundExtent.m_tnY,
						oFoundExtent.m_tnXStart, oFoundExtent.m_tnXEnd);
				if (a_reStatus != g_kNoError)
					return;

				// Look for another extent.
				bStartedExtent = false;
			}
		}

nextExtent:
		// Move to the next extent.
		++itExtent;

		// If the to-do list needs to be replenished, do so.
		if (itExtent == a_rControl.m_oToDo.End())
		{
			// Replenish the to-do list.
			a_rControl.m_oNextToDo.Subtract (a_reStatus,
				a_rControl.m_oAlreadyDone);
			if (a_reStatus != g_kNoError)
				return;
			a_rControl.m_oToDo.Clear();
			a_rControl.m_oToDo.Merge (a_rControl.m_oNextToDo);
			
			// Start over at the beginning.
			itExtent = a_rControl.m_oToDo.Begin();
		}
	}
}



// Make the current region represent the border of the other
// region, i.e. every pixel that borders the region but isn't
// already in the region.
template <class INDEX, class SIZE>
template <class REGION>
void
Region2D<INDEX,SIZE>::MakeBorder (Status_t &a_reStatus,
	const REGION &a_rOther)
{
	typename REGION::ConstIterator itExtent;
		// Used to loop through the other region's extents.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Start with an empty region.
	Region2D<INDEX,SIZE>::Clear();

	// For every extent in the other region, add every surrounding
	// extent.  That creates a region that looks like the other region,
	// but also contains the border we're after.
	for (itExtent = a_rOther.Begin();
		 itExtent != a_rOther.End();
		 ++itExtent)
	{
		UnionSurroundingExtents (a_reStatus, (*itExtent).m_tnY,
			(*itExtent).m_tnXStart, (*itExtent).m_tnXEnd);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Finally, subtract the other region.  That punches a hole in us,
	// and creates the border region we're after.
	Subtract (a_reStatus, a_rOther);
	if (a_reStatus != g_kNoError)
		return;
}



// Add all extents surrounding the given extent.  Used by FloodFill().
template <class INDEX, class SIZE>
void
Region2D<INDEX,SIZE>::UnionSurroundingExtents (Status_t &a_reStatus,
	INDEX a_tnY, INDEX a_tnXStart, INDEX a_tnXEnd)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Add the extent above this one.
	Union (a_reStatus, a_tnY - 1, a_tnXStart, a_tnXEnd);
	if (a_reStatus != g_kNoError)
		return;

	// Add the extent in the middle.
	Union (a_reStatus, a_tnY, a_tnXStart - 1, a_tnXEnd + 1);
	if (a_reStatus != g_kNoError)
		return;

	// Add the extent below this one.
	Union (a_reStatus, a_tnY + 1, a_tnXStart, a_tnXEnd);
	if (a_reStatus != g_kNoError)
		return;
}



// Less-than operator.
template <class INDEX, class SIZE>
inline bool
Region2D<INDEX,SIZE>::Extent::operator <
	(const Region2D<INDEX,SIZE>::Extent &a_rOther) const
{
	// Compare on y, then x-start.
	if (m_tnY < a_rOther.m_tnY)
		return true;
	if (m_tnY > a_rOther.m_tnY)
		return false;
	if (m_tnXStart < a_rOther.m_tnXStart)
		return true;
	// if (m_tnXStart >= a_rOther.m_tnXStart)
		return false;
}



// Default constructor.  Must be followed by a call to Init().
template <class INDEX, class SIZE>
template <class REGION>
Region2D<INDEX,SIZE>::FloodFillControl<REGION>::FloodFillControl()
{
	// Nothing to do.
}



// Initializing constructor.
template <class INDEX, class SIZE>
template <class REGION>
Region2D<INDEX,SIZE>::FloodFillControl<REGION>::FloodFillControl
	(Status_t &a_reStatus)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Initialize ourselves.
	Init (a_reStatus);
	if (a_reStatus != g_kNoError)
		return;
}



// Initializer.  Must be called on default-constructed objects.
template <class INDEX, class SIZE>
template <class REGION>
void
Region2D<INDEX,SIZE>::FloodFillControl<REGION>::Init
	(Status_t &a_reStatus)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Initialize our helper regions.
	m_oToDo.Init (a_reStatus);
	if (a_reStatus != g_kNoError)
		return;
	m_oAlreadyDone.Init (a_reStatus);
	if (a_reStatus != g_kNoError)
		return;
	m_oNextToDo.Init (a_reStatus);
	if (a_reStatus != g_kNoError)
		return;
}



#endif // __REGION2D_H__