TweetFollow Us on Twitter

Jul 99 Challenge

Volume Number: 15 (1999)
Issue Number: 7
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

C-to-HTML

This month, your Challenge is simple enough: generate a little HTML. Not just any HTML, of course, but HTML that displays a C or C++ program the way it looks in your Metrowerks CodeWarrior editor window. The prototype for the code you should write is:

#if defined (__cplusplus)
extern "C" {
#endif

typedef struct Settings {
	unsigned long commentColor;	/*00RRGGBB*/
	unsigned long keywordColor;	/*00RRGGBB*/
	unsigned long stringColor;	/*00RRGGBB*/
	char fontName[32];		/* font to use for display */
	unsigned long fontSize;	/* size of font to use */
	unsigned long tabSize;	/* number of spaces to use for tabs */
} Settings;

long /* output length */ CtoHTML(
	const char *inputText,	/* text to convert */
	char *outputHTML,		/* converted text */
	const Settings displaySettings	/* display parameters */
);

#if defined (__cplusplus)
}
#endif

A syntactically correct C or C++ program will be provided to you as inputText. You should convert that program to HTML so that, when displayed in the current Netscape browser (4.6 as of this writing), the code will appear as the input does when opened in CodeWarrior. The output HTML should be stored in (surprise) outputHTML, and the number of characters generated should be returned by your CtoHTML routine. Your CodeWarrior display preferences are provided in displaySettings: the colors to be used for comments, keywords, and strings, the name and size of the font to be used. The tabSize parameter should be used to convert tab characters to the appropriate number of nonbreaking spaces, so that the HTML appears correct no matter what tab setting is used in CodeWarrior.

The winner will be the solution that correctly converts C into HTML in the minimum amount of execution time. Solutions within 1% of one another in total execution time will be ranked by code size and elegance.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

This Challenge was suggested by Dennis Jones, who earns 2 Challenge points for the idea.

Three Months Ago Winner

Congratulations to Sebastian Maurer for submitting the winning entry to the April Shortest Network Challenge. This Challenge required readers to find a network of line segments connecting a specified set of nodes, minimizing both the total length of the line segments and the execution time used to create the network. Solutions were allowed to create intermediate "Steiner" nodes to reduce network length, although only one of the five solutions submitted took advantage of that option.

Sebastian's entry calculates the minimum spanning tree as a subset of the edges in a Delaunay triangulation. A concept that was also discussed by participants in the March Find A Pass Challenge, a Delaunay triangulation of a set of points in a plane has the property that the circles circumscribing the triangles do not contain any points in the set. Sebastian's solution calculates the Delaunay triangles, sorts the segments in those triangles from shortest to longest, and selects a subset of N-1 segments connecting the N points, avoiding the creation of any loops in the process.

In one of the test problems, 2000 nodes were randomly distributed within eight square regions roughly distributed in a octagonal pattern. A network generated by Sebastian's entry to this test problem is depicted below.


Network generated by Sebastian Maurer's solution

Sebastian's solution won by creating a shorter network than the other solutions. The second place solution submitted by Ernst Munter was the only entry that inserted intermediate nodes into the network. While faster, it created longer networks. Ernst decided that calculating the minimum spanning tree would be too costly, and instead calculated an approximation to the minimum spanning tree in sections. Ernst then added intermediate points until the angles formed by the segments meet a heuristic criterion. The network produced by Ernst's solution to the problem described earlier is shown in the next figure.


Network generated by Ernst Munter's solution

Note that this network contains the loops avoided by Sebastian's solution. The extra segments making up these loops account for the fact that the generated network is longer, despite the inclusion of Steiner points.

The evaluation was based on performance against 5 test cases, with an average of 2000 points per test case. The table below lists the total length of the generated networks, the number of intermediate nodes inserted into the networks, the total number of segments in the networks, the total execution time, and the overall score, as well as the code size, data size, and programming language for each of the solutions submitted. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

Name (size) Length Intermed # of Nodes Time Connect (msec) Score Code Data Lang
Sebastian Maurer (40) 17795 0 9995 696 18042 9536 320 C
Ernst Munter (437) 18361 3869 13864 648 18598 8588 8152 C++
Randy Boring (103) 18598 0 9995 58236 38374 2572 179 C
Willeke Rieken (47) 18589 0 9995 54462 38686 6640 48 C++
Andrew Downs 27439 0 9995 522169 313867 872 32 C

Top Contestants

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 10 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points
1. Munter, Ernst 205
2. Saxton, Tom 99
3. Boring, Randy 73
4. Maurer, Sebastian 60
5. Rieken, Willeke 51
6. Heithcock, JG 37
7. Lewis, Peter 31
8. Nicolle, Ludovic 27
9. Brown, Pat 20
10. Day, Mark 20
11. Hostetter, Mat 20
12. Mallett, Jeff 20
13. Murphy, ACC 14
14. Jones, Dennis 12
15. Hewett, Kevin 10
16. Selengut, Jared 10
17. Smith, Brad 10
18. Varilly, Patrick 10
19. Webb, Russ 10

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Sebastian Maurer's winning Shortest Network solution:

