Geometry Functions

[Baker]

A bit of a headache, but why else do anything ...

1. Area = 0
2. Area = Circle
3. Split into 2 chords and 1 triangle. Calc from there.
4. Split into 4 chords and 3 triangles. Calc from there.
5. 6 chords, 5 triangles. Calc.
6. 2 chords, 2 triangles. Calc.
7. 4 chords. 3 triangles. Calc.
8. 1 chord. 2 triangles. Calc.
9. Area = triangle

+/- margin of error counting offhand.

[Baker]

Fast forward 4 years:

One day I am in New York, standing outside the United Nations building. I am eating a hotdog.

Hillary Clinton is standing somewhere, the Russia ambassador to the UN sticks out his hand. Hillary sticks out her hand. The Russian ambassador walks right by Hillary with his extended hand and starts shaking my hand and says,

Russian Ambassador: "Baker, I want to thank you for your circle-triangle area calculator on behalf of all the mathematicians in Russia."

Surprised, I share the handshake but I'm all like ...

Baker: "I'm really glad you like it."

Baker: "But, uh ... how'd you know I was standing around here?"
Russian Ambassador: "In Soviet Russia, math formula find YOU!!"
Baker: "I kind of opened the door for that one didn't I?"
Russian Ambassador: "Yes you did."
Baker: "Any chance I get an autographed picture of Gorbachev?"
Russian Ambassdor: "No."
Baker: "Well, it never hurts to ask."

At least this how I figure how the future is going to play out. I'm not often right about these kinds of things.

More info:

http://mathworld.wolfram.com/Circle-...ersection.html

[MadGypsy]

hmmm, #2 seems "wrong". Granted the circular area doesn't encompass any edges or vertices but it is still selecting the polygon - so in a sense it is still 3 vertices, because you would need those points to determine the surface point of the poly.

[Baker]

hmmm, #2 seems "wrong". Granted the circular area doesn't encompass any edges

That list is the total area of the intersection, like the 2D area. Not the edges and so forth. Although I see what you mean.

I hadn't even considered the idea of calculating the boundaries length of an intersection.

Another useful one:

http://www.mathopenref.com/polygonirregulararea.html

[MadGypsy]

I bet it would be pretty tough to figure out my interpretation of #2 cause you essentially have no data to tap. If it was easy as saying "get the points of this polygon I am occupying" - then that same "function" could be used for all other examples.

I am actually faced with a very similar problem to the one I just described. I am building a game and I have a bitmask set so the characters can accurately navigate uneven terrain, but I want to suppress the navigation to all polys that are at an angle less than N. However, considering the character is the circle and the polygon is the triangle, and the situation is #2 - I have no intersections to triangulate an angle from.

There is no pitch or roll values available because it isn't a rotated "brush". It is heightmap generated polys that are basically just positioned in 3d space. It would be great if I could figure this out cause filling a board up with clip "brushes" seems like a really hacked way to work around my dilemma.

[Baker]

I bet it would be pretty tough to figure out my interpretation of #2 cause you essentially have no data to tap. If it was easy as saying "get the points of this polygon I am occupying" - then that same "function" could be used for all other examples.

I am actually faced with a very similar problem to the one I just described. I am building a game and I have a bitmask set so the characters can accurately navigate uneven terrain, but I want to suppress the navigation to all polys that are at an angle less than N. However, considering the character is the circle and the polygon is the triangle, and the situation is #2 - I have no intersections to triangulate an angle from.

There is no pitch or roll values available because it isn't a rotated "brush". It is heightmap generated polys that are basically just positioned in 3d space. It would be great if I could figure this out cause filling a board up with clip "brushes" seems like a really hacked way to work around my dilemma.

I bet if you posted your problem at Inside3D or Func_Msgboard it'd be "resolved" rather quickly. "Resolved" does not necessarily mean "solved" ... "resolved" could mean "solved" or determined to be "unsolvable" due to unknown factor. I don't see why you couldn't interpret your circle as an octagon or square or such.

Anyway, this isn't the right place to investigate that because:

