Files | |
file | natmath.h |
Data Structures | |
struct | _PedAlignment |
Defines | |
#define | PED_MAX(a, b) ( ((a)>(b)) ? (a) : (b) ) |
#define | PED_MIN(a, b) ( ((a)<(b)) ? (a) : (b) ) |
Typedefs | |
typedef _PedAlignment | PedAlignment |
Functions | |
PedSector | abs_mod (PedSector a, PedSector b) |
EuclidTriple | extended_euclid (int a, int b) |
PedSector | ped_alignment_align_down (const PedAlignment *align, const PedGeometry *geom, PedSector sector) |
This function returns the closest sector to sector that lies inside geom that satisfies the given alignment constraint align . | |
PedSector | ped_alignment_align_nearest (const PedAlignment *align, const PedGeometry *geom, PedSector sector) |
This function returns the sector that is closest to sector , satisfies the align constraint and lies inside geom . | |
PedSector | ped_alignment_align_up (const PedAlignment *align, const PedGeometry *geom, PedSector sector) |
This function returns the closest sector to sector that lies inside geom that satisfies the given alignment constraint align . | |
void | ped_alignment_destroy (PedAlignment *align) |
Free up memory associated with align . | |
PedAlignment * | ped_alignment_duplicate (const PedAlignment *align) |
Return a duplicate of align . | |
int | ped_alignment_init (PedAlignment *align, PedSector offset, PedSector grain_size) |
Initialize a preallocated piece of memory for an alignment object (used by PedConstraint). | |
PedAlignment * | ped_alignment_intersect (const PedAlignment *a, const PedAlignment *b) |
This function computes a PedAlignment object that describes the intersection of two alignments. | |
int | ped_alignment_is_aligned (const PedAlignment *align, const PedGeometry *geom, PedSector sector) |
This function returns 1 if sector satisfies the alignment constraint align and lies inside geom . | |
PedAlignment * | ped_alignment_new (PedSector offset, PedSector grain_size) |
Return an alignment object (used by PedConstraint), representing all PedSector's that are of the form offset + X * grain_size . | |
PedSector | ped_div_round_to_nearest (PedSector numerator, PedSector divisor) |
PedSector | ped_div_round_up (PedSector numerator, PedSector divisor) |
PedSector | ped_greatest_common_divisor (PedSector a, PedSector b) |
PedSector | ped_round_down_to (PedSector sector, PedSector grain_size) |
PedSector | ped_round_to_nearest (PedSector sector, PedSector grain_size) |
PedSector | ped_round_up_to (PedSector sector, PedSector grain_size) |
Variables | |
const PedAlignment * | ped_alignment_any |
const PedAlignment * | ped_alignment_any = &_any |
const PedAlignment * | ped_alignment_none |
const PedAlignment * | ped_alignment_none = NULL |
This part of libparted models alignment constraints.
PedSector ped_alignment_align_down | ( | const PedAlignment * | align, | |
const PedGeometry * | geom, | |||
PedSector | sector | |||
) |
This function returns the closest sector to sector
that lies inside geom
that satisfies the given alignment constraint align
.
It prefers sectors that are before sector
(are not larger than sector
), but does not guarantee that this.
-1
on failure PedSector ped_alignment_align_nearest | ( | const PedAlignment * | align, | |
const PedGeometry * | geom, | |||
PedSector | sector | |||
) |
This function returns the sector that is closest to sector
, satisfies the align
constraint and lies inside geom
.
-1
on failure PedSector ped_alignment_align_up | ( | const PedAlignment * | align, | |
const PedGeometry * | geom, | |||
PedSector | sector | |||
) |
This function returns the closest sector to sector
that lies inside geom
that satisfies the given alignment constraint align
.
It prefers sectors that are beyond sector
(are not smaller than sector
), but does not guarantee that this.
-1
on failure Initialize a preallocated piece of memory for an alignment object (used by PedConstraint).
The object will represent all sectors s for which the equation s = offset + X * grain_size
holds.
PedAlignment * ped_alignment_intersect | ( | const PedAlignment * | a, | |
const PedAlignment * | b | |||
) |
This function computes a PedAlignment object that describes the intersection of two alignments.
That is, a sector satisfies the new alignment object if and only if it satisfies both of the original ones. (See ped_alignment_is_aligned() for the meaning of "satisfies")
Apart from the trivial cases (where one or both of the alignment objects constraints have no sectors that satisfy them), this is what we're trying to do:
a
and b
.a->grain_size
and b->grain_size
offset = \p a->offset + X * \p a->grain_size (1) offset = \p b->offset + Y * \p b->grain_size (2)
or, abbreviated:
o = Ao + X*Ag (1) o = Bo + Y*Bg (2) => Ao + X*Ag = Bo + Y*Bg (1) = (2) X*Ag - Y*Bg = Bo - Ao (3)
As it turns out, there only exists a solution if (Bo - Ao) is a multiple of the GCD of Ag and Bg. Reason: all linear combinations of Ag and Bg are multiples of the GCD.
Proof:
A * Ag + B * Bg = A * (\p a * gcd) + B * (\p b * gcd) = gcd * (A * \p a + B * \p b)
gcd is a factor of the linear combination. QED
Anyway, a
* Ag + b
* Bg = gcd can be solved (for a
, b
and gcd) with Euclid's extended algorithm. Then, we just multiply through by (Bo - Ao) / gcd to get (3).
i.e.
A * Ag + B * Bg = gcd A*(Bo-Ao)/gcd * Ag + B(Bo-Ao)/gcd * Bg = gcd * (Bo-Ao)/gcd X*Ag - Y*Bg = Bo - Ao (3) X = A*(Bo-Ao)/gcd Y = - B*(Bo-Ao)/gcd
then:
o = Ao + X*Ag (1) = Ao + A*(Bo-Ao)/gcd*Ag o = Bo + Y*Bg (2) = Bo - B*(Bo-Ao)/gcd*Ag
Thanks go to Nathan Hurst (njh@hawthorn.csse.monash.edu.au) for figuring this algorithm out :-)
NULL
is a valid PedAlignment object, and can be used for ped_alignment_*() function.NULL
on failure int ped_alignment_is_aligned | ( | const PedAlignment * | align, | |
const PedGeometry * | geom, | |||
PedSector | sector | |||
) |
This function returns 1 if sector
satisfies the alignment constraint align
and lies inside geom
.
1
on success, 0
on failure