/*
Since the minimum spanning tree (MST) is never that much longer than the Steiner tree, and since the MST is so much easier to calculate, I wont bother searching for Steiner points.
My solution works in three stages: first, construct a list of segments. Second, quicksort them from shortest to longest. Finally, connect the shortest segments together without forming loops.
The MST is a subset of the edges in a Delauney triangulation - it is good to use the triangulation's O(N) edges rather than to have to sort all possible O(N^2) edges.  Finding the Delauney graph makes for the bulk of the code. For comparison, I left the code for the exhaustive listing of edges at the end of the file.  Just replace the call to DelauneySegments() by AllSegments() in ShortestNetwork() to see the difference.
The Delauney triangulation is done following the algorithm described in the book "Computational Geometry: Algorithms and Applications" by M. de Berg et al.
The memory requirement is about 500 bytes per node in addition to what the test code needs. For N points, 9 N + 1 triangles are needed at the most. Each triangle
requires 40 bytes. I need 3 N segments (16 bytes each), and 2 N longs for a total of 416 bytes. The largest sample I tried was 160000 points with an 80 Mb allocation. It took a minute and a half on a 233 MHz G3.
I didn't have much time to work on robustness. There may still be ways to provide a set of nodes that will cause my program to fail.
*/


#include "ShortestNetwork.h"


typedef struct Triangle {
	Node *a, *b, *c;
	// keep pointers to neighbors sharing an edge
	struct Triangle *ab, *bc, *ca;
	// and keep pointers to up to three children
	struct Triangle *child1, *child2, *child3;
	// mark triangles seen in tree traversal
	Boolean visited;
} Triangle;


typedef struct Segment {
	Connection c;
	double distSq;
} Segment;



Prototypes


long DelauneySegments(long numNodes, Node nodes[],
					  Segment *segments[],
					  Connection connections[],
					  long *numDuplicates);			  
void Quicksort(Segment segs[], long first, long last);
void BuildSpanningTree(long numNodes, Segment segs[],
					   Connection connections[],
					   long numDuplicates);


ShortestNetwork

long /* numConnections */ ShortestNetwork(
	long numInitialNodes,	/* number of nodes to connect */
	long *numIntermediateNodes, /* number of nodes added by 																	ShortestNetwork */
	Node nodes[], 
		/* Nodes 0..numInitialNodes-1 are initialized on entry. */
		/* Nodes numInitialNodes..numInitialNodes+*numIntermediateNodes 				added by ShortestNetwork */
	Connection connections[],	/* connections between nodes */
	long maxNodes,
	long maxConnections
) {
	long numSegments;
	Segment *segs;
	long numDuplicates;


	if (maxConnections<numInitialNodes) return -1;
	if (maxNodes<numInitialNodes+1) return -1;

	numSegments =
		DelauneySegments(numInitialNodes, nodes, &segs,
						 connections, &numDuplicates);
	Quicksort(segs, 0, numSegments - 1 - numDuplicates);	
	BuildSpanningTree(numInitialNodes, segs, connections,
					  numDuplicates);
	DisposePtr((char*)segs);
	*numIntermediateNodes = 0;


	// since I didn't add any nodes...
	return numInitialNodes - 1;
}

sameLabel

////////
// Given an ordered list or candidate segments,
// BuildSpanningTree fills the array with the
// (numNodes - 1) connections necessary to build
// a spanning tree. If the array of segments contains
// all the necessary edges, then the spanning tree is
// minimal.
////////
// To figure out whether to labels are equivalent,
// we iterate down the equivalence array for both
// labels until the equivalent labels are equal to
// themselves. Then we can compare.
static Boolean sameLabel(long equiv[],
						 long label1, long label2)
{
	while (equiv[label1] != label1)
		label1 = equiv[label1];
	while (equiv[label2] != label2)
		label2 = equiv[label2];
	return label1 == label2;
}


isConnected

// Two nodes can only be connected if they were
// both already labeled with equivalent labels
static Boolean isConnected(long label[], long equiv[],
						   long node1, long node2)
{
	return (label[node1] > 0) && (label[node2] > 0) &&
			sameLabel(equiv, label[node1], label[node2]);
}



BuildSpanningTree

void BuildSpanningTree(long numNodes, Segment segs[],
					   Connection connections[],
					   long numDuplicates)
// segs should be sorted from shortest to longest
// We pick (numNodes - 1) segments, starting from shortest,
// and make sure to never make a closed loop
{
	long i, j, nextLabel;
	long *label =
		(long*)NewPtr((Size)(numNodes * sizeof(long)));
	long *equiv =
		(long*)NewPtr((Size)(numNodes * sizeof(long)));
	if ((label == NULL) || (equiv == NULL))
		DebugStr("\pNot enough mem in BuildSpanningTree");
	for(i = 0; i < numNodes; i++) {
		label[i] = 0;
		equiv[i] = i;
	}
	nextLabel = 1;
	j = -1;
	for(i = numDuplicates; i < numNodes - 1; i++) {
		long node1, node2;
		do {
			j += 1;
			node1 = segs[j].c.index1;
			node2 = segs[j].c.index2;
		} while (isConnected(label, equiv, node1, node2));
		connections[i].index1 = node1;
		connections[i].index2 = node2;
		if (label[node1] == 0) {
			if (label[node2] == 0) {
				label[node1] = nextLabel;
				label[node2] = nextLabel;
				nextLabel += 1;
			} else {
				label[node1] = label[node2];
			}
		} else {
			if (label[node2] == 0) {
				label[node2] = label[node1];
			} else {
				long lab1 = label[node1];
				long lab2 = label[node2];
				if (lab1 > lab2) {
					while (equiv[lab1] != lab1)
						lab1 = equiv[lab1];
					equiv[lab1] = lab2;
				} else {
					while (equiv[lab2] != lab2)
						lab2 = equiv[lab2];
					equiv[lab2] = lab1;
				}
			}
		}
	}

		
	DisposePtr((char*)label);
	DisposePtr((char*)equiv);
}

