CS计算机代考程序代写 data structure database algorithm 25_Computational_Geometry.pdf

25_Computational_Geometry.pdf

Lecture 25
Computational Geometry

EECS 281: Data Structures & Algorithms

Data Structures & Algorithms

Computational Geometry Overview

Raster (Bitmap) Graphics

Images on screen are represented by pixel arrays

Same idea works for storing images in files
• RGB: 3 colors per pixel, 1 byte per color
• An 1920×1080 image would require ~6.22MB
• Much larger files for high-res camera images

3

Vector Graphics Scale Better

4

Image Compression

• Lossy vs. lossless compression

• Flat background and sparse line graphics
compress well without losses

• Vector graphics compress even better
5

Basic Geometry Objects

Points, segments and lines in 2D and 3D
2D point: (x,y)
2D segment: two distinct points: {(x0, y0), (x1, y1)}
2D line: slope + intercept: (k, c) in y = k x + c
A segment defines a line
• Given two unequal points, solve for k, c

• Different segments may define the same line
• Must use floats or doubles, not ints

6

! = ($! − $”)/((! − (“)
) = $! − !(!

$! = !(! + )
$” = !(” + )

Geometry Transforms

Idea: modify all points & segments the same way
• Shifting/displacing point (x, y) by a vector (dx, dy)

(x, y) → (x + dx, y + dy)
• Scaling/stretching in the x dimension by C > 0

(x, y) → (C x, y)
• Mirroring in the x dimension

(x, y) → (-x, y)
• Rotation by angle θ

(x, y) → cos . − sin .sin . cos .
(
$ =

( cos . − $ sin .
( sin . + $ cos .

7

“Rotation Matrix”

Basic Geometry Questions

• Given two lines
– If they intersect, find their intersection point

• Given three points
– Do they lie on the same line? Find their triangle area?
– Are they ordered clockwise or counter-clockwise?

• Given point P and line L
– Does P lie on L? Find the point on L closest to P

• Given N points (1D, 2D, 3D)
– Find the smallest rectilinear bounding box of N points
– Find a closest pair of points
– Find a closest point among N to a given point A

8

Basic Geometry Questions

Two very different kinds of question

1. Deal with several points, lines, segments at
a time w/o considering algorithmic complexity
– Often solved by simple formulas or simple logic

2. Deal with collections of N points, lines,
segments;
need efficient algorithms in terms of N
– Often use simple formulas many times

9

Floating-Point Comparisons ==

General Rule 1: When comparing floating-
point values for equality, use approximate
comparisons.

Instead of using
if (a == b)

use
if (fabs(a – b) < epsilon) for a suitable epsilon, for example constexpr float epsilon = 0.0001; 10 Floating-Point Comparisons <,>

General Rule 2: When comparing floating-
point values for inequality, use approximate
comparisons.

Instead of using
if (a < b) use if (a < b + epsilon) if (a < b - epsilon) 11 Data Structures & Algorithms Computational Geometry Overview Composite Geometry Objects Pointsets and polygons 13 Composite Geometry Objects 2D and 3D meshes Stored in files: points and segments 14 Application: Solid Modeling CAD 15 Data Structures & Algorithms Points and Lines Intersection of Two Lines (1) Two lines given by their slope-intercept equations y = ax + b and y = cx + d • Check if the slopes are equal (a == c) case: b == d (same line) case: b != d (parallel lines, no intersection) • If slopes are unequal (a != c), find the single intersection point (x0, y0) • y0 = ax0 + b = cx0 + d • x0 = (d – b) / (c – a) • y0 = ax0 + b 17 Intersection of Two Lines (2) Two lines given by pairs of points Same idea as before, but more involved math From Wikipedia: Zero denominators → parallel lines 18 Segment Intersection Test (1) Do two segments intersect? 19 Segment Intersection Test (2) 1. Find two lines formed by the segments 2. If the lines are parallel (same slope) – But distinct (intercepts are ≠), return false – And coincide (equal intercepts), check if the segments’ X and Y projections overlap 3. Else, find the intersection point – Check if it lies inside both segments (by checking this for X and Y coordinates) 20 Collinear Points Q: Do points P1, P2, P3 lie on the same line? A: Check if the lines formed by segments a = [P1, P2] and b = [P2, P3] are the same 1. Find slope-intercept {ka, ca} values from the line segment [P1, P2] 2. Find slope-intercept {kb, cb} values from the line segment [P2, P3] 3. Collinear if ka == kb and ca == cb 21 Distance from Point to a Line • Given a point (x0, y0), find the shortest distance to a line ax + by + c = 0 • Find the coordinates of the point on the line closest to (x0, y0) 22*Source: Wikipedia Min Bounding Box of a Pointset 23 Min Bounding Box of a Pointset • Finding the minimum size BB is easy, IF you stay parallel to x/y axes – For each coordinate, find min and max, O(N) • Usually a smaller BB exists without edges parallel to x/y axes Possible in O(N) time, but non-trivial algorithm 24 Data Structures & Algorithms Points and Lines Closest Pair of Points (1) • Given N points, find two with min distance – Direct O(N2)-time algorithm • In 1D, O(N log N) time via sorting • In 2D, use Divide & Conquer: – Left side – Right side – Middle strip (alternate directions) 26 Closest Pair of Points (2) Partitioning can be done using X-median 1. Recurse on the left half, find min dist 2. Recurse on the right half, find min dist 3. Additionally form a middle strip of width min-dist 4. Sort the strip by Y 5. Compare each pt to 7 points after it 27 Closest Pair of Points (3) Recursion is similar to that in Quick sort, but with two linear terms – for partition and for processing the middle strip O(N log N) time If sorting is used to partition, we get O(N log2 N) time 28 Finding Closest Point from N • Given N points, we’d like to serve the following type of queries – For point P, find a closest point among N pts (“the closest” would be misleading in general) – To go beyond the obvious O(N2)-time solution, build a data structure (a search index) • This problem has many applications in databases, geospatial mapping, Internet systems, computer-aided design etc 29 Data Structures & Algorithms Polygons Clockwise Test & Triangle Area • Given three non-colinear points a, b, c – Determine if they turn counterclockwise (left) or clockwise (right) – Find the area of the triangle they form • Two problems solved by the same formula “signed triangle area” is < 0 for “clockwise” 31 Area of a Polygon • a polygon is given by n points (xi, yi) • no segments are allowed to intersect 32 Area of a Polygon A polygon with 5 points 33 Area of a Polygon Break the polygon into pieces, by drawing vertical lines from each point down to the x-axis. We’re left with nearly- trapezoidal regions. 34 Area of a Trapezoid Area of a trapezoid with right angles: 35 ! = # ℎ! + ℎ"2 Area of a Trapezoid Area of a trapezoid with right angles: 36 1 = (" − (! $# + $" 2 Area of a Polygon Remove the red shape from the green shape to get the yellow shape • Each trapezoid has a top edge in the polygon • Each edge is the top of a trapezoid (red or green) 37 – = =0 +1 -0 =1 -1 Area of a Polygon • Unsigned Area – Green trapezoids have xi < xi+1 ! = #! + #!"# %!"# − %! 2 – Red trapezoids have xi > xi+1

! =
#! + #!”# %! − %!”#

2
• Signed Area

– Green trapezoid have A > 0
– Red trapezoids have A < 0 ! = #! + #!"# %!"# − %! 2 38 – = • For non-convex shapes, the positive/negative regions can overlap. • Some regions are double-counted (+ or -) • It still works! Area of a Polygon 39 – = +2 -2 =0 +1 -0 =1-1 Area of a Polygon • From Wikipedia: the Shoelace formula The points are (x0, y0), (x1, y1), (x2, y2), …, (xn-1, yn-1), with (xn, yn) = (x0, y0) for convenience * will be negative if the points are listed in counterclockwise order • Punchline: computing AreaOf(polygon) in linear time (in the number of points) 40 ! = 1 2 % !"# $%& &!'!'& −% !"# $%& &!'&'! The Shoelace Formula 41 Point Inside a Polygon (1) Given a polygon (defined by N points) and a point P, determine if P is inside the polygon. 42 Point Inside a Polygon (2) Given a polygon (defined by N points) and a point P, determine if P is inside the polygon. 43 Point Inside Polygon (3) Project a horizontal line through the point – Crosses an even number of segments: outside – Crosses an odd number of segments: inside 44*Reminder: all comparisons use epsilon! Point Inside Polygon (4) The special cases when lines cross polygon’s vertices can be handled by “wiggling” the points up/down by epsilon. 45*Reminder: all comparisons use epsilon! Data Structures & Algorithms Polygons Data Structures & Algorithms Additional Topics Computing Min & Max at Once • Computing min of N values takes N - 1 comparisons • Computing max of N values takes N - 1 comparisons • However, both values can be computed using 1 + ceil (3 * (N – 2) / 2) comparisons – For each pair of input values, compare the larger of the two with running max and the smaller of the two with running min 48 k-d (k-dimensional) trees (1) • A binary tree to represent coordinate data • The data structure works in k dimensions, but we will use k=2 for illustration • Construction – Pick one coordinate and partition all points using the chosen value (linear time) – Then recurse to each partition, but use a different coordinate next – Build a tree 49 k-d trees (2) • Each tree node represents a vertical or horizontal cut – One point recorded @node • Construction process takes O(N log N) time • Search takes O(log N) time – Similar to binary search, but alternates dimensions 50 Optional: Convex Hull • Find the smallest polygon enclosing the given pointset • Intuition: if points are nails stuck in a board, then a rubber band stretched around the nails assumes the shape of the convex hull, in O(1) time! • Several algorithms find convex hull of N points in 2D in O(N log N) time – Can be accomplished with a sweeping line 51 Optional: Polygonal Operations • Boolean ops on polygonal shapes: – Union, intersection, set difference • Polygonal shapes can represent mechanical parts in software for solid-modelling CAD – These techniques can be extended to 3D and also to smooth shapes 52 Data Structures & Algorithms Additional Topics Summary • Geometric objects – Basic: points, segments, lines – Compound: pointsets, polygons, meshes • Transforms: shifts, scaling, mirroring, rotation • Geometric tests for points, segments, lines • Efficient geometric algorithms – Closest pair of points, closest-point queries – Area of polygons, point-in-polygon test, etc • Floating-point comparisons must use epsilon 54 Interview Question • Given n points, find a line through two of the given points that divides the remaining points into two halves, in O(n log n) time • Assumptions to make it slightly easier: – There are an even number of points – No three points are collinear • Hint: draw it out! 55