Questions tagged [computational-geometry]

study of algorithms which can be stated in terms of geometry

Filter by
Sorted by
Tagged with
0 votes
0 answers

Land allocation to polygons with specific areas within a boundary

We are looking for a solution to create novel land allocations of an existing area into a subset of polygons for each allocation within the existing space. A high level overview of the requirements ...
mattscooter's user avatar
0 votes
0 answers

Can single 2D LiDAR perform multiple object tracking?

The objective is to track movement of multiple products in a conveyor belt right from the beginning to end of a conveyor belt and monitor the start and end time of the movement of a particular product ...
NitrAl's user avatar
  • 1
1 vote
0 answers

Finding the closest point on a line to a given point (and their distance) efficiently

I am working on a problem that involves some geometry and spatial points. Given a query, consisting of a point p and a line L (point not necessarily on the line), then find the point q on L that is ...
M. Fire's user avatar
  • 31
0 votes
0 answers

Point projection on a polygon along each axis

There is a method in this thread that allows defining a concave outline around a 2D set of points. import alphashape import matplotlib.pyplot as plt from descartes import PolygonPatch points = [(17, ...
Alejandro's user avatar
  • 101
1 vote
0 answers

How to find geographic coordinates of intersection point of two lines originating from two different geographic coordinates?

I have two planes emanating from two different geographic coordinates as per wgs 84 reference ellipsoid namely (lat1, long1, alt1) and (lat2, long2, alt3) with a bearing b1 and b2 with respect to ...
user5349's user avatar
  • 111
0 votes
3 answers

Splitting Streets to Create Polygons?

I have a need to take all the streets belonging to a certain area (in OpenStreetMap) and split each street by each other and form polygons from the segments that result from the split operation. I do ...
c00der's user avatar
  • 231
1 vote
0 answers

Extruding mesh along parametric curve and applying earth curvature?

I'm working on a railway generation project, I must generate 3D meshes for the track (rail, ballast, ...). Track origin is defined geographically (latitude/longitude/azimuth/elevation), then the ...
mat's user avatar
  • 11
1 vote
1 answer

"Average" of two lines

I have a dataset of pairs of parallel linear features (railway tracks) and I need to simplify each pair into its central/median line. This could be achieved by computing a skeleton as suggested in ...
julien's user avatar
  • 10.2k
6 votes
3 answers

Delaunay triangulation algorithm in shapely producing erratic result

I would like to triangulate the following polygon: The wkt for the geometry is given as follows: POLYGON ((3 0, 2 0, 2 0.75, 2.5 0.75, 2.5 0.6, 2.25 0.6, 2.25 0.2, 3 0.2, 3 0)) I ran this code to ...
user32882's user avatar
  • 3,494
1 vote
0 answers

Points on the opposing side of a breakline

If you have a breakline or even a single line segment within a DEM, how can you tell if two points lie on the opposing side of that breakline or line segment? From a computational geometry standpoint ...
afrancio's user avatar
  • 131
2 votes
0 answers

Pattern recognition - machine recognition of plausible shape of a polygon

I have a schoolproject where the task is to locate all possible shapes (of a certain complex polygonic structure) in a layer of several heterogenous polygons. And now the task is to find all the ...
MichaelR's user avatar
  • 542
1 vote
0 answers

Closest Point Pairs to determine grid resolution

I'm reading Hengl's (2006) Finding the Right Pixel Size. In it, among many different suggested approaches, he suggests using a grid resolution where > 95% of the closest point pairs do no fall into ...
JKiss's user avatar
  • 11
2 votes
0 answers

Is there an established method to declare "Forward" on a linear feature

Is there an accepted way to establish a Forward direction for a linear feature regardless of the ordering of the points used to store the feature? An example would come from Roadway Design in the ...
philologon's user avatar
1 vote
0 answers

Is this Fastest, most Elegant and Extendable to nD implementation of AABB Intersection?

I recently did an AABB (Axes Aligned Bounding Box) Intersection implementation on 2D and 3D objects for which I came up with such a short (and very fast) solution as follows. The demonstration below ...
Developer's user avatar
  • 3,387
3 votes
1 answer

What algorithm allows me to calculate the set of all points inside a polygon?

Imagine I have a polygon, which represents the countours of a building on an integer 3D map (everything is a 1 meter by 1 meter block in that map). In the image below, you see several buildings ...
Glory to Russia's user avatar
6 votes
1 answer

Travel planning - Finding farthest points of a polygon

I’d like to organize a tour around the lake with 2 objectives: maximise the length of shores to view minimise travel distance In order to do so I can: Pick 2 most remote points on the lake in ...
FelixIP's user avatar
  • 22.6k
12 votes
2 answers

How to compute Straight Skeletons using Python?

Is there a Python package which provides an implementation of a Straight Skeleton algorithm? I'm aware that the open source (C++) project CGALcontains an implementation but it seems like cgal-...
underdark's user avatar
  • 83.8k