Hi, I'm looking for a simple (if exists) algorithm to find the Voronoi diagram for a set of points on the surface of a sphere. Source code would be great. I'm a Delphi man (yes, I know...), but I eat C-code too. TIA Steven ...
I am writing a program that requires a implementation of Medial Axis extraction, of which Delaunay triangulation is a step. External medial axis is unwanted so the corresponding external triangles are intended to be removed. Luckily I came upon a page with a lot of diagrams, also a hint of a method to determine internal and external Dela...
I've been tasked to figure out how to find the centerline of a polygon. My google searches led me to believe that what I need is called the 'Medial Axis'. Like this: According to what I've read, what I need can be produced by using a 2D Voronoi diagram construction algorithm for segments. I've found a C# version of the Voronoi algo...
UPDATE: the math term for what I'm looking for is actually inward/outward polygon offseting. +1 to balint for pointing this out. The alternative naming is polygon buffering. Before I start developing my own solution from scratch, does anyone know of any good source for an algorithm that can inflate a polygon, something similar to this: ...
I've got some convex polygons stored as an stl vector of points (more or less). I want to tessellate them really quickly. The pieces don't have to be perfectly evenly sized, but they should still be bits and pieces... and preferably no slivers -- I'm just going to use it to explode some objects into little pieces. Does anyone know of a n...
Given a set of points on a plane, find the shortest line segment formed by any two of these points. How can I do that? The trivial way is obviously to calculate each distance, but I need another algorithm to compare. ...
Hi, I wanted to create TINs from 3D points (about 7 million in every file) using qhull. can anyone suggest a place where i could probably see how to do this? thanks! ...
I'm trying to implement a geometry templating engine. One of the parts is taking a prototypical polygonal mesh and aligning an instantiation with some points in the larger object. So, the problem is this: given 3d point positions for some (perhaps all) of the verts in a polygonal mesh, find a scaled rotation that minimizes the differen...
Hi, I'm stuck with this little problem and my algorithm to solve this doesn't hold for all cases. Does anybody has an idea how to solve this? Here's an example polygon: Formal description We have a list of points in CW order defining the polygon. We also can query whether a point is a cutting point with is_cut(p), where p is a giv...
Hi All, How can I draw a perpendicular on a line segment from a given point? My line segment is defined as (x1, y1), (x2, y2), If I draw a perpendicular from a point (x3,y3) and it meets to line on point (x4,y4). I want to find out this (x4,y4). Thankx. ...
I can't find any code for doing this. The only places I can find it is in GIS APIs. Preferably in java, but I can port other languages too. I'd even settle for a overview of all the formulas required. ...
I am trying to use CGAL to do some Delaunay triangulation. I used one of the CGAL samples to compute a triangulation which includes a height field attribute. The problem I have having is that I have no idea how to get the resulting triangulation. I figured out how to get the face_iterator, but I don't know what to do from there. What...
Hello, I want to find when a collision between a static and a moving ball occurs, but the algorithm I came up with, sometimes doesn't detect a collision and the moving ball goes through the static one. The moving ball is affected by gravity and the static one is not. Here's my collision detection code: GLfloat whenSpheresCollide(const...
hello, does anyone know an open source c# dll for Computational Geometry. ...
How does: (1 + 2 + ... + N) / N = (N + 1) / 2 or (1 + 2 + ... + N + N) / N = (N + 3) / 2 My textbook says this is elementary math but I have forgotten the method for finding the answer. ...
Here is some code: struct K : CGAL::Exact_predicates_inexact_constructions_kernel {}; typedef CGAL::Triangulation_vertex_base_2<K> Vb; typedef CGAL::Constrained_triangulation_face_base_2<K> Fb; typedef CGAL::Triangulation_data_structure_2<Vb,Fb> TDS; typedef CGAL::Exact_predicates_tag It...
I would like an algorithm to calculate the convex hull of 4 2D points. I have looked at the algorithms for the generalized problem, but I wonder if there is a simple solution for 4 points. I've been scratching around on paper trying to figure out an algorithm but am having no luck at the moment. Thanks. ...
this is little hard one. i have latitude and longitude and i want to pull the record from the database, which has nearest latitude and longitude by the distance, if that distance gets longer then specified one, then don't retrieve it. Table structure: id latitude longitude place name city country state zip sealevel ...
How can I attach data to a gpc_vertex instance? I am planning to attach vertex indices to the gpc_vertex itself in order to build a Direct3D IndexBuffer later on... ...
I am using GPC to break up polygons into triangles. However, GPC is very obviously creating additional vertices while generating triangles. Is there a way to avoid this? ...