Transcript Programming Interest Group

Programming Interest Group
http://www.comp.hkbu.edu.hk/~chxw/pig/index.htm
Tutorial Eight
Computational Geometry
1
Introduction


Computational geometry is the branch of computer
science that studies algorithms for solving geometric
problems.
Applications



Computer graphics, robotics, VLSI design, computer-aided
design, etc.
Two dimensions, three dimensions, etc.
Common objects in two dimensions

point, line, line segment, vertices, polygon, circle, etc.
2
Points

A point is defined by its two coordinates in the
plane
typedef struct {
y
double x;
double y;
p(a,b)
b
0
a
} point;
x
3
Distance

What’s the distance between two given
points?
d  ( x1  x2 )  ( y1  y2 )
2
2
double distance(point p1, point p2) {
double dx, dy;
dx = p1.x – p2.x;
dy = p1.y – p2.y;
return sqrt(dx*dx + dy*dy);
}
4
Lines


Consider lines in the plane
Two possible representations


By equations such as y = ax + b where a is the
slope of the line and b is the y-intercept.
by any pair of points (x1, y1) and (x2, y2) which lie
on the line


Then the slope will be (y1-y2)/(x1-x2)
We use the formula ax + by + c = 0 to
represent a line
5
Lines
typedef struct {
double a;
/* x-coefficient */
double b;
/* y-coefficient */
double c;
/* constant term */
} line;
If the y-coefficient is 0, set the x-coefficient to 1;
Otherwise, set the y-coefficient to 1.
6
Lines

Given two points p1, p2, determine the line
points_to_line(point p1, point p2, line *m) {
if (p1.x == p2.x) {
m->a = 1;
m->b = 0;
m->c = -p1.x;
} else {
m->b = 1;
m->a = -(p1.y – p2.y) / (p1.x – p2.x);
m->c = -(m->a * p1.x) – (m->b * p1.y);
}
}
Should be (fabs(p1.x-p2.x) <= EPSILON), where EPSILON is a very small
positive number like 0.00000000001
7
Lines

Given a point and the slope, determine the
line
point_and_slope_to_line(point p, double s, line *m) {
m->a = -s;
m->b = 1;
m->c = -( (l->a * p.x) + (l->b * p.y) );
}
8
Line Intersection

Two distinct lines have one intersection point
unless they are parallel
int parallelQ(line m1, line m2) {
return ( (fabs(m1.a - m2.a) <= EPSILON ) &&
(fabs(m1.b – m2.b) <= EPSILON) );
}
int same_lineQ(line m1, line m2) {
return ( parallelQ(m1, m2) &&
(fabs(m1.c – m2.c) <= EPSILON) );
}
9
Line Intersection
intersection_point(line m1, line m2, point *p) {
if (same_lineQ(m1, m2)) {
printf(“Warning: identical lines.\n”);
p->x = p->y = 0.0;
}
if (parallelQ(m1, m2)) {
printf(“Error: Distinct parallel lines do not intersect.\n”);
return ;
}
p->x = (m2.b * m1.c – m1.b * m2.c) / (m2.a * m1.b – m1.a * m2.b);
if (fabs(m1.b) > EPSILON)
/* test for vertical line */
p->y = - (m1.a * p->x + m1.c ) / m1.b;
else
p->y = - (m2.a * p->x + m2.c ) / m2.b;
}
10
Closest Point

Identify the point on line m which is closest to
a given point p
closest_point(point p_in, line m, point *p_c) {
line perp;
/* perpendicular to m
if (fabs(m.b) <= EPSILON) {
/* vertical line */
p_c->x = -m.c;
p_c->y = p_in.y;
return;
}
if (fabs(m.a) <= EPSILON) {
/* horizontal line */
p_c->x = p_in.x;
p_c->y = -m.c;
return;
}
point_and_slope_to_line(p_in, 1/m.a, &perp);
intersection_point(m, perp, p_c);
}
11
Line Segments

A line segment is the portion of a line which
lines between two given points inclusive.
typedef struct {
point p1, p2; /* endpoints of line segment */
} segment;
12
Line Segment Intersections

To test whether two segments intersect

It’s complicated due to tricky special cases
int segment_intersect(segment s1, segment s2) {
line m1, m2;
point p;
/* intersection point */
points_to_line(s1.p1, s1.p2, &m1);
points_to_line(s2.p1, s2.p2, &m2);
if (same_lineQ(m1, m2) )
/* overlapping or disjoint segments */
return ( point_in_box(s1.p1, s2.p1, s2.p2) || point_in_box(s1.p2, s2.p1, s2.p2)
|| point_in_box(s2.p1, s1.p1, s1.p2) || point_in_box(s2.p2, s1.p1, s1.p2) );
if ( parallelQ(m1, m2) )
return 0;
intersection_point(m1, m2, &p);
return (point_in_box(p, s1.p1, s1.p2) && point_in_box(p, s2.p1, s2.p2) );
}
13
Line Segment Intersections

Whether a point lies in a box?
#define max(A, B)
#define min(A, B)
((A) > (B) ? (A) : (B))
((A) < (B) ? (A) : (B))
int point_in_box (point p, point b1, point b2) {
return ( (p.x >= min(b1.x, b2.x)) && (p.x <= max(b1.x, b2.x))
&& (p.y >= min(b1.y, b2.y)) && (p.y <= max(b1.y, b2.y)) );
}
14
Triangles and Trigonometry



Angle is the union of two rays sharing a
common endpoint.
Trigonometry is the branch of mathematics
dealing with angles and their measurement.
Two measures of angles



Radians: from 0 to 2π
Degree: from 0 to 360
Right angle: 90o or π/2 radians
15
Triangles and Trigonometry


Right triangle contains a right internal angle.
Pythagorean theorem:


|a|2 + |b|2 = |c|2
a and b are the two shorter sides, c is the longest
side, or hypotenuse.
c
a
b
16
Triangles and Trigonometry

Two important trigonometric formulae


Law of Sines:
a
b
c


sin A sin B sin C
Law of Cosines:
a  b  c  2bc cos A
2
C
b
2
2
a
A
c
B
17
Area of a Triangle

The signed area of a triangle can be
calculated directly from its coordinate
representation

A(T) = (axby – aybx + aycx – axcy + bxcy – cxby)/2
double signed_triangle_area (point a, point b, point c) {
return ( (a.x*b.y – a.y*b.x + a.y*c.x – a.x*c.y + b.x*c.y – c.x*b.y) / 2.0 );
}
double triangle_area (point a, point b, point c) {
return fabs(signed_triangle_area(a,b,c));
}
18
Circles


A circle is defined as the set of points at a
given distance (or radius) from its center (xc,
yc).
A disk is circle plus its interior.
typedef struct {
point c;
/* center of circle */
double r;
/* radius of circle */
} point;
19
Polygons


Polygons are closed chains of nonintersecting line segments.
We can represent a polygon by listing its n
vertices in order around the boundary of the
polygon.
typedef struct {
int n;
/* number of points in polygon */
point p[MAXPOLY]; /* array of points */
} polygon;
20