SwapSegments

////////
// quicksort the array of segments
// sorting records rather than pointers
// is costly, but still fast compared
// to the Delauney graph calculation
////////
static inline void SwapSegments(Segment segs[],
								long i, long j)
{	
	Segment temp;
	temp.c.index1 = segs[i].c.index1;
	temp.c.index2 = segs[i].c.index2;
	temp.distSq = segs[i].distSq;
	segs[i].c.index1 = segs[j].c.index1;
	segs[i].c.index2 = segs[j].c.index2;
	segs[i].distSq = segs[j].distSq;
	segs[j].c.index1 = temp.c.index1;
	segs[j].c.index2 = temp.c.index2;
	segs[j].distSq = temp.distSq;
}

Quicksort

void Quicksort(Segment segs[], long first, long last)
{
	long left, right;
	double dividingValue;
  	left = first;
  	right = last;
  	dividingValue = segs[(first + last) / 2].distSq;
  	do { // until right < left
  		while (segs[left].distSq < dividingValue)
  			left += 1;
  		while (segs[right].distSq > dividingValue)
  			right -= 1;
  		if (left <= right) {
  			SwapSegments(segs, left, right);
  			left += 1;
  			right -= 1;
  		}
  	} while (right >= left);
  	if (right > first)
  		Quicksort(segs, first, right);
  	if (left < last)
  		Quicksort(segs, left, last);
}


det

/////
// Utility functions for the analytic geometry we need
/////


// In order to figure out whether p is to the left of the
// directed line formed by the points a and b, check if
// the following determinant is positive
//
// |  a.x  a.y  1 |
// |  b.x  b.y  1 | > 0
// |  p.x  p.y  1 |
//
static double det(Node *a, Node *b, Node *c)
{
	// neat - the determinant above can be
	// calculated with only two multiplications
	return (b->y - a->y) * (a->x - c->x) +
		   (b->x - a->x) * (c->y - a->y);
}

isInTriangle

// The vertices a, b and c of my triangles are always in
// counter clock wise order. Then a point p is inside the
// triangle only if it is to the left of the directed lines
// ab, bc and ca.
// By inside I mean *strictly* inside (not on an edge!)
static Boolean isInTriangle(Node *p, Triangle *triangle)
{
	return (det(triangle->a, triangle->b, p) > 0) &&
		   (det(triangle->b, triangle->c, p) > 0) &&
		   (det(triangle->c, triangle->a, p) > 0);
}

isOnTriangle

// By "on" I mean inside including the edges. I use
// epsilon to allow for floating point rouding problems
static Boolean isOnTriangle(Node *p, Triangle *triangle,
							double negEpsilon)
{
	return (det(triangle->a, triangle->b, p) > negEpsilon)
		&& (det(triangle->b, triangle->c, p) > negEpsilon)
		&& (det(triangle->c, triangle->a, p) > negEpsilon);
}

isInsideCircumscribedCircle

// In order to figure out whether p is inside the
// circumscribed circle of the triangle abc check
// whether the following determinant is positive
//
// |  a.x  a.y  a.x^2 + a.y^2  1 |
// |  b.x  b.y  b.x^2 + b.y^2  1 |  >  0
// |  c.x  c.y  c.x^2 + c.y^2  1 |
// |  p.x  p.y  p.x^2 + p.y^2  1 |
static Boolean isInsideCircumscribedCircle(
					Node *a, Node *b, Node *c, Node *p)
{
	return (a->x * a->x + a->y * a->y) * det(b, c, p)
		 - (b->x * b->x + b->y * b->y) * det(a, c, p)
		 + (c->x * c->x + c->y * c->y) * det(a, b, p)
		 - (p->x * p->x + p->y * p->y) * det(a, b, c) > 0;
}



MakeNewTriangle

/////
// Procedures for Delauney graph calculation
/////
// Triangles always have vertices in CCW order
// (so that det(a, b, c) is positive)
static void MakeNewTriangle(Triangle *t,
					 Node *a, Node *b, Node *c,
					 Triangle *ab, Triangle *bc,
					 Triangle *ca)
{
	t->a = a;
	t->b = b;
	t->c = c;
	t->ab = ab;
	t->bc = bc;
	t->ca = ca;
	t->child1 = NULL;
	t->child2 = NULL;
	t->child3 = NULL;	
	t->visited = false;
	if (det(a, b, c) <= 0)
		DebugStr("\pIllegal triangle created");
}



FindCommonEdge