A) Both Inside3D and Func_Msgboard have lots of very experienced and deep knowledge.
B) Some of them are game designers or strange and powerful combinations beyond just that.

[FC Zvyozdochka]

Good day, guys!
First, I lol'd hardly when reading your story about ambassador, Baker
Second, I don't like my first variant of intersection algorithm, cause it needs to calculate six equation systems of second order. That link to Wolfram's site you posted gives a very close solution as I want to post now, the only difference is that it is given to infinite line.
Our case is about 3 finite lines forming triangle.
The solution are that distance between studying line and circle's center are found. When distance is equal to radius, then line intersects circle. When it is less than radius, line is going inside circle. When it is larger, then line is going outside.

[FC Zvyozdochka]

So we are to find 2 distances - lets call them deltaX and deltaY (Δx and Δy).
x0, y0 are the coords of the circle's center.
A, B - two points defining line.

Δx=x0-x
Δy=y0-y=y0-(k*x+b)

Domain area of the line function's argument is (xA, xB).

Now we have 2 functions of one variable x, and there is no need to make equations system.

Distance δ=Δx^2+Δy^2=(x0-x)^2+(y0-k*x-b)^2

[FC Zvyozdochka]

Now it is time to open parenthesis, but it is too boring, so I'm waiting while old Wolfram's Mathematica 5 is found on my another comp. It is very powerful and user-friendly program.

Actually, the right solution is given in your link, Baker.
The only need to do is to check whether intersection point(s) is inside or outside domain area. If it is outside - than line segment does not intersect circle. If both intersection points are outside domain area and distance δ is lesser than radius - then the whole segment is inside hat circle. Respectively, if δ>R - the whole segment is outside.

