Reducing points in polygon

Processing Coding Questions
3

I’ve made a Python Mode version too: :snake:

RamerDouglasPeucker.pyde:

"""
 * Ramer-Douglas-Peucker Algorithm (v1.2.3)
 * GoToLoop & JeffThompson (2019/Aug/27)
 *
 * https://Discourse.Processing.org/t/reducing-points-in-polygon/13590/3
 *
 * https://en.Wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
 * https://Karthaus.nl/rdp/js/rdp2.js
 *
 * https://Bl.ocks.org/GoToLoop/a5db257be4d7756a00220a3e97066dd5
 * https://www.OpenProcessing.org/sketch/747172
"""

from Calc import reducePolygon
from Data import loadCoordsXYAsPVectorsTuple

QTY, DIAM, BOLD = 12, 15, 2;
BG, FG, STROKE = -1, 0x64000000, 0xff0096FF

DEBUG = True

def setup():
    size(800, 600)
    smooth(), noLoop(), strokeWeight(BOLD)

    global coords, reduced

    coords = loadCoordsXYAsPVectorsTuple()
    if DEBUG: print "Polygon's original size: %d" % len(coords)

    reduced = reducePolygon(coords, QTY, DEBUG = DEBUG)
    if DEBUG: print "Polygon's final size: %d\n" % len(reduced)

    if DEBUG:
        txt, digits = '%s: %s', len(`max(0, len(reduced) - 1)`)
        for i, v in enumerate(reduced): print txt % (`i`.zfill(digits), v)


def draw():
    background(BG)
    drawPoints(coords)

    translate(width >> 1, 0)
    drawPoints(reduced)


def drawPoints(dots):
    if not dots: return

    noFill()
    stroke(STROKE)

    with beginClosedShape():
        for v in dots: vertex(v.x, v.y)

    fill(FG)
    noStroke()

    for v in dots: circle(v.x, v.y, DIAM)

Calc.py:

ERRORS = (
    "Polygon's newSize parameter can't be less than 2!",
    "Parameter dots[] must contain at least 2 PVector objects!",
    "Parameter epsilon can't be a negative value!"
)

MSG = 'Step: %d\t\tSize: %d'

def reducePolygon(dots, newSize, ep=0, DEBUG=True):
    if newSize < 2: raise ValueError(ERRORS[0])

    while True:
        reduced = shortDistRDP(dots, ep)
        currLen = len(reduced)

        if DEBUG: print MSG % (ep, currLen)

        if currLen <= newSize: return reduced
        ep += 1


def shortDistRDP(dots, epsilon):
    if not dots or len(dots) < 2: raise ValueError(ERRORS[1])
    if epsilon < 0: raise ValueError(ERRORS[2])

    qty = len(dots)
    if (qty == 2): return dots[:]

    head = dots[0]
    tail = dots[-1]
    last = qty - 1

    maxDistSq = 0
    idx = -1

    for i in xrange(1, last):
        currDistSq = dotToLineDistSq(dots[i], head, tail)

        if (currDistSq > maxDistSq):
            maxDistSq = currDistSq
            idx = i

    if sqrt(maxDistSq) > epsilon:
        recurResL = shortDistRDP(dots[:idx+1], epsilon)
        recurResR = shortDistRDP(dots[idx:], epsilon)

        return recurResL[:-1] + recurResR

    return dots[::last]


def dotToLineDistSq(p, v, w, z=PVector()):
    lineLen = vec2dDistSq(v, w)
    if not lineLen: return vec2dDistSq(p, v)

    lineX = w.x - v.x
    lineY = w.y - v.y
    t = ((p.x - v.x)*lineX + (p.y - v.y)*lineY) / lineLen

    if t < 0: return vec2dDistSq(p, v)
    if t > 1: return vec2dDistSq(p, w)

    return vec2dDistSq(p, z.set(v).add(t * lineX, t * lineY, 0))


def vec2dDistSq(a, b): return sq(a.x - b.x) + sq(a.y - b.y)

Data.py:

# 'xy.csv', 'simple.csv', 'backtracking.csv', 'diff.csv'

def loadCoordsXYAsPVectorsTuple(FILE='xy.csv', SEP=',', f=PApplet.parseFloat):
    return tuple(PVector().set(f(r.split(SEP))) for r in loadStrings(FILE))

xy.csv:

337,333
337,342
333,390
332,391
328,406
328,407
328,408
314,445
314,446
291,494
291,495
289,499
276,525
272,531
271,532
266,539
261,543
259,545
257,547
256,548
253,549
252,550
247,551
234,552
222,552
221,551
219,550
219,550
159,443
154,433
151,424
150,422
139,392
135,380
134,378
124,326
122,313
118,283
118,270
118,258
119,245
121,227
126,193
129,182
132,173
133,171
154,134
208,41
220,41
220,42
277,127
286,142
304,174
319,211
320,213
320,214
330,243
330,245
330,246
334,260
334,262
337,299

simple.csv:

92,158
80,158
69,153
67,147
64,136
63,131
66,126
70,124
75,120
77,118
84,114
96,109
103,105
104,101
103,96
98,92
91,92
83,91
67,91
59,89
55,88
49,83
43,79
43,74
47,66
55,63
61,62
71,64
82,68
93,70
105,73
111,66
112,59
118,55
127,55
129,64
132,74
136,77
147,66
154,41
166,84
169,52
174,64
178,56
183,57
152,13
15,27
70,37
123,23
91,52
84,48
78,55
70,50
65,54
57,52
27,74

backtracking.csv:

14,111
18,114
22,110
25,106
30,106
37,108
44,112
48,115
56,118
57,195
61,118
69,119
73,120
82,120
83,117
88,113
90,47
92,112
99,115
104,114
111,110
113,101
111,91
112,84
115,80
190,77
116,75
117,67
120,64
117,56
116,53
115,46
114,37
110,31
10,27
56,22
74,25
89,22
91,13
107,22
110,26
115,21
117,14

diff.csv:

24,173
26,170
24,166
27,162
37,161
45,157
48,152
46,143
40,140
34,137
26,134
24,130
24,125
28,121
36,118
46,117
63,121
76,125
82,120
86,111
88,103
90,91
95,87
107,89
107,104
106,117
109,129
119,131
131,131
139,134
138,143
131,152
119,154
111,149
105,143
91,139
80,142
81,152
76,163
67,161
59,149
63,138
3 Likes