// Given two triangles with a common edge, return
// pointers to each of the four vertices involved
// (o1, c1, c2 and o2 are in CCW order. o1 and o2
// are on the outside, and c1 and c2 are common
// to both triangles), as well as pointers
// to the neighboring triangles
static void FindCommonEdge(Triangle *t1, Triangle *t2,
						   Node **o1, Node **c1,
						   Node **c2, Node **o2,
						   Triangle **o1c1, Triangle **c2o1,
						   Triangle **o2c2, Triangle **c1o2)
{
	if ((t1->a != t2->a) && (t1->a != t2->b) &&
		(t1->a != t2->c))
	{
		*o1 = t1->a;
		*c1 = t1->b;
		*c2 = t1->c;
		*o1c1 = t1->ab;
		*c2o1 = t1->ca;
	} else if ((t1->b != t2->a) && (t1->b != t2->b) &&
			   (t1->b != t2->c))
	{
		*o1 = t1->b;
		*c1 = t1->c;
		*c2 = t1->a;
		*o1c1 = t1->bc;
		*c2o1 = t1->ab;
	} else if ((t1->c != t2->a) && (t1->c != t2->b) &&
			   (t1->c != t2->c))
	{
		*o1 = t1->c;
		*c1 = t1->a;
		*c2 = t1->b;
		*o1c1 = t1->ca;
		*c2o1 = t1->bc;
	} else {
		DebugStr("\pt1 and t2 are identical");
		return;
	}

	

	if ((t2->a != t1->a) && (t2->a != t1->b) &&
		(t2->a != t1->c))
	{
		*o2 = t2->a;
		if(*c2 != t2->b) DebugStr("\pProblem");
		if(*c1 != t2->c) DebugStr("\pProblem");
		*o2c2 = t2->ab;
		*c1o2 = t2->ca;
	} else if ((t2->b != t1->a) && (t2->b != t1->b) &&
			   (t2->b != t1->c))
	{
		*o2 = t2->b;
		if(*c2 != t2->c) DebugStr("\pProblem");
		if(*c1 != t2->a) DebugStr("\pProblem");
		*o2c2 = t2->bc;
		*c1o2 = t2->ab;
	} else if ((t2->c != t1->a) && (t2->c != t1->b) &&
			   (t2->c != t1->c))
	{
		*o2 = t2->c;
		if(*c2 != t2->a) DebugStr("\pProblem");
		if(*c1 != t2->b) DebugStr("\pProblem");
		*o2c2 = t2->ca;
		*c1o2 = t2->bc;
	}
	else DebugStr("\pA very serious problem");
}



DivideTriangleInto3

// Given a point p inside a triangle t,
// create the three new children of triangle t
// and update all the neighbors' pointers
static void DivideTriangleInto3(Triangle *t, Node *p)
{
 	MakeNewTriangle(t->child1, p, t->a, t->b,
 					t->child3, t->ab, t->child2);
	if (t->ab != NULL) {
		if (t->ab->ab == t) t->ab->ab = t->child1;
		if (t->ab->bc == t) t->ab->bc = t->child1;
		if (t->ab->ca == t) t->ab->ca = t->child1;
	}

	

	MakeNewTriangle(t->child2, p, t->b, t->c,
					t->child1, t->bc, t->child3);	
	if (t->bc != NULL) {
		if (t->bc->ab == t) t->bc->ab = t->child2;
		if (t->bc->bc == t) t->bc->bc = t->child2;
		if (t->bc->ca == t) t->bc->ca = t->child2;
	}


	MakeNewTriangle(t->child3, p, t->c, t->a,
					t->child2, t->ca, t->child1);
	if (t->ca != NULL) {
		if (t->ca->ab == t) t->ca->ab = t->child3;
		if (t->ca->bc == t) t->ca->bc = t->child3;
		if (t->ca->ca == t) t->ca->ca = t->child3;
	}
}


Divide2TrianglesInto2

// Given a point p on the edge between two triangles,
// create four new triangles and update all the
// edges, pointers, etc...
// The two child1 triangles will have a common edge
// and the two child2 will have a common edge
static void Divide2TrianglesInto2(
				Triangle *t1, Triangle *t2, Node *p)
{
	// Vertices
	Node *o1, *c1, *o2, *c2;
	// pointers to triangles on outside of quadrilateral
	Triangle *o2c2, *c2o1, *o1c1, *c1o2;
	FindCommonEdge(t1, t2, &o1, &c1, &c2, &o2,
				   &o1c1, &c2o1, &o2c2, &c1o2);
	MakeNewTriangle(t1->child1, p, c2, o1,
					t2->child1, c2o1, t1->child2);
	if (c2o1 != NULL) {
		if (c2o1->ab == t1) c2o1->ab = t1->child1;
		if (c2o1->bc == t1) c2o1->bc = t1->child1;
		if (c2o1->ca == t1) c2o1->ca = t1->child1;
	}
	MakeNewTriangle(t1->child2, p, o1, c1,
					t1->child1, o1c1, t2->child2);
	if (o1c1 != NULL) {
		if (o1c1->ab == t1) o1c1->ab = t1->child2;
		if (o1c1->bc == t1) o1c1->bc = t1->child2;
		if (o1c1->ca == t1) o1c1->ca = t1->child2;
	}
	MakeNewTriangle(t2->child1, p, o2, c2,
					t2->child2, o2c2, t1->child1);
	if (o2c2 != NULL) {
		if (o2c2->ab == t2) o2c2->ab = t2->child1;
		if (o2c2->bc == t2) o2c2->bc = t2->child1;
		if (o2c2->ca == t2) o2c2->ca = t2->child1;
	}
	MakeNewTriangle(t2->child2, p, c1, o2,
					t1->child2, c1o2, t2->child1);
	if (c1o2 != NULL) {
		if (c1o2->ab == t2) c1o2->ab = t2->child2;
		if (c1o2->bc == t2) c1o2->bc = t2->child2;
		if (c1o2->ca == t2) c1o2->ca = t2->child2;
	}
}



isSpecial

// Check whether point p is one of the fake
// points I added for convenience
static inline Boolean isSpecial(Node *p, double max)
{
	return (p->x > max) || (p->y > max) ||
		   (p->x < -max) || (p->y < -max);
}



intersects

// Two segments intersect if the endpoints of one
// lie on opposite sides of the line formed by the
// other two points, and vice-versa
static Boolean intersects(Node *a1, Node *a2,
						  Node *b1, Node *b2)
{
	double a1a2b1 = det(a1, a2, b1);
	double a1a2b2 = det(a1, a2, b2);
	double b1b2a1 = det(b1, b2, a1);
	double b1b2a2 = det(b1, b2, a2);
	return (((a1a2b1 > 0) && (a1a2b2 < 0)) ||
			((a1a2b1 < 0) && (a1a2b2 > 0))) &&
		   (((b1b2a1 > 0) && (b1b2a2 < 0)) ||
			((b1b2a1 < 0) && (b1b2a2 > 0)));
}



