System and method for determining alpha values for alpha shapes

Patent metadata

Field	Value
Publication number	US-11087534-B2
Application number	US-201916723535-A
Country	US
Kind code	B2
Filing date	Dec 20, 2019
Priority date	Apr 3, 2018
Publication date	Aug 10, 2021
Grant date	Aug 10, 2021

Abstract

Some embodiments provide a non-transitory machine-readable medium that stores a program. The program receives, from a client device, a percentage value for a set of points. The program further determines a triangulation based on the set of points. The program also determines an alpha value based on the triangulation and the percentage value. The program further determines an alpha shape based on the alpha value. The program also provides the client device the alpha shape.

First claim

What is claimed is:

1. A non-transitory machine-readable medium storing a program executable by at least one processing unit of a device, the program comprising sets of instructions for:
receiving, from a client device, a request for an alpha shape formed from a set of points;
determining a triangulation based on the set of points;
determining an alpha value based on the triangulation and a percentage value by determining a list of triangles comprising each triangle in the triangulation, determining an area for each triangle in the list of triangles, determining a circumcircle for each triangle in the list of triangles, determining a radius of the circumcircle for each triangle in the list of triangles, and sorting the list of triangles from shortest radius to longest radius;
determining an alpha shape based on the alpha value; and
providing the client device the alpha shape.

2. The non-transitory machine-readable medium of claim 1 , wherein determining the alpha value further comprises:
determining a total area of the triangles in the list of triangles;
calculating a value based on the percentage value and the total area; and
determining the alpha value by iterating through the list of triangles from shortest radius to longest radius; while iterating through the list of triangles, adding the area of each triangle to an aggregate area value until the aggregate area value is greater than or equal to the value; and selecting the radius of the last triangle whose area is added to the aggregate area value as the alpha value.

3. The non-transitory machine-readable medium of claim 1 , wherein determining the alpha shape based on the alpha value comprises:
generating a circle having a radius equal to the alpha value; and
iterating through each pair of points in the set of points to identify a set of edges configured to define the alpha shape by including in the set of edges each edge formed by a pair of points in the set of points where the circle can be positioned to touch the pair of points without the circle enclosing any other points in the set of points.

4. The non-transitory machine-readable medium of claim 1 , wherein the alpha shape is a first alpha shape, wherein the set of points is a first set of points, and wherein the program further comprises sets of instructions for:
determining a second alpha shape based on a second alpha value, the second alpha value determined based on a second triangulation based on a second set of points and the percentage value, the second set of points being a scaled version of the first set of points, the second alpha shape and the first alpha shape having a same shape.

5. The non-transitory machine-readable medium of claim 1 , wherein the alpha shape is usable for rendering a polygon defined by a subset of the set of points.

6. The non-transitory machine-readable medium of claim 1 , wherein the request from the client device includes the percentage value.

7. The non-transitory machine-readable medium of claim 1 , wherein the percentage value is determined based on a number of points in the set of points.

8. For a device, a method comprising:
receiving, from a client device, a request for an alpha shape formed from a set of points;
determining a triangulation based on the set of points;
determining an alpha value based on the triangulation and a percentage value by determining a list of triangles comprising each triangle in the triangulation, determining an area for each triangle in the list of triangles, determining a circumcircle for each triangle in the list of triangles, determining a radius of the circumcircle for each triangle in the list of triangles, and sorting the list of triangles from shortest radius to longest radius;
determining an alpha shape based on the alpha value; and
providing the client device the alpha shape.

9. The method of claim 8 , wherein determining the alpha value further comprises:
determining a total area of the triangles in the list of triangles;
calculating a value based on the percentage value and the total area; and
determining the alpha value by iterating through the list of triangles from shortest radius to longest radius; while iterating through the list of triangles, adding the area of each triangle to an aggregate area value until the aggregate area value is greater than or equal to the value; and selecting the radius of the last triangle whose area is added to the aggregate area value as the alpha value.

10. The method of claim 8 , wherein determining the alpha shape based on the alpha value comprises:
generating a circle having a radius equal to the alpha value; and
iterating through each pair of points in the set of points to identify a set of edges configured to define the alpha shape by including in the set of edges each edge formed by a pair of points in the set of points where the circle can be positioned to touch the pair of points without the circle enclosing any other points in the set of points.

11. The method of claim 8 , wherein the alpha shape is a first alpha shape, wherein the set of points is a first set of points, and wherein the method further comprises:
determining a second alpha shape based on a second alpha value, the second alpha value determined based on a second triangulation based on a second set of points and the percentage value, the second set of points being a scaled version of the first set of points, the second alpha shape and the first alpha shape having a same shape.

12. The method of claim 8 , wherein the alpha shape is usable for rendering a polygon defined by a subset of the set of points.

13. The method of claim 8 , wherein the request from the client device includes the percentage value.

14. The method of claim 8 , wherein the percentage value is determined based on a number of points in the set of points.

15. A system comprising:
a set of processing units; and
a non-transitory machine-readable medium storing instructions that when executed by at least one processing unit in the set of processing units cause the at least one processing unit to:
receive, from a client device, a request for an alpha shape formed from a set of points;
determine a triangulation based on the set of points;
determine an alpha value based on the triangulation and a percentage value by determining a list of triangles comprising each triangle in the triangulation, determining an area for each triangle in the list of triangles, determining a circumcircle for each triangle in the list of triangles, determining a radius of the circumcircle for each triangle in the list of triangles, and sorting the list of triangles from shortest radius to longest radius;
determine an alpha shape based on the alpha value; and
provide the client device the alpha shape.

16. The system of claim 15 , wherein determining the alpha value further comprises:
determining a total area of the triangles in the list of triangles;
calculating a value based on the percentage value and the total area; and
determining the alpha value by iterating through the list of triangles from shortest radius to longest radius; while iterating through the list of triangles, adding the area of each triangle to an aggregate area value until the aggregate area value is greater than or equal to the value; and selecting the radius of the last triangle whose area is added to the aggregate area value as the alpha value.

17. The system of claim 15 , wherein determining the alpha shape based on the alpha value comprises:
generating a circle having a radius equal to the alpha value; and
iterating through e

Assignees

• Sap Se

Inventors

• Bastian Kai-Niklas
• Gildhoff Hinnerk
• Grouisborn Tim
• Jung Michael

Classifications

• G06F7/08

  Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry (by merging two or more sets of carriers in ordered sequence G06F7/16) · CPC title

• G06T17/205

  Re-meshing · CPC title

• G06T17/10 Primary

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title

• G06T17/20 Primary

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title

• G06T2210/56

  Particle system, point based geometry or rendering · CPC title