# Mining Graphic Gems

June 27, 2001
by Daniel Cummings

#### (C != Lingo) = (Lingo <> C)

Besides Lingo, there is this other programming language called "C", perhaps you have heard of it?

Well, this "C" has a long history as a powerful, multipurpose development tool. Because of that history and the fact that many, many people use it to demonstrate mathematical graphics techniques, there is a lot of freely available C code out there on the web that does some very interesting things. I don't speak "C" fluently, but I can read it a little. I have ported a few lines of code from C to Lingo.

Here are some cool mathematical algorithms (written in C) that I found while poking around the Web. I found these looking around the comp.graphics faq (see http://www.faqs.org/faqs/graphics/algorithms-faq/) There is also Graphic Gems itself (http://www.graphicsgems.org/), which is the repository of hundreds of useful algorithms. This article introduces some C algorithms and shows them side by side with the Lingo versions that I worked up and tested.

The three algorithms I chose from the comp.graphics.algorithms FAQ are:

1. polygonContainsPoint Is a point inside a polygon? TOPIC 2.03
2. polycentroid What is the center of "mass" of this polygon? TOPIC 2.02
3. getCircleCenterFromThreePoints If I make three points and generate a circle that passes through all of them, where is it and what is its radius? TOPIC 1.04

Let's jump right in then...

Here is the sample movie that shows the three algorithms in action.

1. Move the mouse in and out of the polygon to see it change color when the mouse point is inside.
2. Drag the vertices of the polygon around to see the centroid change. Remember the instruction from Ghostbusters, though: Don't cross the streams (or vector lines in this case).
3. Move the points on the circle to see the new circle made from the three points.

A sample Director 7 file is available for download in Windows or Macintosh format

#### polygonContainsPoint

Ok, there are already two commands in Lingo dealing with "intersections" of sprites on the stage and there is the inside function that can tell you if a point is in a rectangle. However, each of these native Lingo commands has limitations. The intersects and intersect functions both rely on sprites, and the inside function is limited to rects (four-sided polygons). So you have to work around these limitations to get them to do specific things. For instance, in order to test intersection of irregular shapes (polygons), sprites need to be dragged onto the stage and set to matte ink. In order to test an intersection of a point with a sprite, one sprite needs to be a one-pixel bitmap. Sometimes it's better to just cook up your own algorithms rather than try to adapt your techniques to native Lingo functions.

#### Simulations and God Games

For an application that needs to keep track of things (and their intersections) which are neither sprites nor rectangles, the inside and intersects techniques do not help.

The polygonContainsPoint algorithm is useful when you are dealing with a simulation of a "world" that is not easily represented using sprites. For example, imagine a God-game (a la Warcraft) where the "world" simulation continues even though the viewpoint is focused on just one part of that world. The calculations of whether your enemy is crossing your southeastern river border still need to happen even though your attention is elsewhere. Imagine trying to do a world simulation using sprite intersection tests!

The following polygonContainsPoint code will allow you to build complex simulations and calculate intersections without using sprites.

The C code (original code from comp.graphics.algorithms FAQ):

int pnpoly (int npol, float *xp, float *yp, float x, float y)

{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i]<=y) && (y < yp[j])) ||
((yp[j]<=y) && (y < yp[i]))) &&
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
c = !c;
}
return c;
}

Pretty scary stuff. Actually, the code is easily translated if you know a little bit of C syntax:

1. The argument list in C needs to be "typed" just like arguments need to be in the Lingo getPropertyDescriptionList function, that is why float and int are part of the parameter list
2. for means repeat
3. i = 0 is the starting value for the variable i
4. j = npol - 1 initializes the other variable, j
5. i < npol tells the repeat loop when to break out
6. j = i++ means increment the value of the variable i and set j to it after each repeat
7. && means and
8. || means or
9. =! means <>
10. the semicolon ; tells the C compiler that it's the end of the line. In Lingo we just hit the Return key to start a new line of code.

Here is the Lingo translation:

on polygonContainsPoint pts, x, y
j = pts.count
tot = pts.count
containsP = 0

repeat with i = 1 to tot
if ((pts[i][2] <= y) and (y < pts[j][2])) or »
((pts[j][2] <= y) and (y < pts[i][2])) then
if x < ((pts[j][1] - pts[i][1]) * (y - pts[i][2]) / »
float(pts[j][2] - pts[i][2])) + pts[i][1] then
containsP = not containsP
end if
end if
j = i
end repeat

return containsP

end

Whew, that's easier to read, but not by much. The math is still a little tricky. However, for most of these "Graphics Gems" algorithms, it is sufficient to just port the C code, test it and see if it does what it is supposed to do. In this case, it does.

#### polycentroid

Polycentroid helps you find the center of "mass" of any irregular closed polygon. Generally that means that you will get a point that is inside the polygon, but not always. (Try moving the polygon in the demo movie around to get the centroid to be outside the polygon.) Lingo has native functions and properties to calculate the center of a bounding box (setting the centerRegPoint and checking the regPoint), but again it is rectangle- and single-sprite-based and therefore limited.