LegalizeEdge

// LegalizeEdge flips the common edge
// between two triangles if the initial edge can not
// be part of the Delauney graph
static void LegalizeEdge(Triangle *t1, Triangle *t2,
				Triangle triangles[], int *free, double max)
{
	// t1 and t2 are two triangles with a common edge
	// t1 has all the edges legalized from the caller
	// t2 will need to be legalized recursively if the
	// edge shared with t1 is flipped
	// Vertices in CCW order
	Node *o1, *c1, *o2, *c2;
	// Triangles on outside of quadrilateral
	Triangle *o2c2, *c2o1, *o1c1, *c1o2;
	Boolean specialCase, generalCase;
	Boolean c1Special, c2Special, o2Special, o1Special;
	// If there is no neighboring triangle, the edge has
	// to be legal. This happens if the edge c1c2 is
	// formed by two special points
	if ((t1 == NULL) || (t2 == NULL))
		return;
	FindCommonEdge(t1, t2, &o1, &c1, &c2, &o2,
				   &o1c1, &c2o1, &o2c2, &c1o2);
	c1Special = isSpecial(c1, max);
	c2Special = isSpecial(c2, max);
	o1Special = isSpecial(o1, max);
	o2Special = isSpecial(o2, max);
	// The two common vertices can't be special
	// since all added points are inside the
	// triangle formed by the three special points 
	if (c1Special && c2Special)
		DebugStr("\pBoth common vertices are special");
	// If both opposite vertices are special
	// (this can happen if the point falls on a
	// preexisting edge) we don't flip the edge
	if (o1Special && o2Special)
		return;
	// If one of the opposite vertices is special, we
	// don't flip the edge between the two common points 
	if (o2Special || o1Special)
		return;
	// If exactly one of the common vertices is special,
	// we flip the edge if the union of both triangles
	// is concave - otherwise we won't get a proper
	// triangle after the flip
	specialCase = (c1Special || c2Special) &&
				  (intersects(o1, o2, c1, c2));
	// Finally the general case when none of the points
	// is special.
	generalCase =
		!(c1Special || c2Special ||
		  o2Special || o1Special) &&
		isInsideCircumscribedCircle(o1, c1, c2, o2);
	if (specialCase || generalCase) {		
		// Create new triangles
		Triangle *newT1, *newT2;
		newT1 = &(triangles[*free]);
		*free += 1;
		newT2 = &(triangles[*free]);
		*free += 1;
		// Assign new children
		t1->child1 = newT1;
		t1->child2 = newT2;
		t2->child1 = newT1;
		t2->child2 = newT2;
		MakeNewTriangle(newT1, o1, o2, c2,
						newT2, o2c2, c2o1);
		MakeNewTriangle(newT2, o1, c1, o2,
						o1c1, c1o2, newT1);
		// Update pointers from neighbors
		if (o2c2 != NULL) {
			if (o2c2->ab == t2) o2c2->ab = newT1;
			if (o2c2->bc == t2) o2c2->bc = newT1;
			if (o2c2->ca == t2) o2c2->ca = newT1;
		}
		if (c2o1 != NULL) {
			if (c2o1->ab == t1) c2o1->ab = newT1;
			if (c2o1->bc == t1) c2o1->bc = newT1;
			if (c2o1->ca == t1) c2o1->ca = newT1;
		}
		if (o1c1 != NULL) {
			if (o1c1->ab == t1) o1c1->ab = newT2;
			if (o1c1->bc == t1) o1c1->bc = newT2;
			if (o1c1->ca == t1) o1c1->ca = newT2;
		}
		if (c1o2 != NULL) {
			if (c1o2->ab == t2) c1o2->ab = newT2;
			if (c1o2->bc == t2) c1o2->bc = newT2;
			if (c1o2->ca == t2) c1o2->ca = newT2;
		}
		// and recursively legalize the new edges on
		// the second new triangle
		LegalizeEdge(newT1, o2c2, triangles, free, max);
		LegalizeEdge(newT2, c1o2, triangles, free, max);
	}
}



isLeaf

// return true if the given triangle is at the
// end of the acyclic directed graph and has
// no more children
static inline Boolean isLeaf(Triangle *t)
{
	return ((t->child1 == NULL) &&
			(t->child2 == NULL) &&
			(t->child3 == NULL));
}



FindTriangle

///////
// Recursively find the triangle that point p is on
// (including the edge).
///////
static Triangle* FindTriangle(Node *p, Triangle *triangle,
							  double negEpsilon)
{
	if (isLeaf(triangle)) return triangle;
	if ((triangle->child1 != NULL) &&
		isOnTriangle(p, triangle->child1, negEpsilon))
			return FindTriangle(p, triangle->child1,
								negEpsilon);
	if ((triangle->child2 != NULL) &&
		isOnTriangle(p, triangle->child2, negEpsilon))
			return FindTriangle(p, triangle->child2,
								negEpsilon);
	if ((triangle->child3 != NULL) &&
		isOnTriangle(p, triangle->child3, negEpsilon))
			return FindTriangle(p, triangle->child3,
								negEpsilon);
	DebugStr("\pProblem in FindTriangle");
	return NULL;
}



FindTheOtherTriangle

