New Page 2

____________________________________________________________________________________

How to quickly compute the area of a polygon cutting by a line

Project for CS507 - Computational Geometry (Prof. Stefan Langerman)
Presented by Lianzhen Luo

Abstract

In this project, first the literature survey about the history of area computing has been done. Then the algorithms are presented for preprocessing a polygon (convex and simple) so that, for any line or chord of the polygon, the area of subpolygons determined by the line or chord can be determined quickly. Moveover, for the Fan problem, by using FFT (Fast Fourier Transform), we can compute each area A(Q) in O((n+k)log²n), k is the number of query lines. At last the applet demonstrates the algorithms.

Contents

Introduction

History of area computing

__________________________________________________________________________________