## Boundary enclosing a given set of points

Here is some Python code that computes the alpha-shape (concave hull) and keeps only the outer boundary. This is probably what matlab’s boundary does inside. from scipy.spatial import Delaunay import numpy as np def alpha_shape(points, alpha, only_outer=True): “”” Compute the alpha shape (concave hull) of a set of points. :param points: np.array of shape (n,2) … Read more

## Area of rectangle-rectangle intersection

Since you stated that the rectangles may not be aligned, possible answers may be nothing, a point, a line segment, or a polygon with 3-8 sides. The usual way to do this 2d boolean operation is to choose a counterclockwise ordering of the edges, and then evaluate edge segments between critical points (intersections or corners). … Read more

Categories c++

## Perpendicular on a line from a given point

I solved the equations for you: k = ((y2-y1) * (x3-x1) – (x2-x1) * (y3-y1)) / ((y2-y1)^2 + (x2-x1)^2) x4 = x3 – k * (y2-y1) y4 = y3 + k * (x2-x1) Where ^2 means squared

## Find if a point is inside a convex hull for a set of points without computing the hull itself

The problem can be solved by finding a feasible point of a Linear Program. If you’re interested in the full details, as opposed to just plugging an LP into an existing solver, I’d recommend reading Chapter 11.4 in Boyd and Vandenberghe’s excellent book on convex optimization. Set A = (X[1] X[2] … X[n]), that is, … Read more

## Location of highest density on a sphere

There is in fact no real reason to partition the sphere into a regular non-overlapping mesh, try this: partition your sphere into semi-overlapping circles see here for generating uniformly distributed points (your circle centers) Dispersing n points uniformly on a sphere you can identify the points in each circle very fast by a simple dot … Read more

Categories r

## What is the fastest way to find the closest point to a given point?

You may organize your points in an Octree. Then you only need to search a small subset. A Octree is a fairly simple data structure you can implement yourself (which would be a valuable learning experience), or you may find some helpful libraries to get you going.

## robust algorithm for surface reconstruction from 3D point cloud?

I have been facing this dilemma for some months now, and made exhaustive research. Algorithms Mainly there are 2 categories of algorithms: computation geometry, and implicit surfaces. Computation Geometry They fit the mesh on the existing points. Probably the most famous algorithm of this group is powercrust, because it is theoretically well-established – it guarantees … Read more

## Catmull-Rom interpolation on SVG Paths

To answer your questions directly: Yes. Catmull-Rom spline is an algorithm to interpolate a series of (x, y, z) points. It will generate a cubic polynomial curve between each two consecutive points. You cannot direcly use Catmull Rom spline for SVG path. You need to convert it to cubic Bezier curve first. For a curve … Read more

Categories svg

## Shortest distance between points algorithm

http://en.wikipedia.org/wiki/Closest_pair_of_points The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows: Sort points along the x-coordinate Split the set of points into two equal-sized subsets by a vertical line x = xmid Solve the problem recursively in the left and right subsets. This will give … Read more