Given a line similar to what you see here... even if I strip it down to a single pixel like the single pixel version, I can't seem to find a good tool to extract the vertices of these lines. I've tried a couple physics body tools and photoshop and illustrator kinda has a way to script out vertices...although I couldn't get it to recognize the lines as shape, as a pre-requisite. Anyone know how I might get the vertices of a complex hand-drawn line? How do other engines do it?

##
How to determine the vertices of a line
Started by
jack95
Aug 13 2019 10:38 PM

Anyone know how I might get the vertices of a complex hand-drawn line? How do other engines do it?

I'm not aware of any engine that'll do what you ask at run-time.

Suggest you give up on raster-to-vector conversion - the best you're likely to do is create an outline of the stroked path (because pixels have >0 area, though your brain might "see" a "line" in that raster, it is not a proper "line", at best it is the "rasterized shell of a stroked line" - which results in an areal feature, not a linear feature)

So instead, suggest you draw these freehand lines with a vector tool where you'll be able to treat it as a proper line with actual vertices. You may need to densify (add vertices) then simplify (remove curves) after freehanding, depending on the tool used. But once you have clean vectors, just save as svg, then it'll be easy to parse the coords in xml form.

because pixels have >0 area?

Pixels are coordinate points. They do not have an area. Another term I have heard is "path" or "bezier curve".

I freehand pixels and those are the points of the line. I don't care about the angles, I just care about the physical points (all of them, discretely).

I don't understand "line with actual vertices" or "densify", when the points are sufficiently specific.

When tracing the line in photoshop, I get coordinates. This is what I want. Maybe vertex is the incorrect term, but I have been using it as something like "x,y within a constrained plane"

I see imagemagick has something like this:

http://im.snibgo.com/linptcv.htm#autotr

Hi.

I don't know about programs that already do it, but have an idea how I would tackle it.

A plugin I wrote has a method to load an image as raw data. I'd probably go with its "mask" option to get one byte per pixel, then detect whether those pixels' values, between 0 and 255, were below some threshold (in case they weren't strictly black or white).

It would be slightly easier if you knew where to start. Otherwise I guess you'd scan until finding a black one.

Anyhow, you probably don't care too much about speed and could just write this as a little helper program. Then a flood fill approach ought to do. Something like:

local visited = {} local stack = {} local function Index (x, y) return (y - 1) * ImageWidth + x end local function XY (index) -- undo the Index() op local x = ((index - 1) % ImageWidth) + 1 local y = (index - x) / ImageWidth return x, y end EmitVertex(X, Y) -- first black pixel local LastX, LastY = X, Y stack[#stack + 1] = Index(X, Y) local function TryToAdd (x, y) local index = Index(x, y) if not visited[index] then stack[#stack + 1] = index end end repeat local spot = table.remove(stack) local x, y = XY(spot) if x > 1 then TryToAdd(x - 1, y) end if x < ImageWidth then TryToAdd(x + 1, y) end if y > 1 then TryToAdd(x, y - 1) end if y < ImageHeight then TryToAdd(x, y + 1) end -- can adjust for 8-way and so on, too... if (x - LastX)^2 + (y - LastY)^2 >= SomeDistanceSquared then -- are we far enough from the previous vertex? EmitVertex(x, y) LastX, LastY = x, y end visited[spot] = true until #stack == 0 -- Emit a final vertex if far enough...

(Untested!)

This assumes you have "nice" lines, of course. Also, if you search for a first pixel, the general case would require some work to fill ahead and behind. (You might do a first-pass "fill" to discover an endpoint and then restart there.) But maybe it's a starting point?

Pixels are coordinate points. They do not have an area.

Then we're speaking two totally different languages.

To me: A pixel is a square (nominally), it occupies space, it has a finite measurable size, for instance can be measured in terms of dots-per-inch, etc. A vertex is a point, thus zero area, and an infinite number (notwithstanding storage limitations of the number representation) of unique points could created within any measurable distance, a purely mathematical description of geometry.

If you traced that raster with a vector tool (like Illustrator) you'd probably get cubic curves along with straight segments - that's where "densify" and "simplify" would come in - to generate more discrete vertices.

But given that you seem to want "an ordered list of all black pixel coordinates" then Starcrunch's approach (as a preprocessing step) would probably be best. hth