A new approach (extra vertex) and generalization of Shoelace Algorithm usage in convex polygon (Point-in-Polygon)

Ochilbek Rakhmanov

A new approach (extra vertex) and generalization of Shoelace Algorithm usage in convex polygon (Point-in-Polygon)

T0 review · 2 major / 0 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Adding an extra vertex to the Shoelace summation identifies whether a point lies inside a convex polygon.

desk verdict The paper claims an extra-vertex tweak to Shoelace for convex point-in-polygon but supplies no derivation or test details to back the effectiveness claim. read the letter →

arxiv 1907.11015 v1 pith:YNZ4VD7C submitted 2019-07-25 cs.CG

Ochilbek Rakhmanov This is my paper

classification cs.CG

keywords Shoelacealgorithmpoint-in-polygonconvexpolygonextravertexareacalculationCartesiancoordinateslinesegmentintersection

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces a modified Shoelace algorithm that inserts one extra vertex into the coordinate list when computing the signed area for a test point. This change is presented as a way to decide point inclusion for convex polygons on the Cartesian plane. The method is then extended to cover line-segment checks and general polygon cases. Python tests are used to compare performance against existing approaches, with the claim that the new version runs more effectively.

What carries the argument

The extra-vertex insertion step that augments the standard Shoelace summation so the resulting signed area sign or magnitude indicates point containment.

What would settle it

A concrete convex polygon together with a test point that the modified Shoelace sum classifies differently from the known geometric truth (for example, a point strictly inside that yields a sum whose sign indicates outside).

Watch

Extended reading notes

Core claim

By inserting an extra vertex into the vertex list before applying the Shoelace formula, the signed area computation can be repurposed to return a consistent inside/outside classification for any test point relative to a convex polygon; the same construction is asserted to generalize directly to line segments and to arbitrary polygons.

Load-bearing premise

Inserting a single extra vertex into the Shoelace list will always produce the correct inside/outside answer for every convex polygon and every test point without further checks or special cases.

Editorial extensions

If this is right

The same extra-vertex construction applies to deciding whether a line segment intersects a convex polygon.
The construction extends without change to non-convex polygons.
Python implementations of the method run faster than the standard point-in-polygon routines used in the tests.
Area calculations remain the only arithmetic operation required for the inclusion test.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The approach might reduce the number of special-case branches needed in graphics libraries that already use Shoelace for area.
If the extra vertex is chosen as a fixed offset from an existing vertex, the method could be implemented with only one additional addition and multiplication per test point.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The core idea is to insert one extra vertex into a convex polygon and reuse the Shoelace summation to decide whether a query point lies inside. The abstract positions this as both a new approach and a generalization that also covers line segments. Python experiments are said to show better performance than existing methods. That is the full extent of what is presented here. The work stays inside standard computational geometry and does not introduce new primitives or complexity bounds. On the positive side, restricting attention to convex polygons removes the need to handle reflex vertices, which keeps the implementation short. The generalization claim to line segments is at least a clear direction even if undeveloped. The main weaknesses are the absence of any algebraic justification for why the extra vertex produces a correct inside/outside result and the lack of any reported baseline, error count, or edge-case handling. Without those, the reported effectiveness cannot be separated from an implementation that simply passed the chosen examples. Degenerate placements (point on edge, collinear vertices) are not addressed. The paper therefore reads as an implementation note rather than a verified algorithm. It would be of interest only to someone already writing a small geometry routine in Python who wants another variant to try; it does not contain enough substance for a reading group or for citation in research that requires proven correctness. I would not send it to referees.

Referee Report

2 major / 0 minor

Summary. The paper proposes a new method for the point-in-polygon test on convex polygons that inserts an extra vertex before applying the Shoelace formula, generalizes the approach to line segments and polygons, and reports Python implementation tests claiming greater effectiveness than existing methods.

Significance. If the extra-vertex construction were shown to be correct and the reported timing advantage were reproducible against standard baselines, the work would supply a simple, easily implemented alternative for convex PIP queries. The generalization to segments and polygons is a positive direction, but the current manuscript supplies neither an algebraic justification nor comparative data, so the practical significance cannot yet be evaluated.

