Geometry Functions

[Baker]

Just storing a list of geometry functions that eventually I might up end using for some things involving 2D rendering:

2D (not 3D)
Length of Line (x1, y1, x2, y2) = sqrt ( SQUARED(x2-x1)) + SQUARED(y2-y1) )

Slope of Line (x1, y1, x2, y2) = (y2 - y1) / ( x2 - x1) // Handle div0 situation

Calc interception of 2 lines return x, y intersection
Calc area of triangle accepting any 3 vectors
Calc center of convex polygon with N vertices
Calc area of convex polygon with N vertices (split into series of triangles, area and sum)

[MadGypsy]

what if n2 is in a negative direction from n1? - you would end up with a negative line length
If I'm picturing the implication of your equation correctly, you need to determine the lowest values before you do any math to it. or use an math.abs() wrapper in your Pythagorean theorem.

function length(x1,x2,y1,y2)
{
    a = math.abs(x2-x1);
    b = math.abs(y2-y1);
    c = math.sqrt((a*a)+(b*b));
    return c;
}

just my two Krugerrands
Michael

[Baker]

what if n2 is in a negative direction from n1? - you would end up with a negative line length

Well, you can't square a real number and get a negative result.

-2 Squared = 4
2 Squared = 4

[MadGypsy]

**face palms self***

carry on ...lol
Michael

P.S. What are you doing this for? Are you making a game?

[Baker]

P.S. What are you doing this for? Are you making a game?

I've come to the conclusion that 2D math and 3D math calculations are far simpler than I realized in the past. I've been working through a ton of geometry problems lately. Some of this is due to looking inside the guts of some of the open source Quake map editors.

I used to fear 2D and 3D math and mostly wanted to avoid it.

[FC Zvyozdochka]

Calc interception of 2 lines return x, y intersection

First you need to tell are these lines are infinite or not (the second case is of 2 segments). Two segments may have no intersections along its length.
Second - how each of these lines are determined, as 2 points or as equation?
Interception is easily found as general solution for 2 equations:
Line 1 - y1=K1*x+B1
Line 2 - y2=K2*x+B2
y1=y2 (condition of the intersection)
K1*x+B1=K2*x+B2

xI=(B2-B1)/(K1-K2)
yI=K1*xI+B1=K2*xI+B2


If line is determined by two points, then it is need to find K coefficient and B summand:
K=(y2-y1)/(x2-x1)
B=y1-K*x1=y2-K*x2

Calc area of triangle accepting any 3 vectors

Actually I don't understand what are you meaning - do you want to find area of the triangle formed by 3 lines crossing in 3 points or not?

Calc center of convex polygon with N vertices

Polygon is determined by N verticles with coordinates x1...xN and y1...yN (we are currently exploring 2D space).
X-coordinate of central point of the polygon is calculated as follows:
Xc=(X1+X2+...+Xn)/n, where
Xc - X-coordinate of central point
X1...Xn - coordinates of the verticles
n - number of verticles

Y-coordinate of central point of the polygon is calculated similarly.

Calc area of convex polygon with N vertices (split into series of triangles, area and sum)

The most obvious way for me is to calc area of the each triangle and then to sum them all.
Each triangle is determined by 3 points - (v1, v2, vC) for the first one, (v2, v3, vC) for the second, ... , (vM, vN, vC) for the penultimate one, (vN, v1, vC) for the last one, where
vC - is the central point of polygon (evaluated as shown above)
v1, v2, ... , vM, vN - are the vertexes.
Area of the each triangle is evaluated as half of the product of two vectors - for the triangle which is determined by points A, B, C, the area is ABxAC or BAxBC or CAxCB (does not matter which one choosed). The resulting formula of the triangle's area is shown below:



Sorry if I said the thing that you already know.

[Baker]

Sorry if I said the thing that you already know.

The triangle area by any 3 points calculation was very useful. Far simpler than the formula I was going to use. Thanks!

(That probably saved me 30 minutes and is a better formula. And I obviously can use that one for the convex polygon one.)

