## How to find largest triangle in convex hull aside from brute force search

Yes, you can do significantly better than brute-force. By brute-force I assume you mean checking all triples of points, and picking the one with maximum area. This runs in O(n3) time, but it turns out that it is possible to do it in not just O(n2) but in O(n) time! [Update: A paper published in … Read more

## get closest point to a line

Here’s Ruby disguised as Pseudo-Code, assuming Point objects each have a x and y field. def GetClosestPoint(A, B, P) a_to_p = [P.x – A.x, P.y – A.y] # Storing vector A->P a_to_b = [B.x – A.x, B.y – A.y] # Storing vector A->B atb2 = a_to_b**2 + a_to_b**2 # **2 means “squared” # Basically finding … Read more

## How to calculate the area of a polygon on the earth’s surface using python?

Let’s say you have a representation of the state of Colorado in GeoJSON format {“type”: “Polygon”, “coordinates”: [[ [-102.05, 41.0], [-102.05, 37.0], [-109.05, 37.0], [-109.05, 41.0] ]]} All coordinates are longitude, latitude. You can use pyproj to project the coordinates and Shapely to find the area of any projected polygon: co = {“type”: “Polygon”, “coordinates”: … Read more

## How to rotate a vertex around a certain point?

The easiest approach is to compose three transformations: A translation that brings point 1 to the origin Rotation around the origin by the required angle A translation that brings point 1 back to its original position When you work this all out, you end up with the following transformation (where x is the desired angle … Read more

## How to find two most distant points?

For this specific problem, with just a list of Euclidean points, one way is to find the convex hull of the set of points. The two distant points can then be found by traversing the hull once with the rotating calipers method. Here is an O(N log N) implementation: http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/ If the list of points … Read more

## How to make a circular UIView

I can at least show you a shortcut for drawing circles of arbitrary size. No OpenGL, no Core Graphics drawing needed. Import the QuartzCore framework to get access to the .cornerRadius property of your UIView or UIImageView. #import <QuartzCore/QuartzCore.h> Also manually add it to your project’s Frameworks folder. Add this method to your view controller … Read more

## How do I reverse-project 2D points into 3D?

[*] Alright, I came here looking for an answer and didn’t find something simple and straightforward, so I went ahead and did the dumb but effective (and relatively simple) thing: Monte Carlo optimisation. Very simply put, the algorithm is as follows: Randomly perturb your projection matrix until it projects your known 3D coordinates to your … Read more

Categories 3d

## How to determine if a point is inside a 2D convex polygon?

This page: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html shows how to do this for any polygon. I have a Java implementation of this, but it is too big to post here in its entirety. However, you should be able to work it out: class Boundary { private final Point[] points; // Points making up the boundary … /** * Return … Read more

## How to tell whether a point is to the right or left side of a line

Try this code which makes use of a cross product: public bool isLeft(Point a, Point b, Point c){ return ((b.X – a.X)*(c.Y – a.Y) – (b.Y – a.Y)*(c.X – a.X)) > 0; } Where a = line point 1; b = line point 2; c = point to check against. If the formula is equal … Read more

## Calculating the position of points in a circle

Given a radius length r and an angle t in radians and a circle’s center (h,k), you can calculate the coordinates of a point on the circumference as follows (this is pseudo-code, you’ll have to adapt it to your language): float x = r*cos(t) + h; float y = r*sin(t) + k;