// When p is on the edge of a triangle, this function
// returns the triangle that shares this edge
// If p lies on more than edge (i.e. on a vertex),
// then I return NULL
static Triangle* FindTheOtherTriangle(
					Node *p, Triangle *triangle,
					double epsilon)
{
	double detABP = det(triangle->a, triangle->b, p);
	double detBCP = det(triangle->b, triangle->c, p);
	double detCAP = det(triangle->c, triangle->a, p);
	Boolean detABPis0 = (detABP < epsilon) &&
						(detABP > - epsilon);
	Boolean detBCPis0 = (detBCP < epsilon) &&
						(detBCP > - epsilon);
	Boolean detCAPis0 = (detCAP < epsilon) &&
						(detCAP > - epsilon);
	if (detABPis0 && !detBCPis0 && !detCAPis0)
		return triangle->ab;
	if (!detABPis0 && detBCPis0 && !detCAPis0)
		return triangle->bc;
	if (!detABPis0 && !detBCPis0 && detCAPis0)
		return triangle->ca;
	if (detABPis0 || detBCPis0 || detCAPis0)
		return NULL;
		// indicate that p lies on two edges at once
	// p doesn't lie on any edge - we should
	// not have been called in this case
	DebugStr("\pProblem FindTheOtherTriangle");
	return NULL;
}



FindMultipleVertex

// If FindTheOtherTriangle returned NULL, then
// I want to find the vertex that was so close to p
static Node* FindMultipleVertex(Node *p, Triangle *t,
								double epsilon)
{
	double dxa = p->x - t->a->x;
	double dya = p->y - t->a->y;
	double dxb = p->x - t->b->x;
	double dyb = p->y - t->b->y;
	double dxc = p->x - t->c->x;
	double dyc = p->y - t->c->y;
	if ((dxa < epsilon) && (dxa > - epsilon))
		return t->a;
	else if ((dxb < epsilon) && (dxb > - epsilon))
		return t->b;
	else if ((dxc < epsilon) && (dxc > - epsilon))
		return t->c;
	else {
		// We should not have been called
		// if there is no neighboring point!
		// DebugStr("\pProblem in FindMultipleVertex");
		// return NULL;
		// but to be safe I'll just return anything :-)
		return t->a;
	}
}


addPointInsideTriangle

static void addPointInsideTriangle(Node *p, Triangle *t,
		Triangle *triangles, int *free, double max)
{	
	// Now we create the three new triangles
	t->child1 = &(triangles[(*free)++]);
	t->child2 = &(triangles[(*free)++]);
	t->child3 = &(triangles[(*free)++]);
	DivideTriangleInto3(t, p);		
	// and make sure the added edges are part of
	// a real Delauney triangulation
	LegalizeEdge(t->child1, t->ab, triangles, free, max);
	LegalizeEdge(t->child2, t->bc, triangles, free, max);
 	LegalizeEdge(t->child3, t->ca, triangles, free, max);
}



ExtractSegments

///////
// The final step in DelauneySegments is to traverse
// the triangle "tree" to build a list segments. This
// requires that all the nodes have the visited flag
// set to false. (Note that the tree is not really a
// tree, it's actually an "acyclic directed graph". The
// tree is no longer a tree after an edge flip).
///////
static void ExtractSegments(
	long *numSegments, Segment segments[],
	Triangle* mother, Node nodes[], double max)
{
	if (mother != NULL) {
		if (!(mother->visited))
		{
			mother->visited = true;
			if (isLeaf(mother))
			{
				double dx, dy;
				if (!mother->ab->visited &&
					!isSpecial(mother->a, max) &&
					!isSpecial(mother->b, max))
				{
					segments[*numSegments].c.index1 =
						mother->a - &nodes[0];
					segments[*numSegments].c.index2 =
						mother->b - &nodes[0];
					dx = mother->a->x - mother->b->x;
					dy = mother->a->y - mother->b->y;
					segments[*numSegments].distSq =
						dx * dx + dy * dy;
					*numSegments += 1;
				}
				if (!mother->bc->visited &&
					!isSpecial(mother->b, max) &&
					!isSpecial(mother->c, max))
				{
					segments[*numSegments].c.index1 =
						mother->b - &nodes[0];
					segments[*numSegments].c.index2 =
						mother->c - &nodes[0];
					dx = mother->b->x - mother->c->x;
					dy = mother->b->y - mother->c->y;
					segments[*numSegments].distSq =
						dx * dx + dy * dy;
					*numSegments += 1;
				}
				if (!mother->ca->visited &&
					!isSpecial(mother->c, max) &&
					!isSpecial(mother->a, max))
				{
					segments[*numSegments].c.index1 =
						mother->c - &nodes[0];
					segments[*numSegments].c.index2 =
						mother->a - &nodes[0];
					dx = mother->c->x - mother->a->x;
					dy = mother->c->y - mother->a->y;
					segments[*numSegments].distSq =
						dx * dx + dy * dy;
					*numSegments += 1;
				}
			}
			else
			{
				ExtractSegments(numSegments, segments,
					mother->child1, nodes, max);
				ExtractSegments(numSegments, segments,
					mother->child2, nodes, max);
				ExtractSegments(numSegments, segments,
					mother->child3, nodes, max);
			}
		}
	}
}


DelauneySegments