[FC Zvyozdochka]

That's good. It is always a pleasure to help!

And I obviously can use that one for the convex polygon one.

Not only for convex, you can even use it for some cases of non-convex ones (like stars, for example). The only conditions are that sides of the polygon don't intersect each other and central point is inside the polygon.

[MadGypsy]

...looking inside the guts of some of the open source Quake map editors

Man, build me a worldcraft clone that exports as .obj and skips all the Quake related stuff
(vis , txqbsp - etc). I don't even need light entities.

[Baker]

The only conditions are that sides of the polygon don't intersect each other and central point is inside the polygon.

Any idea on how to accurately calculate the total area of triangle and circle overlap for circle at X, Y with radius of R and Triangle with X, Y points ABC?

Or even calculate the intersection points?

You seem to know your geometry.

[FC Zvyozdochka]

Let's start from last to first.

You seem to know your geometry.

Yep, but my english is not so good. And then some misunderstanding may occur, and actually I already have one - what is overlap? That red area on related pic, as far as google.translate tells me something like that, or other?

I'll be thinking that figures are placed like in the picture and then I'll make all conclusions.

Or even calculate the intersection points?

Well, this is the easy - we are to find general solutions for 3 equation systems. There will be up to 6 points of intersection.

Triangle (A,B,C) contains 3 lines - AB, BC, CA. It is easy to find it's canonic equations when the points' coordinates are known, as I've shown in my first post.

Circle cannot be represented as single function in Cartesian coordinates, so it is divided by 2 halfs:
yC1(x)=y0+(R^2-(x-x0))^0.5 and
yC2(x)=y0-(R^2-(x-x0))^0.5 where
yC1(x), yC2(x) - functions of top and bottom halfs respectively;
y0, x0 - coords of the circle's center
R - radius of the circle

There will be 6 systems with 2 equations in each one.

As one of the equations in each system is of second order, the general solution is not so easy to find, but I'll tell you my variant of it after having some sleep.

Any idea on how to accurately calculate the total area of triangle and circle overlap for circle at X, Y with radius of R and Triangle with X, Y points ABC?

When intersection points are known, it is not so hard. But it depends on the required accuracy.
If it is affordable for you - then you can calculate the area of the figure (from triangle up to hexagon) formed by intersection points.
If not - then you'll need to find areas of triangles and circular sectors forming overlap figure. It is much harder to do, but not too hard. I'll tell about it next morning too.

[Baker]

actually I already have one - what is overlap?

I'll draw up a pic and post it in a while.

As one of the equations in each system is of second order, the general solution is not so easy to find, but I'll tell you my variant of it after having some sleep.


When intersection points are known, it is not so hard. But it depends on the required accuracy.
If it is affordable for you - then you can calculate the area of the figure (from triangle up to hexagon) formed by intersection points.
If not - then you'll need to find areas of triangles and circular sectors forming overlap figure. It is much harder to do, but not too hard. I'll tell about it next morning too.

It is very cool you know this stuff. Things involving circles appear to be less clear than the other types of functions.

I spent a few hours working on a representation of mapping a rect to a trapezoid the other day and things with fixed sides all seem to work out:

X = [ BX - AX         (CX - DX) - (BX - AX)            ]
      [---------- +  --------------------------  +  AX  ]
      [  X2 - X1        CY-BY                                ]
      [                                                              ]
Y =  [(CY - BY) - (DY - AY)    (DY - AY)              ]
      [-----------------------  +  ------------  +  AY  ]
      [  BX - AX                         Y2 - Y1             ]

But sections of a circle are a bit tough for me to get a grasp of how to calculate.

[Baker]

Owwww ...

[Baker]

Partial piece of puzzle, not so easy ...

Circular segment - Wikipedia, the free encyclopedia

Easy:

http://en.wikipedia.org/wiki/Circular_sector

[Baker]

Intersection of circle walkthrough ....

phatcode.net / articles / graphics / tutorials / circle-triangle intersection method