Here is my problem;
I am trying to find the outline of a shape which consists of a series of polys (I'm reading the shape in from a .obj file so the vertex are sorted by poly)
I have tried Jarvis and Graham's convex hull algorithms and they seem to be culling vertex (which i don't want)
I have all the information of an .obj file at my disposal.
Can anyone help me solve this problem?
I need to be able to draw the outline starting from any point and then continue clockwise.
Any help would be greatly appreciated
*** EDIT *** Added some code as an example
Red/Green dots are points (Green dot is the starting point)
White lines are the Jarvis Convex hull
// Project: outline test
// Created: 2017-10-26
// show all errors
SetErrorMode(2)
// set window properties
SetWindowTitle( "outline test" )
SetWindowSize( 1024, 768, 0 )
SetWindowAllowResize( 1 ) // allow the user to resize the window
// set display properties
SetVirtualResolution( 1024, 768 ) // doesn't have to match the window
SetOrientationAllowed( 1, 1, 1, 1 ) // allow both portrait and landscape on mobile devices
SetSyncRate( 30, 0 ) // 30fps instead of 60 to save battery
SetScissor( 0,0,0,0 ) // use the maximum available screen space, no black borders
UseNewDefaultFonts( 1 ) // since version 2.0.22 we can use nicer default fonts
type point
x as float
y as float
endtype
points as point[]
point as point
jarvis as point[]
values as float[11] = [ -358.155, 201.439, -267.644, 150.927, -278.418, 132.039, -288.892, 103.452, -389.509, 119.435, -291.066, 74.865 ]
i as integer
for i=0 to values.length step 2
point.x = values[i]
point.y = values[i + 1]
points.insert(point)
next
jarvis = JarvisConvexHull(points, points.length)
do
DrawShape(jarvis, points)
Print( ScreenFPS() )
Sync()
loop
function DrawShape(points as point[], dots as point[])
i as integer
fp as point
tp as point
for i=0 to dots.length
fp = dots[i]
DrawEllipse(fp.x + 500, fp.y+300, 3, 3, MakeColor(0xff, 0, 0), MakeColor(0xff, 0, 0), 1)
next
for i=0 to points.length
fp = points[i]
if i = points.length
tp = points[0]
else
tp = points[i + 1]
endif
drawline(fp.x + 500, fp.y + 300, tp.x + 500, tp.y + 300, 0xff, 0xff, 0xff)
if i = 0
DrawEllipse(fp.x + 500, fp.y+300, 6, 6, MakeColor(0, 0xff, 0), MakeColor(0, 0xff, 0), 1)
endif
next
endfunction
function Orientation(p as point, q as point, r as point)
var as float
var = ((q.y - p.y) * (r.x - q.x)) - ((q.x - p.x) * (r.y - q.y))
if var > 0
var = 1
elseif var < 0
var = 2
endif
endfunction var
function JarvisConvexHull(points as point[], n as integer)
l as integer
length as integer
i as integer
q as integer
p as integer
hull as point[]
l=0
// Find the leftmost point
for i=1 to points.length
if points[i].x < points[l].x
l = i
endif
next
p = l
length = points.length
repeat
hull.insert(points[p])
q = mod(p + 1, n + 1)
for i=0 to n
if Orientation(points[p], points[i], points[q]) = 2
q = i
endif
next
p = q
until p = l
endfunction hull