For example, in your God-game, if you wanted to keep the captain of a battle group at the center of "mass" of the positions of his soldiers, this algorithm is your solution.

The C Code:

/*
* ANSI C code from the article
* "Centroid of a Polygon"
* by Gerard Bashein and Paul R. Detmer,
(gb / at / locke.hs.washington.edu, pdetmer / at / u.washington.edu)
* in "Graphics Gems IV", Academic Press, 1994
*/

int polyCentroid (double x[], double y[], int n,
double *xCentroid, double *yCentroid, double *area)
{
register int i, j;
double ai, atmp = 0, xtmp = 0, ytmp = 0;
if (n < 3) return 1;
for (i = n-1, j = 0; j < n; i = j, j++)
{
ai = x[i] * y[j] - x[j] * y[i];
atmp += ai;
xtmp += (x[j] + x[i]) * ai;
ytmp += (y[j] + y[i]) * ai;
}
*area = atmp / 2;
if (atmp != 0)
{
*xCentroid = xtmp / (3 * atmp);
*yCentroid = ytmp / (3 * atmp);
return 0;
}
return 2;
}

A few new C syntax things to learn:

• double is just a type of integer, Lingo makes no distinction between the various integer types.
• += means add the value on the right to the variable on the left, the same as the standard Lingo: gVar = gVar + newVar

The Lingo translation:

on polyCentroid pts

n = pts.count()
if (n < 3) then return 1

atmp = 0
xtmp = 0
ytmp = 0
i = n

repeat with j = 1 to n

ai = pts[i][1] * pts[j][2] - pts[j][1] * pts[i][2]
atmp = ai + atmp
xtmp = ((pts[j][1] + pts[i][1]) * ai) + xtmp
ytmp = ((pts[j][2] + pts[i][2]) * ai) + ytmp
i = j

end repeat

area = atmp / 2
if (atmp <> 0) then
xCentroid = xtmp / (3 * atmp)
yCentroid = ytmp / (3 * atmp)
return [xCentroid, yCentroid, area]
else
return 2
end if

end

This gem is based on the idea of breaking polygons down into triangles. The triangles's centroids are computed, then the areas of those triangles are used to determine how much "weight" to give them in their averaging. This average centroid is the centroid of the irregular polygon.

#### getCircleCenterFromThreePoints

There is no native Lingo that even comes close to doing this. I have used this code on one occasion, perhaps you can think of other applications. My application was to determine whether data points from a mouse were sketching out a circle and to determine where that circle's center was. By using this algorithm multiple times on the continuously sampled data points, I was able to "smooth out" the "circle" and determine its radius and center point.

The code:

/*
* Let the three given points be a, b, c. Use _0 and _1 to represent
*x and y coordinates. The coordinates of the center p=(p_0,p_1) of
* the circle determined by a, b, and c are:
*/

A = b_0 - a_0;
B = b_1 - a_1;
C = c_0 - a_0;
D = c_1 - a_1;

E = A* (a_0 + b_0) + B * (a_1 + b_1);
F = C* (a_0 + c_0) + D * (a_1 + c_1);

G = 2.0 * (A* (c_1 - b_1) - B * (c_0 - b_0));

p_0 = (D * E - B * F) / G;
p_1 = (A * F - C * E) / G;

/*
* If G is zero then the three points are collinear and no finite-radius
* circle through them exists. Otherwise, the radius of the circle is:
*/

r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2

This isn't really C code, but it is certainly translatable -- I pretty much copied and pasted and it worked after a few tweaks. Mining gems can be so easy!

The Lingo translation:

on getCircleCenterFromThreePoints a_0, a_1, b_0, b_1, c_0, c_1

A = b_0 - a_0
B = b_1 - a_1
C = c_0 - a_0
D = c_1 - a_1
E = A * (a_0 + b_0) + B * (a_1 + b_1)
F = C * (a_0 + c_0) + D * (a_1 + c_1)
G = 2.0 * (A * (c_1 - b_1) - B * (c_0 - b_0))

if G = 0 then G = 0.0001 --hack to avoid divide by zero
p_0 = (D * E - B * F) / G
p_1 = (A * F - C * E) / G

return [point (p_0, p_1), sqrt (((a_0 - p_0) * (a_0 - p_0)) + ((a_1 - p_1) * (a_1 - p_1)))]

end

Don't be afraid to venture beyond the usual Lingo haunts, there are gems out there in the C and C++ worlds, go and get 'em and bring them back for other Lingo programmers to use!

Happy mining!

Daniel Cummings is the founder and Chief Technologist at Polysense -- a media research and prototyping design firm in San Francisco -- where he investigates Augmented Reality and Polysensory media. Polysense provides device consulting and prototyping services to the technology industry.