todo.org

HsYAML has GLPL licence apparently

make a constructable point class, getting rid of the Default ext constraints

make everything public sublibraries of hgeometry

hopefully this will also make the CI story easier

rename the minimum1 and maximum1 functions in the HGeometry.List.Utils module

build clean with werror

hgeometry-combinatorial

hgeometry-vector

hgeometry-point

hgeometry-kernel

hgeometry

hgeometry-ipe

hgeometry-svg

update the readme

haddock builder

hgeometry-examples

bapc stuff as tests

floorpainting BAPC example with the segment tree :)

move LINEQ to HGeometry.Line.NonVertical

fromPointAndNormal of NonVertical hyperplane

this can’t be right:

fromPointAndNormal _ n = NonVerticalHyperPlane n

we should really use the in plane point p

normal vector business

want:

• normalVector points into the positive halfspace
• onSideTest p

write some tests for testing line x line intersections of the various forms

basically test that converting to a diff line type results in consistent results

polymorphic cooordinates

Doctests

vector

point

kernel

hgeometry

hgeometry-ipe

hgeometry-combinatorial

setup hspec tests

vector

point

kernel

hgeometry

raytracer demo

Ray x Triangle intersection

https://en.wikipedia.org/wiki/M%C3%B6ller%E2%80%93Trumbore_intersection_algorithm

our Melkman algorithm also just works when given a polyline.

See if we can generalize its type signatures

2d linear programming

port the visibility polygon stuff

port the shortest path in simple polygon stuff

ccwPredecessorOf’ and ‘ccwSuccessorOf’ convex polygon

additional quickcheck tests

all vertices of a simple polygon lie on the boundary of the polygon (pointInPoly)

generate random simple polygons

ipe tests

point

kernel

CANCELED IntersectionSpec

BoxSpec

trianglespec

LineSegmentSpec

most of the tests are uncommented. Not sure why

halflinespec

intersecting halflines with boxes seems to go wrong somehow.

hgeometry

convex polygon spec

box x box intersection

fromExtent to build a Box

renderer

ipe-renderer

test import

ipe-reader

point in polygon

for simple polygon

Line segment intersection ; i.e Benthey Otham

the naive algorithm

represent the various types of intersections

debug the onSideTest hyperplane function again

test intersection for colinear line segments incorrect

benthey othham for open-ended segments.

polygon triangulation

triangulate monotone

triangiulate non-monotone

split into non-monotone parts

graph representation

triangulate a polygon with holes

triangulate world demo/benchmark

initial run that actually triangulates the whole world:

cabal run hgeometry-examples:hgeometry-triangulateworld – -i -o 130.82s user 0.50s system 99% cpu 2:12.23 total

verify fromPoints

i.e. add a test that makes sure that the cyclic zero’s are correct, i.e. that

myPoly :: SimplePolygon (Point 2 R) myPoly = fromJust . fromPoints $ read @[Point 2 R] “[Point2 0 0,Point2 26 37.1,Point2 7.1 45.2,Point2 (-6.6) 39,Point2 (-1.9) 15.1,Point2 (-1.4) 12.7,Point2 0 0]”

sanitizes the two Point2 0 0’s at the end and the start

polygons with holes

represent polygons with holes

inpolygon test

make sure we can report in which hole we are as well

some tests

render them to ipe

intersect with a line or with a segment

avoid binary files in the tests ; replace them with json files or so

(in particular, the arbitrary instances for polygon)

update the readme

add other libraries

the type for convex hull seems wrong/not general enough; why don’t we accept an Foldable1 ?

polyline simplification

imai iri

DP

arrangement

line-segment-intersection sweep

planar subdivision

plane graph

3d-lower-envelope

naive

triangulated envelope

handle degeneracies

handle all colinear

cyclic sorting of the edges

set up generating plane graphs so that we I can devbug the separator stuff

define tests

correctly render a lower envelope/vd with 1 vertex and 3 unbounded edges

correctly render bounded edges of some larger set of points

correctly render unbounded edges of some larger set of points

properyt test that every (bounded) face is convex

some sort of benchmarking for the naive algorithm

Set3 type to clean up and/or speed up the fromVertexForm code ?

I wonder if we can clean up and/or speed up the fromVertexForm code by having a specific Set3 type that stores at least three elements. Since every vertex should have at least (and probably often also exactly) three definers, this could clean up some of the code. (We have a few “there should be at least three items here” cases).

Still not entirely sure that will help stufficiently though. Since we are sometimes relying on sorting etc, to be efficient.

e.g. if we have three definers, and we delete h from it (where h is guaranteed to appear: )

planar separators

batch point-location by sweeping scheme

vertices -> adjrep

3d convex hull

render faces as polygons

3d export of the lower envelope

Convex polygons

binary search extremal direction

point in polygon

almost done; but needs some fractional -> num work in point on line segment

report the edge on whichwe lie in case we lie on an edge

make an inpolygon typeclass

test pointInPolygon for convex polygons; seems we have a discrepency

data structures

kd-tree

range-tree

base tree

segment-tree

base tree

quad-tree

interval-tree

2d-convex hull algos

divide and conquer

quickhull

jarvis march

convex hull of polygon

smallest enclosing ball

linear programming (RIC)

delaunay triangulation

voronoi diagram

all colinear points

closest pair

minkowski-sum

fix testcases

probably requires testing if two polygons are cyclic shifts

common intersection of halfplanes

have some type representing the unbounded common intersection part

profile the convex hull algos, since they are quite a bit slower than just sorting.

– I’m now guessing that the _Vector iso is causing the trouble, since that thing is potentially rebuilding a new vector (using generate) even if we are just accessing some field. If that is indeed happening, then that is very wasteful.

clean up the benchmarks

images in the haddocks

visual debugger

maybe make s.t. like prettychart; i.e have some webserver running that can show geometries as svg, and use ghci to start the server and send input to the server.

index state

cabal v2-update ‘hackage.haskell.org,2022-12-29T17:16:17Z’

performance

I compared the BAPC armybase tests. It’s a bit of an apples vs oranges comparison, since I only had an old 8.10.7 build of the bapc examples around, and I’ve built the new stuff using 9.6.1

anyway, the old bapc armybase testsuite took

13.65s user 0.03s system 99% cpu 13.687 total

whereas the new run took roughly

8.28s user 0.02s system 99% cpu 8.305 total

not sure what’s the mian gain. Maybe most of it is simply switching to a faster sorting algo; since we are now using vector-algorithms’s introsort rather than mergesort. > Still, it’s nice that we are faster :).

old tests