// Here's where the actual Delauney triangulation
// is done. We return all the edges that are part
// of the Delauney graph.
long DelauneySegments(long numNodes, Node nodes[],
					  Segment *segments[],
					  Connection connections[],
					  long *numDuplicates)
{
	int i;
	long numSegments;
	Node p1, p2, p3;
	double max, dummy;
	double epsilon, negEpsilon;
	// The maximum number of triangles constructed by
	// the algorithm is 9 N + 1
	Triangle *triangles =
		(Triangle*)NewPtr((Size)((9 * numNodes + 1)
							* sizeof(Triangle)));
	Triangle *mother = &(triangles[0]);
	// free is next available position in triangle array
	int free = 1;
	*numDuplicates = 0;
	// The maximum number of edges created by any
	// triangulation is 3 N - 3 - k, where k is the
	// number of points on the boundary of the convex hull
	*segments =
		(Segment*)NewPtr((Size)((3 * numNodes - 3)
							* sizeof(Segment)));
	if ((*segments == NULL) || (triangles == NULL)) {
		DebugStr("\pNot enough memory");
		return -1;
	}
	// Initialize mother triangle - steps 1 and 2 in book
	max = 0;
	for(i = 0; i < numNodes; i++) {
		if (nodes[i].x > max) max = nodes[i].x;
		if (nodes[i].y > max) max = nodes[i].y;
		if (nodes[i].x < -max) max = - nodes[i].x;
		if (nodes[i].y < -max) max = - nodes[i].y;
	}
	// multiply max because I like a safety margin
	epsilon = max * 1e-12;
	negEpsilon = - epsilon;
	max *= 1.1;


	// and find the coordinates of the special triangle
	dummy = max * 3;
	p1.x = dummy;
	p1.y = 0;
	p2.x = 0;
	p2.y = dummy;
	p3.x = - dummy;
	p3.y = - dummy;
	MakeNewTriangle(mother, &p1, &p2, &p3,
					NULL, NULL, NULL);
	// I should shuffle the input points if I
	// really want to avoid worst case behavior
	for(i = 0; i < numNodes; i++) {
		Node *p = &(nodes[i]);
		// First find the "leaf" triangle that contains p
		Triangle *t = FindTriangle(p, mother, negEpsilon);
		if (isInTriangle(p, t))
		{
			addPointInsideTriangle(p, t, triangles,
								   &free, max);
		}
		else // we have a degenerate case
		{
			Triangle *t2 =
				FindTheOtherTriangle(p, t, epsilon);
			if (t2 != NULL)
			//the point is on a shared edge, in which
			// case we find the other triangle and continue
			{
				t->child1 = &(triangles[free++]);
				t->child2 = &(triangles[free++]);
				t2->child1 = &(triangles[free++]);
				t2->child2 = &(triangles[free++]);
				Divide2TrianglesInto2(t, t2, p);		
				// the 2 child1 triangles have a common edge
				// the 2 child2 triangles have a common edge
				LegalizeEdge(t->child1, t->child1->bc,
							 triangles, &free, max);
				LegalizeEdge(t->child2, t->child2->bc,
							 triangles, &free, max);
				LegalizeEdge(t2->child1, t2->child1->bc,
							 triangles, &free, max);		
				LegalizeEdge(t2->child2, t2->child2->bc,
							 triangles, &free, max);
			}
			else
			// We have a duplicate point - I just connect
			// it up right away and forget about it
			{
				Node *q = FindMultipleVertex(p, t, epsilon);
				connections[*numDuplicates].index1 = i;
				connections[*numDuplicates].index2 =
					i + q - p;
				*numDuplicates += 1;
			}
		}
	}
		// Traverse the tree to build the list of edges
	numSegments = 0;
	ExtractSegments(&numSegments, *segments,
					mother, nodes, max);
	DisposePtr((char*)triangles);
	return numSegments;
}
///////
// This was my first solution that naively calculated all
// possible distances. It requires a lot of memory and
// is a very slow, but it is a lot easier to debug.
///////
/*
long AllSegments(long numNodes, Node nodes[],
				 Segment *segments[])
{
	long i, j, k;
	long numSegments = numNodes * (numNodes - 1) / 2;
	

	*segments = (Segment*) NewPtr((Size)(numSegments *
									sizeof(Segment)));
	if (segments == NULL)
		return -1;
	k = 0;
	for(i = 0; i < numNodes - 1; i++)
		for(j = i + 1; j < numNodes; j++) {
			double dx = nodes[i].x - nodes[j].x;
			double dy = nodes[i].y - nodes[j].y;
			(*segments)[k].c.index1 = i;
			(*segments)[k].c.index2 = j;
			(*segments)[k].distSq = dx * dx + dy * dy;
			k += 1;
		}
	return numSegments;
}
*/


 

Community Search:
MacTech Search:

Software Updates via MacUpdate

OmniOutliner Pro 4.2 - Pro version of th...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
VLC Media Player 2.2.1 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Nisus Writer Pro 2.1.1 - Multilingual wo...
Nisus Writer Pro is a powerful multilingual word processor, similar to its entry level products, but brings new features such as table of contents, indexing, bookmarks, widow and orphan control,... Read more
Tinderbox 6.2.0 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more
OmniOutliner 4.2 - Organize your ideas,...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
Things 2.5.4 - Elegant personal task man...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
NeoOffice 2014.10 - Mac-tailored, OpenOf...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
iPhoto Library Manager 4.2 - Manage mult...
iPhoto Library Manager allows you to organize your photos among multiple iPhoto libraries, rather than having to store all of your photos in one giant library. You can browse the photos in all your... Read more
Web Snapper 3.3.8 - Capture entire Web p...
Web Snapper lets you capture Web pages exactly as they appear in your browser. You can send them to a file as images or vector-based, multi-page PDFs. It captures the whole Web page - eliminating the... Read more
TeamViewer 10.0.41404 - Establish remote...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds, or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for... Read more

