A Programmer's Geometry.pdf-资料库

A programmer's geometry Adrian Bowyer BSc, PhD, ACGI, MBCS University of Bath and John Woodwark BSc, PhD, CEng, MIMechE, MBCS IBM UK Scientific Centre, Winchester Butterworths London Boston Singapore Sydney Toronto Wellington

Part of Reed International P.L.C. All rights reserved. No part of this publication may be reproduced or transmitted in any form or by any means (including photocopying and recording) without the written permission of the copyright holder except in accordance with the provisions of the Copyright Act 1956 (as amended) or under the terms of a licence issued by the Copyright Licensing Agency Ltd, 33-34 Alfred Place, London, England, WC1E 7DP. The written permission of the copyright holder must also be obtained before any part of this publication is stored in a retrieval system of any nature. Applications for the copyright holder's written permission to reproduce, transmit or store in a retrieval system any part of this publication should be addressed to the Publishers. Warning: The doing of an unauthorised act in relation to a copyright work may result in both a civil claim for damages and criminal prosecution. This book is sold subject to the Standard Conditions of Sale of Net Books and may not be re-sold in the UK below the net price given by the Publishers in their current price list. First published, 1983 Reprinted, 1984, 1985, 1988 © A Bowyer & J R Woodwark, 1983 British Library C a t a l o g u i ng in P u b l i c a t i on D a ta Bowyer, A. A programmer's geometry. 1. Geometry I. Title 516 QA445 II. Woodwark, J. ISBN 0-408-1242-0 Pbk The cover picture was generated on a computer using a geometric modelling system written by John Woodwark at Bath University. Printed in England by Hartnolls Ltd., Bodmin, Cornwall

A straight line segment can be drawn joining any two points. Any straight line segment can be extended indefinitely in a straight line. Given any straight line segment, a circle may be drawn having the segment as radius and one end point as centre. All right angles are congruent. If two lines are drawn which intersect a third in such a way that the sum of the inner angles on one side is less than two right angles, then the two lines inevitably intersect on that side if they are extended far enough. Euclid's five postulates (circa 300 B.C.) To describe right lines and circles are problems, but not geometrical problems. The solution of these problems is required from mechanics, and by geometry the use of them, when so solved, is shown; and it is the glory of geometry that, from those few principles brought from without, it is able to produce so many things. Isaac Newton's preface to Principia (1686 A.D.)

Foreword This book aims to fulfil two needs of the programmer whose work includes geometric calculations. Firstly, it provides useful formulae in a single source. Secondly, it presents advice on, and examples of, the computer representation and coding of geometry. Applications are not restricted to computer graphics, although graphics are useful for checking, even when the working program will produce no pictures. The reader is assumed to have a grasp of simple Euclidean geometry and the Cartesian coordinate system. For some sections an elementary knowledge of calculus and vector algebra is desirable. The reader is also assumed to be familiar with a scientific programming language, such as FORTRAN, Pascal, or BASIC. The scope of this book has been determined by the authors' own experiences in designing and implementing programs. We hope that many readers will find that it is applicable to their work, too. We would, however, be interested to hear about material that we should, perhaps, have included. Notification of mistakes that have escaped checking will also be received with thanks and acknowledgement. A number of the authors' colleagues have assisted in the preparation of this book. We would like to thank them all, and in particular Professor John Fitch and Julian Padget for the use of their symbolic algebra package and Dr Peter Green as the originator of the subroutines for perspective projection described in Chapter Six. We are also grateful for the understanding shown by our wives. Adrian Bowyer and John Woodwark University of Bath, Autumn 1982

Introduction The chapters in this book are divided into sections, each dealing with the representation and solution of a single geometrical problem. The sections are usually headed with a diagram to make reference easier. As far as possible uniform conventions have been observed throughout diagrams, algebra, and code. The nomenclature adopted is a compromise between uniformity and the symbols already in wide use for certain equations. It is as follows: A, Β, C, and D Coefficients of implicit equations of lines and planes F, G, and H Coefficients of parametric lines I J, Subscript of a known radius κ, L, M, and Ν Labels of points Ρ and Q R Vectors Radius and distance in general S and Τ Parameters υ, ν, and W χ. Y, and Ζ Second set of coordinate values Coordinates in space OL, ß, 7, and θ Angles (in radians) In the text and diagrams only points appear as capital letters. In the coding examples capitals are used throughout to avoid problems for readers whose computer facilities do not support lower case 1