major comments (2)

[Abstract / method description] Abstract and method description: the central claim that the extra-vertex Shoelace variant correctly identifies interior points for every convex polygon is unsupported by any derivation, algebraic identity, or case analysis (including points on edges, vertices, or collinear chains). This is load-bearing for the effectiveness assertion.
[Testing section] Testing section: the statement that 'Results of tests show that the new approach is more effective' is not accompanied by any baseline algorithm, error metrics, test-suite description, or handling of degenerate inputs, leaving the comparative claim without visible evidence.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below and commit to revisions that will strengthen the presentation of the method and its evaluation.

read point-by-point responses

Referee: [Abstract / method description] Abstract and method description: the central claim that the extra-vertex Shoelace variant correctly identifies interior points for every convex polygon is unsupported by any derivation, algebraic identity, or case analysis (including points on edges, vertices, or collinear chains). This is load-bearing for the effectiveness assertion.

Authors: We agree that a formal derivation and case analysis are required to substantiate the central claim. In the revised manuscript we will add an algebraic justification showing how the extra vertex modifies the signed area computation while preserving the interior/exterior distinction for convex polygons, together with explicit case analysis for boundary points, vertices, and collinear chains. revision: yes
Referee: [Testing section] Testing section: the statement that 'Results of tests show that the new approach is more effective' is not accompanied by any baseline algorithm, error metrics, test-suite description, or handling of degenerate inputs, leaving the comparative claim without visible evidence.

Authors: We accept that the testing section must be expanded. The revision will specify the baseline algorithms (standard ray-casting and winding-number implementations), report accuracy and timing metrics, describe the test suite (polygon counts, point distributions, trial numbers), and document handling of degenerate inputs such as boundary and collinear cases. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No derivation or first-principles claim present; method described at procedural level only

full rationale

The manuscript proposes inserting an extra vertex into the Shoelace summation as a point-in-polygon test for convex polygons and reports Python timing results, but supplies neither equations, an algebraic identity, a uniqueness argument, nor any derivation chain. Without a claimed prediction or first-principles result that could reduce to its inputs, no circularity of the enumerated kinds can be exhibited. The effectiveness statement rests on empirical tests rather than a mathematical reduction that would require inspection.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract supplies no equations, parameters, or background assumptions that can be audited.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A new approach (extra vertex) and generalization of Shoelace Algorithm usage in convex polygon (Point-in-Polygon)." pith.science (2026). https://pith.science/paper/YNZ4VD7C

@misc{pith2026190711015,
  author       = {Pith},
  title        = {Pith review of: A new approach (extra vertex) and generalization of Shoelace Algorithm usage in convex polygon (Point-in-Polygon)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YNZ4VD7C}},
  note         = {Machine review of arXiv:1907.11015}
}

read the original abstract

In this paper we aim to bring new approach into usage of Shoelace Algorithm for area calculation in convex polygons on Cartesian coordinate system, with concentration on point in polygon concept. Generalization of usage of the concept will be proposed for line segment and polygons. Testing of new method will be done using Python language. Results of tests show that the new approach is more effective than the current one.

Figures

Figures reproduced from arXiv: 1907.11015 by the authors.

**Figure 2.** Representation of shoelace algorithm Actually, sum of area method is also using the same idea used in shoelace algorithm. It divides the polygon into many triangles, with one fixed vertex and calculates the area of all formed triangles. The approach this paper proposing is still using triangle method, but not with one fixed point vertex. We should underline this paper’s methodology will be more concentrated on conve… view at source ↗

**Figure 3.** Ray shooting concept represantation. One of most popular algorithms is Ray Shooting method. Randolph Franklin converted Ray Shooting method into 7 line C code, after several trials with his doctoral students. The algorithm is simple; from any chosen point, you go through a ray to any side of a polygon. If the ray intersects the polygon in odd number times, than it is inside of it, for even number it is oppose, it is… view at source ↗

