Computational Geometry in C

Joseph O'Rourke

Mentioned 4

This is the newly revised and expanded edition of the popular introduction to the design and implementation of geometry algorithms arising in areas such as computer graphics, robotics, and engineering design. The second edition contains material on several new topics, such as randomized algorithms for polygon triangulation, planar point location, 3D convex hull construction, intersection algorithms for ray-segment and ray-triangle, and point-in-polyhedron. A new "Sources" chapter points to supplemental literature for readers needing more information on any topic. A novel aspect is the inclusion of working C code for many of the algorithms, with discussion of practical implementation issues. The self-contained treatment presumes only an elementary knowledge of mathematics, but reaches topics on the frontier of current research, making it a useful reference for practitioners at all levels. The code in this new edition is significantly improved from the first edition, and four new routines are included. Java versions for this new edition are also available. All code is accessible from the book's Web site (http://cs.smith.edu/~orourke/) or by anonymous ftp.

More on Amazon.com

Mentioned in questions and answers.

How can I check if 2 segments intersect?

I've the following data:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

I need to write a small algorithm in python to detect if the 2 lines are intersecting.

Update:
alt text

You don't have to compute exactly where does the segments intersect, but only understand whether they intersect at all. This will simplify the solution.

The idea is to treat one segment as the "anchor" and separate the second segment into 2 points.
Now, you will have to find the relative position of each point to the "anchored" segment (OnLeft, OnRight or Collinear).
After doing so for both points, check that one of the points is OnLeft and the other is OnRight (or perhaps include Collinear position, if you wish to include improper intersections as well).

You must then repeat the process with the roles of anchor and separated segments.

An intersection exists if, and only if, one of the points is OnLeft and the other is OnRight. See this link for a more detailed explanation with example images for each possible case.

Implementing such method will be much easier than actually implementing a method that finds the intersection point (given the many corner cases which you will have to handle as well).

Update

The following functions should illustrate the idea (source: Computational Geometry in C).
Remark: This sample assumes the usage of integers. If you're using some floating-point representation instead (which could obviously complicate things), then you should determine some epsilon value to indicate "equality" (mostly for the IsCollinear evaluation).

// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
     return Area2(a, b, c) > 0;
}

bool IsOnRight(Point a, Point b, Point c)
{
     return Area2(a, b, c) < 0;
}

bool IsCollinear(Point a, Point b, Point c)
{
     return Area2(a, b, c) == 0;
}

// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
     return (b.X - a.X) * (c.Y - a.Y) -
            (c.X - a.X) * (b.Y - a.Y);
}

Of course, when using these function, one must remember to check that each segment lays "between" the other segment (since these are finite segments, and not infinite lines).

Also, using these function you can understand whether you've got a proper or improper intersection.

  • Proper: There are no collinear points. The segments crosses each other "from side to side".
  • Improper: One segment only "touches" the other (at least one of the points is collinear to the anchored segment).

Is there a trivial, or at least moderately straight-forward way to generate territory maps (e.g. Risk)?

I have looked in the past and the best I could find were vague references to Voronoi diagrams. An example of a Voronoi diagram is this:

here.

These hold promise, but I guess i haven't seen any straight-forward ways of rendering these, let alone holding them in some form of data structure to treat each territory as an object.

Another approach that holds promise is flood fill, but again I'm unsure on the best way to start with this approach.

Any advice would be much appreciated.

The best reference I've seen on them is Computational Geometry: Algorithms and Applications, which covers Voronoi diagrams, Delaunay triangulations (similar to Voronoi diagrams and each can be converted into the other), and other similar data structures.

They talk about all the data structures you need but they don't give you the code necessary to implement it (which may be a good exercise). In terms of code, an Amazon search shows the book Computational Geometry in C, which presumably comes with the code (although since you're stuck in C, you'd mind as well get the other one and implement it in whatever language you want). I also don't have any experience with this book, only the first.

Sorry to have only books to recommend! The only decent online resource I've seen on them are the two Wikipedia articles, which doesn't really tell you implementation details. This link may be helpful though.

I have a 3D shape in a 3D binary image. Therefore, I have a list of all of the x,y,z points.

If I am to analyze a shape for various identification, such as "sphericity", "spiky"-ness, volume, surface area, etc., what are some of the choices do I have here?

Could you post a sample shape? Do you have a complete set of points on the surface and interior of the shape? Are the points evenly spaced? Is this synthetic data, or perhaps a point cloud from a 3D scan?

A few ideas:

  1. Calculate the 3D convex hull of the points. This will give you the outer "envelope" of the points and is useful for comparison with other measurements. For example, you can compare the surface area of the convex hull to the surface area of the outer surface points.
  2. Find the difference between "on" voxels in the convex hull and "on" voxels in the raw point set. You can then determine how many points are different, whether there is one big clump, etc. If the original shape is a doughnut, the convex hull will be a disk, and the difference will be the shape of the hole.
  3. To calculate spikiness, you can think of comparing the Euclidean distance between two points (the "straight line" distance) and the shortest distance on the outer surface between those two points.
  4. Compare the surface area of the raw data to the surface area after a 3D morphological "close" operation or some other smoothing operation.
  5. To suggest a type of volume calculation, we'd need to know more about the point set.
  6. Consider the Art Gallery Problem to 3D. Are there points on the surface not visible to certain points in the interior? Is the shape convex or star convex?

A good reference for geometric algorithms is Geometric Tools for Computer Graphics by Schneider and Eberly. It's pricey new, but you can probably find a cheap used copy in good condition at addall.com. I suspect you'll find all the answers you want and more in that book. http://www.amazon.com/Geometric-Computer-Graphics-Morgan-Kaufmann/dp/1558605940

One of the authors maintains a site on the same subject: http://www.geometrictools.com/

Another good textbook is Computational Geometry in C by Joseph O'Rourke. http://www.amazon.com/Computational-Geometry-Cambridge-Theoretical-Computer/dp/0521649765/ref=sr_1_1?s=books&ie=UTF8&qid=1328939654&sr=1-1

How to generate buffer around lines or any type of geometric shapes?
Not interested in available packages such as Shapely etc but wish to implement. enter image description here

Mathematically, this operation is a Minkowski sum. You should find a reference and some pseudo-code in a good book on compuational geometry. Try Computational Geometry in C by O'Rourke, or Computational Geometry: Algorithms and Applications by Berg et al.