letters. Symbols are never used for different purposes in upper and lower case. Subscripts are widely employed in a number of different ways. They may define more than one set of constants, as in two different straight lines: a x + b y +c =0 1 1 1 a x + b y +c 2 2 =0 2 They may specify values corresponding to points, so that, for example, the coordinates of point J would be (x , y ), or they may indicate parameter values; χ might be the value of χ w h e re a parameter, J J t, say, was zero. Generally, subscripted variables are those known 0 in advance, and variables without subscripts are to be calculated. Primed variables, such as x f , are avoided as far as possible, but are sometimes used where numerical subscripts would be inappropriate. In drawing the diagrams the aim has been to strike a balance between consistency and an excessive use of special symbols, line types, and tones. Three line types (dashed, thin, and thick) show lines of increasing interest, and dashed lines are also used where only distance, rather than an actual line, is to be indicated. Three intensities of tone are used to define areas, and to indicate surfaces and solids. Points given as part of a problem are labelled with the letters J to N, as mentioned above, while unknown points are labelled (x, y), with numerical subscripts on χ and y when there is more than one value for each. Lines are υ η label led if they are given, unless there is more than one, when they are numbered. Lines to be calculated are labelled with their equation: ax + by + c = 0. Planes are labelled similarly. After the first diagram in a section, which usually shows a simple case of the geometry to be discussed, the conventions are often relaxed, especially in complicated diagrams enumerating all possible cases of a problem. This informality in labelling also extends to non-circular curves and three-dimensional figures, with clarity as the main objective throughout The selection of a programming language in which to provide examples of coding involved some deliberation. The authors finally decided to use FORTRAN 77. They did this in an attempt to recognise the obvious virtues of structured languages, whilst acknowledging that many geometric applications are tied to a vast amount of existing software, such as graphics packages, written in FORTRAN. They hope that there is enough structure in FORTRAN 77 to satisfy ALGOL 68 and C programmers. In any case there are no curly brackets or semi-colons to baffle the BASIC enthusiast The authors have tried to use FORTRAN 77 straightforwardly, too. All the algebra has been written out in the code, without attempting to use arrays, subroutines, or functions to mimic the vector and matrix operations available implicitly in other languages, such as APL. The code is distinguished from the rest of the text and algebra by a different typeface. Comments have not been included in FORTRAN standard form, but in italics to the right of lines of code, to save space. The number of comments has been decided by the fact that code is preceded by a diagram and explanation. The reader would often be well advised to lay his code out more sparsely 2

with more comments, directed, of course, at his particular problem. Most of the examples of code are assumed to be part of a larger program section, not subroutines in their own right In these cases there are no SUBROUTINE, FUNCTION, RETURN, or END statements. Any arrays used are declared in a disconnected section above the executable statements. If a condition, most often an error, occurs such that all the code should not be executed, a special italic comment line is inserted, starting with a row of dots. This indicates what condition has occurred, and should be replaced in an actual program by code to report the error in a WRITE statement or to set a condition flag. As a final deviation from the FORTRAN 77 standard, continuation lines are started with the ampersand (&) character, which is a little more readable than the FORTRAN standard system when column numbers are not shown. Single variables from the text are translated directly into the code. Subscripts simply form the second letter of the variable name, so that χ becomes XJ, for example. Angles are written out as ALPHA, BETA, GAMMA and THETA, and are never subscripted. W h en additional variables are introduced, these are assembled as far as possible from the components of the relevant algebraic expression. Thus χ - χ becomes XLK, for instance. W h en two different terms would have the same name using this convention, or the FORTRAN six letter name limit is exhausted, other mnemonics are chosen. Some names, such as DENOM for the bottom line of a fraction, and ROOT for the result of a square root operation, are used consistently throughout Also suffices, such as SQ for a squared t e r m, or INV for a reciprocal, are generally employed, again where the name length restriction will allow. Thus lines such as XJSQ = XJ*XJ XJINV = 1.0/XJ are common. Multiplication by a reciprocal is often used when many terms must be divided by a single term. This is done because the division operation is commonly the slowest on a computer, but the best balance will depend on the reader's own system. If there is any chance at all of the denominator in a division operation being so near to zero that the result of the division exceeds the largest real number with which the computer can cope, then the value of the denominator must be checked before the division commences. In this book this is achieved by comparing the absolute value of the denominator with a notional accuracy value, which is always called ACCY. This value should be selected with regard for the likely size of numbers that will be encountered in a program. ACCY should be set so as to avoid rejecting good data, while also considering the characteristics of the computer being used. For instance, an accuracy parameter of 10 might be set in a data s t a t e m e nt ~S DATA ACCY / l . O E- 6/ This is a good general purpose value for systems w h e re real number calculations are done in a floating point format giving an average resolution of 6 or 7 decimal places, and the data are values not too far from 1 (say 0.01 to 100.0). In e x t r e me cases a single accuracy parameter may not be 3

applicable throughout a program, especially if it is used for other purposes; for instance to determine the distance between points below which they can be considered to be coincident. Careful thought is needed to decide what accuracy values actually refer to, particularly when values to be compared are dimensionally different, such as distance and squared distance. These are problems of numerical analysis, and the reader is referred to W e eg and Reed for a fuller t r e a t m e nt W h e re other books are referred to in the text only the author's name is given. There is a list of references after Chapter Nine, w h e re the reader may find the full titles of the books, together with a few words about each one. 4

资料库

A Programmer's Geometry.pdf

相关推荐

开发技术

热门标签

最新资料