**Figure 4.** Triangulation with fixed vertex Assume that point H is inside of enclosed polygon and point K is outside. Fixing these points as one of triangle vertices, divide polygon into triangles with respect to each side of polygon. Fig.5 demonstrates the triangulation for point H, and Fig.6 for point K [PITH_FULL_IMAGE:figures/full_fig_p002_4.png] view at source ↗

Figures from the paper (6 more)

**Figure 5.** Figure 5: Triangulation with point H If we calculate total area of newly formed 7 triangles with fixed vertex H, it is clear that the area will be same with our original polygon P, with area of A ABCDEFG () . No matter where the point H will be, inside the polygon, result will b…

**Figure 6.** Figure 6: Triangulation with point K. C. A new approach on point in polygon The new approach this paper is proposing is to evaluate point H, or K, as one of the points of the polygon listed in clockwise direction and forms a new polygon P1 with vertices ABCDHEFG, or P2 with vert…

**Figure 7.** Figure 7: Point H as a extra vertex. It is clear to observe, from Fig.6, that when the point H is inside the polygon, the new formed polygon P1 (ABCDHEFG) will definitely have smaller area size than original polygon P (ABCDEFG) [PITH_FULL_IMAGE:figures/full_fig_p003_7.png]

**Figure 8.** Figure 8: Point K as a extra vertex. Point H will push one of the sides of the polygon to inner side of the polygon; consequently, will decrease the area of the polygon, while point K will form extra triangle with one of the side, hence will increase the area of the polygon. As …

**Figure 10.** Figure 10: Results for polygon with 20 sides [PITH_FULL_IMAGE:figures/full_fig_p004_10.png]