Now when we have found all intersection points, it is time to find overlap area.
The hardest thing is for me to determine the type of overlap (in numbers from post 13's pic). But this is possible when intersection point and lines' (or better vertexes') positions (inside/outside circle) are known. So lets think that we've found that type.
The main problem now is to find areas of circle segments by 2 intersection points and radius.
Obvious way is to throw lines from intersection points A and B to the center C, then to find sector's area and to subtract area of triangle ABC from it.
But it is need to find angle between them. I only know how to find its cosine - cosα = (xAxB + yAyB)/((xA� + yA�)(xB� + yB�))^1/2.
In this formula place of origin is the center of circle. So in general case xA goes to (xA-x0), yA goes to (yA-y0) and so on.
α=arccos((xAxB + yAyB)/((xA� + yA�)(xB� + yB�))^1/2)

Sector's area is 0.5*R^2*(α-sin(α))
Triangle's ABC area could easily be calculated in matrix form as show in post #6.

This solution should work good, but I don't like its bulkiness. I'll tell if I find more elegant one.

[Baker]

Good day, guys!
First, I lol'd hardly when reading your story about ambassador, Baker

I'm glad my sense of humor carried across the language barrier

Sometimes I wonder if things don't get lost in translation at times, but not this time

[Baker]

Now it is time to open parenthesis, but it is too boring, so I'm waiting while old Wolfram's Mathematica 5 is found on my another comp. It is very powerful and user-friendly program.

Actually, the right solution is given in your link, Baker.
The only need to do is to check whether intersection point(s) is inside or outside domain area. If it is outside - than line segment does not intersect circle. If both intersection points are outside domain area and distance δ is lesser than radius - then the whole segment is inside hat circle. Respectively, if δ>R - the whole segment is outside.

Right now I'm trying to organize stuff together, I bet it starts snapping together quite quickly at some point. I'm trying to work through odds and ends like fitting chords into results. I'm not quite there yet ...

And I really want to put linear equations into a matrix 2 x 3, but for some reason infinite slope is holding me back and shouldn't apply to a matrix 2x3 ?

/***********************************************************************************************************\
 *****
 **
 **	geometry_2d.h:	Math functions and macros.
 **
 *****
 \***********************************************************************************************************/


#ifndef GEOMETRY_2D_H
#define GEOMETRY_2D_H

#include "engine.h"
#include "mathlib.h"

// Special Note:	Only convex polygons are supported at this time.  Generally.
//					

typedef float Point_2D[2];

typedef enum // C: An enumeration set can contain duplicate constant values
{
	
	MAX_OBJECTS_2D		= 512,				// Max entities

	MAX_VERTICES		= 32,				// Supports maximum of 32 vertices (corners or points per poly, so 32 sided poly is max)
	MAX_LINE_SEGMENTS	= MAX_VERTICES,
} geoLimits_t;

typedef enum
{
// Special

	G_COMPLEX			= -2,   // Special case
	
	G_CIRCLE_ELLIPSE	= -1,	// Circle and friends
	
	G_NOTHING			= 0,	// Invalid results
	G_POINT				= 1,	// One vertex.		No perimeter/circumference.  No area.
	G_LINE_SEGMENT		= 2,	// Two vertices.	Has perimeter.  No area.
	G_TRIANGLE			= 3,
	G_RECT_QUAD			= 4,	// We mean quadrilateral.  However, that would confuse normal people.
} geoshape_t;


typedef struct
{
	int				isVerticalLine;		// Special case: use x = mY + b or something?
	float			slope;
	float			intercept;
} line_t;


typedef struct line_segment_s
{
	Point_2D		start;
	Point_2D		end;
	
	float			length;
	line_t			linearEquation;		// Slope intercept form: y = mX + b
} line_segment_t;

typedef struct geo_object_s
{
// possible future support of compound polys
	struct 
	geo_object_s*	childchain;

	
// aggregate data.  Not necessarily populated
	Point_2D		center;					// Center or origin or centroid or whatever you prefer.
	Point_2D		minimums;
	Point_2D		maximums;

	float			perimeter;				// Perimeter or circumference
	float			area;					
	float			width;
	float			height;
	
	int				numberVertices;			// Circle = -1, point = 1, line segment = 2, triangle = 3, etc.
	Point_2D		vertices[MAX_VERTICES];	// Vertices.  These are points at the corners.
	
	line_segment_t	linesegments[MAX_LINE_SEGMENTS];
	

	// Bookkeeping ...
	struct 
	geo_object_s*	next;

	int				index;
	const char*		name;
	
	
} geo_object_t;


geo_object_t* GeoObjects[MAX_OBJECTS_2D];

int numGeoObjects;





#endif // ! GEOMETRY_2D_H

[FC Zvyozdochka]

And I really want to put linear equations into a matrix 2 x 3, but for some reason infinite slope is holding me back and shouldn't apply to a matrix 2x3 ?

Which ones you want to put in?

If you are solving an inhomogeneous system of equations, then you have 2 matrices: the main matrix A, containing coefficients, and B - matrix of free terms.
Matrix A MUST be square one (must have equal numbers of lines and columns), otherwise the whole system could have no solutions at all (except some special cases). Matrix B has 1 column and as many lines as "A" has.

[Baker]

Well ...

I'm trying to determine that. And I'm not quite sure.

Maybe it should be a 2x2 matrix. I don't know how to put the slope intercept into the matrix, which I know sounds stupid. I have my damn textbook from college sitting right here and it isn't helping.

Which seems like the most trivial thing to be (somewhat) stuck on. I guess it is a 2x2 matrix? But I only have 2 numbers?

Y = [X factor + intercept] or do I have

X = [Y factor + intercept]
Y = [X factor + intercept]

I'm not sure how to handle this. Especially to avoid infinite slope problem. I want slope to fit into a floating point number always.

What do you feel is the best way? Especially --- if possible -- avoiding the infinite slope problem.

[Baker]

Y = [X factor + intercept] or do I have

X = [Y factor + intercept]
Y = [X factor + intercept]

Or ... this seems even more logical ...

X = [X factor + Y factor + intercept]
Y = [X factor + Y factor + intercept]

But to make it a 3 x 3 matrix, I'd need a 3rd row? Well, what the heck would go in there and why? Because I am doing 2D and not using Z.

And with that I'm still not sure what to do with the infinite slope issue. Argh.

[Baker]

I've got this resolved. My limitation is no right way to handle an infinite number in IEEE 754 floating point, but not an issue now.