vertex detection in quad

November 1st, 2008 • ar, flash, math

Problem:

You have a quad outline as point data, and want to detect the four vertices

I googled that problem a lot but couldn’t find any solution that fitted my needs. Moreover I didn’t want to copy paste something I do not really understand, so I solved it my way

In this case I know the points D and B (detecting theese points is easy, but in some special cases you track D and A but that’s an other problem). Now I wanted to store the outline in a point array. So I started at D doing this:

_currentPt = findStartPoint(f_bmd, f_rect);
while(findNextBlackPixel(f_bmd, _currentPt, 1 , 0 , 0, 1));
while(findNextBlackPixel(f_bmd, _currentPt, 0 , 1, -1, 0));
while(findNextBlackPixel(f_bmd, _currentPt, -1 ,0, 0, -1));
while(findNextBlackPixel(f_bmd, _currentPt, 0 ,-1, 1, 0));
 
...
...
 
private function findNextBlackPixel(f_bmd : BitmapData,  pt : Point, shiftA : int, shiftB : int, shiftC : int, shiftD : int) : Boolean
{
	if(f_bmd.getPixel32(pt.x + shiftA, pt.y + shiftB) == 0xff000000)
	{
		_currentPt.x = pt.x + shiftA;
		_currentPt.y = pt.y + shiftB;
		_ptsAr.push(new Point(_currentPt.x, _currentPt.y));
		return true;
	}
	else if(f_bmd.getPixel32(pt.x + shiftC, pt.y + shiftD) == 0xff000000)
	{
		_currentPt.x = pt.x + shiftC;
		_currentPt.y = pt.y + shiftD;
		_ptsAr.push(new Point(_currentPt.x, _currentPt.y));
		return true;
	}
	_ptsAr.push(new Point(_currentPt.x, _currentPt.y));
	return false;
}

This is how I get the outline Array (Blue Line)

Now here’s the problem:

Between D and B has to be a point with MaxHeight. So how can I calculate that height value.

My solution:

Looping over triangles with differenc C values. Then you have a triangle with known Points DBC DBC’ DBC” and so on.

Fancy math:

Calculating the length from DB BC DC via sinus (easy). Now we have a trianlge DBC without any right angle. BUT we know the length of each side. After some researching I remembered this cosine math.

So we know the angle BDC now. With simple sinus we can calulate the MaxHeight. Comparing the heights -> you’re done :D

Have fun.

Trackback URI.