**Figure 11.** Figure 11: Results for polygon with 180 sides [PITH_FULL_IMAGE:figures/full_fig_p004_11.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

This generalization can only contradict if the polygon is concave

Line Segment If it is needed to check whether a line segment lies in-side the polygon region, then it is sufficient to check if the beginning and ending point are both inside the polygon. This generalization can only contradict if the polygon is concave. In this case, it is necessary to check whether the line segment is intersecting with any sides of the ...

work page
[2]

Fig.9 demonstrates how all vertices of New Polygon (LJONM) are placed inside of P

Polygon To check whether a new given polygon is completely inside of the polygon P, just like in line segment condition, all the vertices of the polygon should be checked whether they are inside of P. Fig.9 demonstrates how all vertices of New Polygon (LJONM) are placed inside of P. If any of those vertices will drop out than it is clear that polygons are...

work page
[3]

Assigning variables x=[x 1,x2,…,xn] , y=[y1,y2,…,yn] (x and y coordinates) k=number of vertices Ps = area calculated with SLA Pt= area calculated with triangulation x f, yf = fixed point for triangle calculation xout, yout = new points chosen outside of polygon xin, yin = new points chosen inside of polygon

work page
[4]

Shoelace algorithm and result of area calculation: def AreaSL(x,y,k): for i in range (0,k): Calculate area using (3.2) return float area (or double) P=AreaSL(x,y,k)

work page
[5]

Round, float or double can be used

Triangulation of polygon and area calculation result def AreaT(xf, yf , x,y,k): for i in range (0,k): calculate area using (3.2), for 3 vertices with one fixed (x f, yf) return float area (or double) Pt=AreaT(x[i],y[i],x,y,k) (#i is any edge on P) It is necessary to underline that choosing the type of the result will affect this result. Round, float or do...

work page
[6]

Assigning new points for test and appending them to existing list: x=x.append(x new) y=y.append(y new)

work page
[7]

Testing new points with Shoelace algorithm, using extra vertex concept. x=x.append(xin) y=y.append(yin) k=k+1 if(AreaSL(x,y,k)>P): outside point else: inside point x=x.append(xout) y=y.append(yout) k=k+1 if(AreaSL(x,y,k)<P): inside point else: outside point

work page
[8]

Testing new points with triangulation: if(AreaT(xin, yin ,x,y,k)>P): outside p else: inside point if(AreaT(xout, yout ,x,y,k)>P): outside p else: inside point F. Analysis of algorithms( existing and extra vertex) Both of the algorithms (triangulation method and extra vertex method) loops for n times, hence both can be accepted as linear function. So time ...

work page

Show all 13 references

[9]

On the complexity of point-in-polygon algorithms

C.W. Huang et al., “On the complexity of point-in-polygon algorithms”. Compufers& Geosciences Vol. 23, No. I, pp. 109-I 18, 1997

1997
[10]

The Surveyor's Area Formula

B. Braden. “The Surveyor's Area Formula”. The College Mathematics Journal. 17 (4): 326–337. 1986

1986
[11]

F.M. Chowdhury et al.,”The Unidirectional Edge Method: A New Approachfor Solving Point Enclosure problem for Arbitrary Polygon”, Asian Journal of Information Technology 4 (5): 537-540, 2005

2005
[12]

Randolph Franklin, 1994, PNPOLY - Point In-clusion in Polygon Test

W. Randolph Franklin, 1994, PNPOLY - Point In-clusion in Polygon Test. Rensselaer Polytechnic Institute. https://wrf.ecse.rpi.edu/Research/Short_Notes/ pnpoly.html (accessed 04/25/2017)

1994
[13]

(November 1987)

Bourke P. (November 1987). Determining if a point lies interior of Polygon. University of Western Australia. http://paulbourke.net/geometry/polygonmesh (accessed on 01/05/2017)

1987

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.

[1] [1]

This generalization can only contradict if the polygon is concave

Line Segment If it is needed to check whether a line segment lies in-side the polygon region, then it is sufficient to check if the beginning and ending point are both inside the polygon. This generalization can only contradict if the polygon is concave. In this case, it is necessary to check whether the line segment is intersecting with any sides of the ...

work page

[2] [2]

Fig.9 demonstrates how all vertices of New Polygon (LJONM) are placed inside of P

Polygon To check whether a new given polygon is completely inside of the polygon P, just like in line segment condition, all the vertices of the polygon should be checked whether they are inside of P. Fig.9 demonstrates how all vertices of New Polygon (LJONM) are placed inside of P. If any of those vertices will drop out than it is clear that polygons are...

work page

[3] [3]

Assigning variables x=[x 1,x2,…,xn] , y=[y1,y2,…,yn] (x and y coordinates) k=number of vertices Ps = area calculated with SLA Pt= area calculated with triangulation x f, yf = fixed point for triangle calculation xout, yout = new points chosen outside of polygon xin, yin = new points chosen inside of polygon

work page

[4] [4]

Shoelace algorithm and result of area calculation: def AreaSL(x,y,k): for i in range (0,k): Calculate area using (3.2) return float area (or double) P=AreaSL(x,y,k)

work page

[5] [5]

Round, float or double can be used

Triangulation of polygon and area calculation result def AreaT(xf, yf , x,y,k): for i in range (0,k): calculate area using (3.2), for 3 vertices with one fixed (x f, yf) return float area (or double) Pt=AreaT(x[i],y[i],x,y,k) (#i is any edge on P) It is necessary to underline that choosing the type of the result will affect this result. Round, float or do...

work page

[6] [6]

Assigning new points for test and appending them to existing list: x=x.append(x new) y=y.append(y new)

work page

[7] [7]

Testing new points with Shoelace algorithm, using extra vertex concept. x=x.append(xin) y=y.append(yin) k=k+1 if(AreaSL(x,y,k)>P): outside point else: inside point x=x.append(xout) y=y.append(yout) k=k+1 if(AreaSL(x,y,k)<P): inside point else: outside point

work page

[8] [8]

Testing new points with triangulation: if(AreaT(xin, yin ,x,y,k)>P): outside p else: inside point if(AreaT(xout, yout ,x,y,k)>P): outside p else: inside point F. Analysis of algorithms( existing and extra vertex) Both of the algorithms (triangulation method and extra vertex method) loops for n times, hence both can be accepted as linear function. So time ...

work page