Medial Axis

Medial Axis

We’ll have a mini-lecture at the beginning of class explaining vector arithmetic.

Starter Code

The code contains a DCEL implementation tailored for use in the medial axis computation. A few important operations are:

  • DCEL.HalfEdge.contract(): Contracts an edge by merging it into a single vertex.
  • DCEL.HalfEdge.angle(): Returns the interior angle measure of the origin of this half-edge.
  • DCEL.HalfEdge.length(): Returns the length of this half-edge.
  • DCEL.Face.isDegenerate(): Returns true if a face is incident to exactly two half-edges (i.e. is just not really a face, but a line segment).
  • DCEL.Face.removeDegenerate(): This operation “cleans up” the DCEL by replacing the degenerate face with just an edge (i.e. two half-edges). It returns one of the resulting half-edges.
  • DCEL.Face.offset(double t): Offsets a polygon by moving its points inwards along the angle bisector to a height above the edges of t. This code works topologically, but will not work correctly geometrically until you complete the lab. Note that the current face record is reused as the interior of the offset face. Thus if you offset on faces.get(1), the offset version of that face is now faces.get(1).

Vectors

  • We will do a mini-lecture, at which point you will play with this model.

Your Task

Complete the following functions. Note that you may assume any face of the DCEL is a convex polygon.

  • DCEL.HalfEdge.bisector(): Returns a vector in the direction of the interior angle bisector of this half-edge’s origin.
  • DCEL.HalfEdge.pointAlongBisectorAtHeight(double t): Returns the point p along the bisector ray that is inset to a height of t above the half-edge.
  • DCEL.HalfEdge.contractionheight(): Returns the contraction height for this edge (i.e. at what height do the bisectors at the origin and destination of this half-edge intersect? See the rayIntersection function in the Vector3d tab.)
  • DCEL.Face.calcContractionHeight(): find the minimum contraction height over all edges incident to a given face.
  • DCEL.Face.shortestHalfEdge(): find the minimum half-edge incident to a given face.
  • Algorithms/computeMedialAxis: compute the medial axis.

Turning it in

Turn it in on Canvas by next Monday 11:55pm.