PedAlignment

Alignment constraint model. More...

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

---

Detailed Description

Alignment constraint model.

This part of libparted models alignment constraints.

---

Function Documentation

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.

Returns:

a PedSector on success, -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.

Returns:

a PedSector on success, -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.

Returns:

a PedSector on success, -1 on failure

int ped_alignment_init	(	PedAlignment *	align,
		PedSector	offset,
		PedSector	grain_size
	)

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:

• two input constraints: a and b.
• the new grain_size is going to be the lowest common multiple of a->grain_size and b->grain_size
• hard part - solve the simultaneous equations, for offset, where offset, X and Y are variables. (Note: offset can be obtained from either X or Y, by substituing into either equation)

        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 :-)

Note:

Returned NULL is a valid PedAlignment object, and can be used for ped_alignment_*() function.

Returns:

a PedAlignment on success, 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.

Returns:

1 on success, 0 on failure

---