Chainsaw Warrior: Lords of the Night has...
It's time to put the Darkness back in its place now that Chainsaw Warrior: Lords of the Night has officially made it to iOS. | Read more »
A World of Ice and Fire Lets You Stalk 2...
George R. R. Martin’s A World of Ice and Fire, by Random House, is a mobile guide to the epic series. The new update gives you the Journeys map feture that will let you track the movements of 25 different characters. But don't worry, you can protect... | Read more »
Gameloft Announces Battle Odyssey, a New...
Battle Odyssey, Gameloft's newest puzzle RPG, is coming to the App Store next week. Set in the world of Pondera, you will need to control the power of the elements to defend the world from evil. You'll be able to entlist over 500 allies to aid you... | Read more »
Fusion - HDR Camera (Photography)
Fusion - HDR Camera 1.0.0 Device: iOS Universal Category: Photography Price: $1.99, Version: 1.0.0 (iTunes) Description: Fusion creates HDR (high dynamic range) photos by capturing different exposures and then combining them into one... | Read more »
Sago Mini Toolbox (Education)
Sago Mini Toolbox 1.1 Device: iOS Universal Category: Education Price: $2.99, Version: 1.1 (iTunes) Description: Come build with the Sago Mini friends! Use a wrench, try a saw, or hammer some nails. From sewing hand puppets to... | Read more »
You Should Probably Grab Hitman GO While...
Hitman GO is a surprisingly cool (yet also incredibly drastic) departure from the Hitman series. It's well worth playing for any puzzle game fans out there, and at the moment you can get your hands - or garrotte if you will - on it for a mere $0.99... | Read more »
IFTTT is Bringing Do Button and Do Note...
IFTTT has announced Do Button and Do Note for the Apple Watch. Do Button lets you make your own personalized button that can connect to things like your Google Drive, control the temperature in your home with Nest Thermostat, or turn the lights on... | Read more »
How Many Days, Hours, and Minutes Are Le...
Countdown, by Yves Tscherry, is now available on the App Store. The app keeps track of countdowns to your favorite things such as someones birthday or days till the New Year. You can display the time in seconds, minutes, hours, days, weeks, months,... | Read more »
The All-New Misfit 2.0 App is Available...
Misfit has just given their app a complete overhaul. Misfit 2.0 now has a brand new interface with a sleek design and is easier to navigate. You'll be able to sync your Misfit device and look up health and fitness information faster than ever before... | Read more »
Halo: Spartan Strike (Games)
Halo: Spartan Strike 1.0 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0 (iTunes) Description: Delve into 30 challenging missions through cities and jungles using a devastating arsenal of weapons, abilities and... | Read more »

Price Scanner via MacPrices.net

TigerText Introduces First Secure Enterprise...
TigerText, a provider of secure, real-time messaging for the enterprise, has announced the launch of TigerText for the Apple Watch. TigerText for the Apple Watch enables users to securely send and... Read more
The Conservation Fund Partners with Apple To...
The Conservation Fund has announced that it will partner with Apple to help protect working forests in the United States. The Apple initiative will conserve more than 36,000 acres of working... Read more
Clearance 13-inch 2.6GHz Retina MacBook Pro a...
B&H Photo has clearance 2014 13″ 2.6GHz/128GB Retina MacBook Pros now available for $1099, or $200 off original MSRP. Shipping is free, and B&H charges NY sales tax only. Read more
Apple refurbished 2014 13-inch Retina MacBook...
The Apple Store has Apple Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and... Read more
iMacs on sale for up to $205 off MSRP, NY tax...
B&H Photo has 21″ and 27″ iMacs on sale for up to $205 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $1019 $80 off - 21″ 2.7GHz iMac: $1189 $110 off - 21″ 2.9GHz... Read more
Sale! 16GB iPhone 5S for $1 with service
Best Buy is offering 16GB iPhone 5Ss for $1.00 with 2-year activation at a participating cellular provider. Choose free home shipping and activation, or buy online and activate during in-store pickup... Read more
Apple refurbished 2014 MacBook Airs available...
The Apple Store has Apple Certified Refurbished 2014 MacBook Airs available starting at $679. An Apple one-year warranty is included with each MacBook, and shipping is free. These are currently the... Read more
27-inch 3.5GHz 5K iMac on sale for $2349, sav...
 Adorama has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2349 including free shipping plus NY & NJ sales tax only. Their price is $150 off MSRP. For a limited time, Adorama will... Read more
Save up to $380 on an iMac with Apple refurbi...
The Apple Store has Apple Certified Refurbished iMacs available for up to $380 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27″ 3.5GHz 5K iMac – $2119 $... Read more
iFixIt Teardown Awards 12-IInch Retina MacBoo...
iFixIt has posted its illustrated teardown of the new 12-inch MacBook Retina. They note that this new MacBook is less than half the thickness of the last Apple notebook called just “MacBook” back in... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Technical Project Manager - *Apple* Pay - A...
**Job Summary** Apple Pay is seeking an experienced technical PM to…manage the on boarding of new merchants for the Apple Pay platform in the US Within this role you Read more
Senior Identity Architect - *Apple* Pay - A...
**Job Summary** Apple , Inc. is looking for a highly motivated, innovative and hands-on senior identity architect to join the Apple Pay Engineering team. You will Read more
Program Manager, *Apple* Retail Global Tale...
…for the worldwide creation and implementation of the key talent development initiatives within Apple Retail. He or she will work closely with our Retail Corporate team, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.