Questions tagged [computational-geometry]

study of algorithms which can be stated in terms of geometry

17 questions
Filter by
Sorted by
Tagged with
50 views

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 ...
29 views

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 ...
1 vote
96 views

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 ...
• 31
363 views

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, ...
• 101
1 vote
1k views

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 ...
• 111
403 views

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 ...
• 231
1 vote
45 views

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 ...
• 11
1 vote
551 views

"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 ...
• 10.2k
7k views

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 ...
• 3,494
1 vote
24 views

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 ...
• 131
600 views

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 ...
• 542
1 vote
90 views

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 ...
• 11
46 views

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 ...
• 178
1 vote
280 views

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 ...
• 3,387
4k views

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 ...
• 1,047
674 views

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 ...
• 22.6k