Algorithms – Determine if a Line Segment is an External Edge of Delaunay Triangulation

algorithmsgeometry

I've created a Delauney triangulation of a set of points. Now I want to iterate over the triangulation and remove any line segments/edges on the exterior for which the following are true:

The outside edge is the hypotenuse of the triangle
Call the hypotenuse the "base" and determine the "height" of the triangle. Then if base/height > x (where x is some criteria value, say 4), delete that edge/triangle (depending on data structure/object definitions).

In essence I'm trying to remove edges from the triangulation to create a more characteristic shape by deleting edges that are long, skinny, and on the outside of the triangulation. I might add in a check later for size of the triangle relative to the average of the rest, too.

My question is: is there an easy way to check if a given edge is on the exterior of the triangulation?

I figured I could build in to the triangulation process itself a design that will make every line segment its own object, then have each line segment "know" its neighboring polygons, and if it has an empty neighbor slot then it is external. This seemed inefficient, though, and the code I currently have just spits out a bunch of triangle objects with its vertices's indexes stored. Calculating the line segments shouldn't be too bad, but then I only want to do the deletion process on external edges as opposed to all of them.

Not sure if this question belonged in math or programming, apologies if it should not be in here or if I provided too little/too much information.

I'm working in Python, but my concern here is about theoretical approach/algorithm as opposed to code so I don't feel it necessary to include code.

EDIT to note: I'll want to iterate over the exterior multiple times in the event that after deleting one exterior triangle the first round through it reveals a new exterior that fits the deletion parameters. Therefore I'd like to avoid completely recalculating the exterior edges each time — thus the question about a quick-and-easy, if it exists.

Best Answer

A triangulation of your point set gives you for each point a list of "adjacent" points, the neighbours to which a point is connected.

Once you have calculated the triangulation, you can determine the outer edges by applying an algorithm similar to the classic gift-wrapping algorithm for convex hulls. You start with, for example, the "rightmost" point (which is part of the convex hull and so at the outer edge). Then step from point to point using only outer edges of the triangulation. The only difference to the "convex hull" algorithm is, when having points p_(n-1) and p_(n), you choose p_(n+1) as the point among all adjacent points minimizing the angle between p_(n)->p_(n-1) and p_(n) ->p_(n+1).

Hope this helps.

example for going from p_n to p_(n+1)

Related Solutions

Algorithms – How to Create an Algorithm for Determining Boolean Tautologies

The problem to detect a tautology is equivalent to the boolean satisfiability problem which is sadly np-complete for general instances. You can easily convert tautology detection into SAT problem by negating the boolean equation and check its satisfiability , if the negated equation is unsatisfiable then the original equation must be a tautology.

What you can do :-

Use lex & yacc parser tools to generate a grammer to parse a equation.

Evaluate the negation of the equation using de-morgan's law.

Give the negated eqaution to a standard SAT solvers.

Note: If your equation is reducible to 2-SAT then there is linear time algorithm .

Efficient method for finding closest point to a line segment from a set of points including line segment’s vertices

You're going to have to loop through all the points and calculate the distance. There is a great question on StackOverflow about how to calculate the distance: Shortest distance between a point and a line segment

Some of the work can be precalculated, given that you have to do this more than once for a given line segment. You also don't need to figure out the smallest distance, only the smallest distance squared (since squaring is strictly increasing). I converted the top voted answer in that question to a Java version that does this precalculation (in the constructor), and is easier to read and follow. Unfortunately I don't know Python well enough to give you Python code, but you should be able to figure it out.

import java.util.Arrays;
import java.util.List;

public class LineSegment {
    public static class Point {
        public final double x;
        public final double y;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return "(" + x + "," + y + ")";
        }
    }

    public static void main(String[] args) {
        LineSegment segment = new LineSegment(new Point(0, 3), new Point(2, 0));
        List<Point> pointList =
                Arrays.asList(new Point[] { new Point(-5, 3), new Point(1, 1),
                        new Point(2, 3), new Point(0, 5) });

        Point answer = segment.closestPoint(pointList);
        System.out.println("The closest point is: " + answer);
    }

    private static double sqr(double x) {
        return x * x;
    }

    private static double distanceSquared(Point v, Point w) {
        return sqr(v.x - w.x) + sqr(v.y - w.y);
    }

    private final Point firstSegPoint;
    private final Point secondSegPoint;
    private final double segmentDistance;
    private double xDifference;
    private double yDifference;

    public LineSegment(Point firstSegPoint, Point secondSegPoint) {
        this.firstSegPoint = firstSegPoint;
        this.secondSegPoint = secondSegPoint;
        this.segmentDistance = distanceSquared(firstSegPoint, secondSegPoint);
        this.xDifference = secondSegPoint.x - firstSegPoint.x;
        this.yDifference = secondSegPoint.y - firstSegPoint.y;
    }

    public Point closestPoint(List<Point> pointList) {
        double minDistance = Double.POSITIVE_INFINITY;
        Point answer = null;

        for (Point point : pointList) {
            double distSquared = distToSegmentSquared(point);
            if (distSquared < minDistance) {
                answer = point;
                minDistance = distSquared;
            }
        }

        return answer;
    }

    private double distToSegmentSquared(Point input) {
        if (segmentDistance == 0)
            return distanceSquared(input, firstSegPoint);

        double xComponent = (input.x - firstSegPoint.x) * xDifference;
        double yComponent = (input.y - firstSegPoint.y) * yDifference;
        double t = (xComponent + yComponent) / segmentDistance;
        if (closestPointIsFirst(t))
            return distanceSquared(input, firstSegPoint);
        if (closestPointIsSecond(t))
            return distanceSquared(input, secondSegPoint);
        Point closestPointOnLine =
                new Point(firstSegPoint.x + t * xDifference, firstSegPoint.y
                        + t * yDifference);
        return distanceSquared(input, closestPointOnLine);
    }

    private boolean closestPointIsFirst(double t) {
        return t < 0;
    }

    private boolean closestPointIsSecond(double t) {
        return t > 1;
    }
}

See the full implementation here: http://ideone.com/fBFwda

Best Answer

Related Solutions

Algorithms – How to Create an Algorithm for Determining Boolean Tautologies

Efficient method for finding closest point to a line segment from a set of points including line segment’s vertices

Related Topic