geom.cpp revision fc69b99d41121cdaab54d55eb2efe2dc3c6ac358
/**
* \brief Various geometrical calculations.
*/
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
namespace Geom {
/**
* Finds the intersection of the two (infinite) lines
* defined by the points p such that dot(n0, p) == d0 and dot(n1, p) == d1.
*
* If the two lines intersect, then \a result becomes their point of
* intersection; otherwise, \a result remains unchanged.
*
* This function finds the intersection of the two lines (infinite)
* defined by n0.X = d0 and x1.X = d1. The algorithm is as follows:
* To compute the intersection point use kramer's rule:
* \verbatim
* convert lines to form
* ax + by = c
* dx + ey = f
*
* (
* e.g. a = (x2 - x1), b = (y2 - y1), c = (x2 - x1)*x1 + (y2 - y1)*y1
* )
*
* In our case we use:
* a = n0.x d = n1.x
* b = n0.y e = n1.y
* c = d0 f = d1
*
* so:
*
* adx + bdy = cd
* adx + aey = af
*
* bdy - aey = cd - af
* (bd - ae)y = cd - af
*
* y = (cd - af)/(bd - ae)
*
* repeat for x and you get:
*
* x = (fb - ce)/(bd - ae) \endverbatim
*
* If the denominator (bd-ae) is 0 then the lines are parallel, if the
* numerators are 0 then the lines coincide.
*
* \todo Why not use existing but outcommented code below
* (HAVE_NEW_INTERSECTOR_CODE)?
*/
{
/* X = (-d1, d0) dot (n0[Y], n1[Y]) */
if (denominator == 0) {
if ( X == 0 ) {
return coincident;
} else {
return parallel;
}
}
return intersects;
}
/* ccw exists as a building block */
int
/* Determine which way a set of three points winds. */
{
/* compare slopes but avoid division operation */
if(c > 0)
return +1; // ccw - do these match def'n in header?
if(c < 0)
return -1; // cw
/* Colinear [or NaN]. Decide the order. */
return -1; // p2 < p0 < p1
return +1; // p0 <= p1 < p2
} else {
return 0; // p0 <= p2 <= p1
}
}
/** Determine whether the line segment from p00 to p01 intersects the
infinite line passing through p10 and p11. This doesn't find the
point of intersection, use the line_intersect function above,
or the segment_intersection interface below.
\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
*/
bool
{
}
/** Determine whether two line segments intersect. This doesn't find
the point of intersection, use the line_intersect function above,
or the segment_intersection interface below.
\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
*/
bool
{
/* true iff ( (the p1 segment straddles the p0 infinite line)
* and (the p0 segment straddles the p1 infinite line) ). */
}
/** Determine whether \& where a line segments intersects an (infinite) line.
If there is no intersection, then \a result remains unchanged.
\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
**/
{
} else {
return no_intersection;
}
}
/** Determine whether \& where two line segments intersect.
If the two segments don't intersect, then \a result remains unchanged.
\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
**/
{
} else {
return no_intersection;
}
}
/** Determine whether \& where two line segments intersect.
If the two segments don't intersect, then \a result remains unchanged.
\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11.
**/
{
}
// this is used to compare points for std::sort below
static bool
{
if (A[X] < B[X]) {
return true;
} else if (A[X] == B[X] && A[Y] < B[Y]) {
return true;
} else {
return false;
}
}
// TODO: this can doubtlessly be improved
static void
{
if (size < 2)
return;
if (size == 2) {
}
} else {
if (size == 3) {
}
} else {
// we have size == 4
}
}
}
}
}
/** Determine whether \& where an (infinite) line intersects a rectangle.
*
* \a c0, \a c1 are diagonal corners of the rectangle and
* \a p1, \a p1 are distinct points on the line
*
* \return A list (possibly empty) of points of intersection. If two such points (say \a r0 and \a
* r1) then it is guaranteed that the order of \a r0, \a r1 along the line is the same as the that
* of \a c0, \a c1 (i.e., the vectors \a r1 - \a r0 and \a p1 - \a p0 point into the same
* direction).
*/
{
using namespace Geom;
Point B(A[X], C[Y]);
Point D(C[X], A[Y]);
}
}
}
}
// sort the results so that the order is the same as that of p0 and p1
}
}
return results;
}
/**
* polyCentroid: Calculates the centroid (xCentroid, yCentroid) and area of a polygon, given its
* vertices (x[0], y[0]) ... (x[n-1], y[n-1]). It is assumed that the contour is closed, i.e., that
* the vertex following (x[n-1], y[n-1]) is (x[0], y[0]). The algebraic sign of the area is
* positive for counterclockwise ordering of vertices in x-y plane; otherwise negative.
* Returned values:
0 for normal execution;
1 if the polygon is degenerate (number of vertices < 3);
2 if area = 0 (and the centroid is undefined).
* for now we require the path to be a polyline and assume it is closed.
**/
const unsigned n = p.size();
if (n < 3)
return 1;
double atmp = 0;
for (unsigned i = n-1, j = 0; j < n; i = j, j++) {
}
if (atmp != 0) {
return 0;
}
return 2;
}
}
/*
Local Variables:
mode:c++
c-file-style:"stroustrup"
c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
indent-tabs-mode:nil
fill-column:99
End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :